Databases
StackOverflow2013
Postsdbo
POCounting combinations of pairs of items from multiple lists without repetition
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POCounting combinations of pairs of items from multiple lists without repetition
    primarykey
    data
    text
    <p>Given a scenario where we have multiple lists of pairs of items, for example:</p> <ol> <li>{12,13,14,23,24}</li> <li>{14,15,25}</li> <li>{16,17,25,26,36}</li> </ol> <p>where 12 is a pair of items '1' and '2' (and thus 21 is equivalent to 12), we want to count the number of ways that we can choose pairs of items from each of the lists such that no <em>single</em> item is repeated. You must select one, and only one pair, from each list. The number of items in each list and the number of lists is arbitrary, but you can assume there are at least two lists with at least one pair of items per list. And the pairs are made from symbols from a finite alphabet, assume digits [1-9]. Also, a list can neither contain duplicate pairs {12,12} or {12,21} nor can it contain symmetric pairs {11}.</p> <p>More specifically, in the example above, if we choose the pair of items 14 from the first list, then the only choice we have for the second list is 25 because 14 and 15 contain a '1'. And consequently, the only choice from the third list is 36 because 16 and 17 contain a '1', and 25 and 26 contain a '2'.</p> <p>Does anyone know of an <em>efficient</em> way to count the total combinations of pairs of items without going through every permutation of choices and asking "is this a valid selection?", as the lists can each contain hundreds of pairs of items?</p> <hr> <p><strong>UPDATE</strong></p> <p>After spending some time with this, I realized that it is trivial to count the number of combinations when none of the lists share a distinct pair. However, as soon as a distinct pair is shared between two or more lists, the combinatorial formula does not apply. </p> <p>As of now, I've been trying to figure out if there is a way (using combinatorial math and not brute force) to count the number of combinations in which every list has the same pairs of items. For example:</p> <ol> <li>{12,23,34,45,67}</li> <li>{12,23,34,45,67}</li> <li>{12,23,34,45,67}</li> </ol>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USsnazzer
    1. USsnazzer
    plurals
    1. This table or related slice is empty.
    1. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    3. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POCounting combinations of pairs of items from multiple lists without repetition
      1. UStrh178
      1. VTFavorite
    2. VO
      singulars
      1. POCounting combinations of pairs of items from multiple lists without repetition
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POCounting combinations of pairs of items from multiple lists without repetition
      1. This table or related slice is empty.
      1. VTUpMod
    1. COSmall correction - I think in your example from the second list nothing would be selected as 14,15,25 all have either 1 or 2 as part of the pair of items.
      singulars
      1. POCounting combinations of pairs of items from multiple lists without repetition
      1. USArnkrishn
    2. COAh, thanks for catching that. It should be corrected now.
      singulars
      1. POCounting combinations of pairs of items from multiple lists without repetition
      1. USsnazzer
    3. COCan we only select one pair from each list? Do we have to select an item from each list? Are the number of items in each list arbitrary? Is the number of lists arbitrary? The pairs are made of symbols from some alphabet, is the alphabet finite?
      singulars
      1. POCounting combinations of pairs of items from multiple lists without repetition
      1. USntownsend
 

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