Databases
StackOverflow2013
Postsdbo
POGenerating Balls in Boxes
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POGenerating Balls in Boxes
    primarykey
    data
    text
    <p>Given two sorted vectors <code>a</code> and <code>b</code>, find all vectors which are sums of <code>a</code> and some permutation of <code>b</code>, and which are unique once sorted.</p> <p>You can create one of the sought vectors in the following way:</p> <ul> <li>Take vector <code>a</code> and a permutation of vector <code>b</code>.<br></li> <li>Sum them together so <code>c[i]=a[i]+b[i]</code>.<br></li> <li>Sort <code>c</code>.</li> </ul> <p>I'm interested in finding the set of <code>b</code>-permutations that yield the entire set of unique <code>c</code> vectors.</p> <p><strong>Example 0</strong>: <code>a='ccdd'</code> and <code>b='xxyy'</code><br> Gives the summed vectors: <code>'cycydxdx'</code>, <code>'cxcxdydy'</code>, <code>'cxcydxdy'</code>.<br> Notice that the permutations of <code>b</code>: <code>'xyxy'</code> and <code>'yxyx'</code> are equal, because in both cases the "box c" and the "box d" both get exactly one <code>'x'</code> and one <code>'y'</code>.</p> <p>I guess this is similar to putting <code>M</code> balls in <code>M</code> boxes (one in each) with some groups of balls and boxes being identical.<br> <strong>Update:</strong> Given a string <code>a='aabbbcdddd'</code> and <code>b='xxyyzzttqq'</code> your problem will be 10 balls in 4 boxes. There are 4 distinct boxes of size 2, 3, 1 and 4. The balls are pair wise indistinguishable.</p> <p><strong>Example 1:</strong> Given strings are <code>a='xyy'</code> and <code>b='kkd'</code>.<br> Possible solution: <code>'kkd'</code>, <code>'dkk'</code>.<br> <em>Reason:</em> We see that all unique permutations of <code>b</code> are <code>'kkd'</code>, <code>'kdk'</code> and <code>'dkk'</code>. However with our restraints, the two first permutations are considered equal as the indices on which the differ maps to the same char <code>'y'</code> in string <code>a</code>.<br></p> <p><strong>Example 2:</strong> Given strings are <code>a='xyy'</code> and <code>b='khd'</code>.<br> Possible solution: <code>'khd'</code>, <code>'dkh'</code>, <code>'hkd'</code>.</p> <p><strong>Example 3:</strong> Given strings are <code>a='xxxx'</code> and <code>b='khhd'</code>.<br> Possible solution: <code>'khhd'</code>.</p> <p>I can solve the problem of generating unique candidate <code>b</code> permutations using Narayana Pandita's algorithm as decribed on <a href="http://en.wikipedia.org/wiki/Permutation#Systematic_generation_of_all_permutations" rel="nofollow noreferrer">Wikipedia/Permutation</a>.<br> The second part seams harder. My best shot is to join the two strings pairwise to a list, sort it and use it as a key in a lookup set. (<code>'xx'</code>+<code>'hd'</code> join→<code>'xh','xd'</code> sort→<code>'xd','xh'</code>).</p> <p>As my <code>M</code> is often very big, and as similarities in the strings are common, I currently generate way more <code>b</code> permutations than actually goes through the set filter. I would love to have an algorithm generating the correct ones directly. Any improvement is welcome.</p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USThomas Ahle
    1. USThomas Ahle
    plurals
    1. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POGenerating Balls in Boxes
      1. USJeriko
      1. VTFavorite
    2. VO
      singulars
      1. POGenerating Balls in Boxes
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POGenerating Balls in Boxes
      1. USShivendra
      1. VTFavorite
    1. COI'm really having trouble understanding your constraint and the examples. Can you rephrase it more formally? The wording is also a little hard to understand (e.g. "the indices on which the differ maps to the same char").
      singulars
      1. POGenerating Balls in Boxes
      1. USJohn Feminella
    2. COAlso having a hard time on this. Maybe you consider b[i] equal to b[j] if a[i] == a[j]?! So in example 1 with i=1 and j=2 because both are 'y' in a they are considered equal in b?
      singulars
      1. POGenerating Balls in Boxes
      1. USEiko
    3. COI'm not sure I understand your question. Can you put the first sentence into a complete sentence?
      singulars
      1. POGenerating Balls in Boxes
      1. USJustin L.
 

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