Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>To generate k-combinations of possibly repeated elements (multiset), the following could be useful: <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.50.9222" rel="nofollow noreferrer">A Gray Code for Combinations of a Multiset (1995)</a>.</p> <p>For a recursive solution you try the following:</p> <p>Count the number of times each character appears. Say they are x1 x2 ... xm, corresponding to m distinct characters.</p> <p>Then you need to find all possible ordered pairs (y1 y2 ... ym) such that</p> <p>0 &lt;= yi &lt;= xi</p> <p>and Sum yi = k.</p> <p>Here yi is the number of times character i appears.</p> <p>The idea is, fix the number of times char 1 appears (y1). Then recursively generate all combinations of k-y1 from the remaining.</p> <p>psuedocode:</p> <pre><code>List Generate (int [] x /* array index starting at 1*/, int k /* size of set */) { list = List.Empty; if (Sum(x) &lt; k) return list; for (int i = 0; i &lt;= x[1], i++) { // Remove first element and generate subsets of size k-i. remaining = x.Remove(1); list_i = Generate(remaining, k-i); if (list_i.NotEmpty()) { list = list + list_i; } else { return list; } } return list; } </code></pre> <hr> <p>PRIOR TO EDITS:</p> <p>If I understood it correctly, you need to look at string a, see the symbols that appear exactly once. Say there are k such symbols. Then you need to generate all possible permutations of b, which contain k elements and map to those symbols at the corresponding positions. The rest you can ignore/fill in as you see fit.</p> <p>I remember posting C# code for that here: <a href="https://stackoverflow.com/questions/2350211/how-to-find-permutation-of-k-in-a-given-length/2350399#2350399">How to find permutation of k in a given length?</a></p> <p>I am assuming xxyy will give only 1 unique string and the ones that appear exactly once are the 'distinguishing' points.</p> <p>Eg in case of <code>a=xyy, b=add</code></p> <p>distinguishing point is x</p> <p>So you select permuations of 'add' of length 1. Those gives you <code>a</code> and <code>d</code>.</p> <p>Thus <code>add</code> and <code>dad (or dda)</code> are the ones you need.</p> <p>For <code>a=xyyz b=good</code></p> <p>distinguishing points are x and z</p> <p>So you generate permutations of b of length 2 giving</p> <pre><code>go og oo od do gd dg </code></pre> <p>giving you 7 unique permutations.</p> <p>Does that help? Is my understanding correct?</p>
    singulars
    1. This table or related slice is empty.
    1. POGenerating Balls in Boxes
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USCommunity
    1. This table or related slice is empty.
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. CONo sorry, Is my new explaination better?
      singulars
      1. PO
      1. USThomas Ahle
    2. CO+1 because I understood the same thing ...
      singulars
      1. PO
      1. USDr. belisarius
    3. CONo, the solution doesn't work. That seams clear for a case where there are no unique symbols in a?
      singulars
      1. PO
      1. USThomas Ahle
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload