1
$\begingroup$

I am working a personal project, and I need to derive subsets of permutations of unique elements.

For example: I have a set of 5 unique elements {A, B, C, D, E}. There are 60 permutations tuples of size 3 of this: {A,B,C}, {A,B,D}...{E,C,D}, {E,D,C}. What I want is to select tuples from this list such that the count of each symbol in the same position across all tuples is constrained as 0 < A# < B# < C# < D# < E# the count of each symbol is the same in each position.

E.g.

{A, B, C}
{A, B, D}
⋮
{E, C, D}
{E, D, C}

For the full set of tuples, there are 12 of each symbol in each position within the tuple, or specifically for what is explicitly written above there are quantity A2 and E2 in position 0, B2 C1 D1 in position 1, and C2 and D2 in position 2, so this does not meet the criteria.

With the example of 5 permute 3, as there are only 60 permutation tuples I was able to create such a desired subset by brute force, finding a collection of 20 permutation tuples resulting in counts of A2, B3, C4, D5, E6 in each position.

My question is: Is there a known algorithmic way of selecting subsets with this type of criteria, and is there a predictive formula to calculate how many valid solutions can be derived? I will need this to be for quantities of symbols up to 15 and up to tuple size 5 so brute force is sub-optimal.

For completeness, the solution subset I found for 5 symbols permut 3 is the following set:

AEC
AED
BCE
BDE
BED
CBE
CDB
CDE
CED
DBC
DBE
DCE
DEB
DEC
EAC
EAD
ECA
ECD
EDA
EDB

Edit: Using logic inspired by Ross Millikan, I verified that 4 permut 3 has no solution, as the permut domain is too small. I did find via brute force a solution for 6 permut 3: A3,B4,C5,D6,E7,F8 for a total of 33 tuples:

ABC
ABE
ACD
BCF
BDF
BEF
BFE
CAD
CED
CEF
CFD
CFE
DCE
DCF
DEC
DEF
DFC
DFE
ECF
EDB
EDC
EDF
EFB
EFC
EFD
FAD
FAE
FBA
FBE
FDA
FDB
FEA
FEB
$\endgroup$
1
$\begingroup$

Not an answer, but I hope helpful and too long for a comment.

There are a number of constraints that you can use to guide the search. The big one is that the sum of the counts in each position must match the number of tuples. For your example, you have $20$ tuples and $2+3+4+5+6=20$ Among the $60$ permutations you have $E$ at each slot in $12$ of them. If you were to demand $E\#=12$ you would need $36$ permutations to satisfy that because there are $12\ E$s in each position, which is all the permutations that include $E$. There are $24$ non-E slots which are equally distributed among the other letters, violating your constraint that there be less $A$s than $B$s and so on.

The number of permutations is the sum of the counts because you have one letter in each position of each permutation. If you demanded $E\#=11$ you would need at least $33$ permutations (more if some do not contain $E$ at all). The sum of the other four counts would be at least $22$. That means $D\#$ is at least $7$, so there are at least four $D$s in one position matched with $E$s in the same position. However there are only three choices for the third position, so this will not work. The same argument works for $E\#=10$. You have a hope with $E\#=9, 27$ total permutations with $D\#=6, C\#=5, B\#=4, A\#=3$ Three of the $D$s in each column go with $E$s in each of the other two. That gives you $18$ permutations including $DE$ and one of each of the other letters and uses two of the other letters in each column. If we focus on the ones with $E$ in the first column we have E,D,(A,B,C)
E,(A,B,C),D
for six and we need three more which can only be EAC ECB EBA
and we have an equal number of $A,B,C$ so this fails.

I don't think it is easy

$\endgroup$
1
  • $\begingroup$ Ross, thank you for your contribution and insights. I agree it's a bit complicated :) When I brute forced it, It was only when I started from the top down (A1 and A2) did the pattern reveal itself (with some use of spreadsheet handy conditional formatting to highlight state on remaining permutations, and looking for cases where tuples could be exchanged between the keep and discard categories while changing only a single symbol, e.g. exchanging ACE with ADE to effectively just exchange a C for a D in pos 2. $\endgroup$
    – Ian F
    Dec 7 '20 at 6:11
1
$\begingroup$

Not a complete answer, however some interesting research results

Using the setup of 5 distinct symbols {A,B,C,D,E} permut 3, 60 permutations. I have run exhaustive checks on all permutations for the positional symbol count criteria form of A#1, B#2, C#3, D#4, E#5.

For ease of computation I arbitrarily grouped the set based upon the symbol in position 0, thus having 5 subgroups of 12 tuples each, e.g. ABC ABD ABE ACB ACD ACE ADB ADC ADE AEB AEC AED ... With this, the maximum number of checks can be calculated as $$ \binom{12}{1}\binom{12}{2}\binom{12}{3}\binom{12}{4}\binom{12}{5}=68,309,049,600 $$ For optimization, I recursively worked through the initial symbol sub groups starting with symbol A, and could abandon a recursion before reaching symbol E subgroup as soon as the remaining symbol count violated the constraint. With this optimization, when I ran this the code only had to perform 12,788,832 checks to find there were in total only 130 solutions that met the criteria. Since it is such a small set, below is the exhaustive list by row of the valid tuple subsets.

ACE BDE BEC CBE CDE CED DCE DEA DEB DEC EAD EBD ECD EDB EDC 
ACE BDE BEC CDE CEA CED DBE DCE DEB DEC EAD EBD ECD EDB EDC 
ACE BDE BEC CDE CEB CED DBE DCE DEA DEC EAD EBD ECD EDB EDC 
ACE BDE BEC CDE CEB CED DBE DCE DEB DEC EAD EBD ECD EDA EDC 
ACE BDE BED CAE CDE CED DCE DEA DEB DEC EBC EBD ECD EDB EDC 
ACE BDE BED CBE CDE CED DCE DEA DEB DEC EAC EBD ECD EDB EDC 
ACE BDE BED CBE CDE CED DCE DEA DEB DEC EAD EBC ECD EDB EDC 
ACE BDE BED CDE CEA CED DAE DCE DEB DEC EBC EBD ECD EDB EDC 
ACE BDE BED CDE CEA CED DBE DCE DEB DEC EAC EBD ECD EDB EDC 
ACE BDE BED CDE CEA CED DBE DCE DEB DEC EAD EBC ECD EDB EDC 
ACE BDE BED CDE CEB CED DAE DCE DEA DEC EBC EBD ECD EDB EDC 
ACE BDE BED CDE CEB CED DAE DCE DEB DEC EBC EBD ECD EDA EDC 
ACE BDE BED CDE CEB CED DBE DCE DEA DEC EAC EBD ECD EDB EDC 
ACE BDE BED CDE CEB CED DBE DCE DEA DEC EAD EBC ECD EDB EDC 
ACE BDE BED CDE CEB CED DBE DCE DEB DEC EAC EBD ECD EDA EDC 
ACE BDE BED CDE CEB CED DBE DCE DEB DEC EAD EBC ECD EDA EDC 
ACE BEC BED CAE CDE CED DBE DCE DEB DEC EBD ECD EDA EDB EDC 
ACE BEC BED CBE CDE CED DAE DCE DEB DEC EBD ECD EDA EDB EDC 
ACE BEC BED CBE CDE CED DBE DCE DEB DEC EAD ECD EDA EDB EDC 
ACE BEC BED CDE CEB CED DAE DBE DCE DEC EBD ECD EDA EDB EDC 
ADE BCE BDE CDE CEB CED DCE DEA DEB DEC EAD EBC EBD ECD EDC 
ADE BCE BEC CBE CDE CED DCE DEA DEB DEC EAD EBD ECD EDB EDC 
ADE BCE BEC CDE CEA CED DBE DCE DEB DEC EAD EBD ECD EDB EDC 
ADE BCE BEC CDE CEB CED DBE DCE DEA DEC EAD EBD ECD EDB EDC 
ADE BCE BEC CDE CEB CED DBE DCE DEB DEC EAD EBD ECD EDA EDC 
ADE BCE BED CAE CDE CED DCE DEA DEB DEC EBC EBD ECD EDB EDC 
ADE BCE BED CBE CDE CED DCE DEA DEB DEC EAC EBD ECD EDB EDC 
ADE BCE BED CBE CDE CED DCE DEA DEB DEC EAD EBC ECD EDB EDC 
ADE BCE BED CDE CEA CED DAE DCE DEB DEC EBC EBD ECD EDB EDC 
ADE BCE BED CDE CEA CED DBE DCE DEB DEC EAC EBD ECD EDB EDC 
ADE BCE BED CDE CEA CED DBE DCE DEB DEC EAD EBC ECD EDB EDC 
ADE BCE BED CDE CEB CED DAE DCE DEA DEC EBC EBD ECD EDB EDC 
ADE BCE BED CDE CEB CED DAE DCE DEB DEC EBC EBD ECD EDA EDC 
ADE BCE BED CDE CEB CED DBE DCE DEA DEC EAC EBD ECD EDB EDC 
ADE BCE BED CDE CEB CED DBE DCE DEA DEC EAD EBC ECD EDB EDC 
ADE BCE BED CDE CEB CED DBE DCE DEB DEC EAC EBD ECD EDA EDC 
ADE BCE BED CDE CEB CED DBE DCE DEB DEC EAD EBC ECD EDA EDC 
ADE BDE BEC CBE CDE CED DCE DEA DEB DEC EAD EBD ECB ECD EDC 
ADE BDE BEC CDE CEA CED DBE DCE DEB DEC EAD EBD ECB ECD EDC 
ADE BDE BEC CDE CEB CED DBE DCE DEA DEC EAD EBD ECB ECD EDC 
ADE BDE BEC CDE CEB CED DBE DCE DEB DEC EAD EBD ECA ECD EDC 
ADE BDE BED CAE CDE CED DCE DEA DEB DEC EBC EBD ECB ECD EDC 
ADE BDE BED CBE CDE CED DCE DEA DEB DEC EAC EBD ECB ECD EDC 
ADE BDE BED CBE CDE CED DCE DEA DEB DEC EAD EBC ECB ECD EDC 
ADE BDE BED CDE CEA CED DAE DCE DEB DEC EBC EBD ECB ECD EDC 
ADE BDE BED CDE CEA CED DBE DCE DEB DEC EAC EBD ECB ECD EDC 
ADE BDE BED CDE CEA CED DBE DCE DEB DEC EAD EBC ECB ECD EDC 
ADE BDE BED CDE CEB CED DAE DCE DEA DEC EBC EBD ECB ECD EDC 
ADE BDE BED CDE CEB CED DAE DCE DEB DEC EBC EBD ECA ECD EDC 
ADE BDE BED CDE CEB CED DBE DCE DEA DEC EAC EBD ECB ECD EDC 
ADE BDE BED CDE CEB CED DBE DCE DEA DEC EAD EBC ECB ECD EDC 
ADE BDE BED CDE CEB CED DBE DCE DEB DEC EAC EBD ECA ECD EDC 
ADE BDE BED CDE CEB CED DBE DCE DEB DEC EAD EBC ECA ECD EDC 
ADE BEC BED CAE CDE CED DBE DCE DEA DEC EBD ECB ECD EDB EDC 
ADE BEC BED CAE CDE CED DBE DCE DEB DEC EBD ECA ECD EDB EDC 
ADE BEC BED CAE CDE CED DBE DCE DEB DEC EBD ECB ECD EDA EDC 
ADE BEC BED CBE CDE CED DAE DCE DEA DEC EBD ECB ECD EDB EDC 
ADE BEC BED CBE CDE CED DAE DCE DEB DEC EBD ECA ECD EDB EDC 
ADE BEC BED CBE CDE CED DAE DCE DEB DEC EBD ECB ECD EDA EDC 
ADE BEC BED CBE CDE CED DBE DCE DEA DEC EAD ECB ECD EDB EDC 
ADE BEC BED CBE CDE CED DBE DCE DEB DEC EAD ECA ECD EDB EDC 
ADE BEC BED CBE CDE CED DBE DCE DEB DEC EAD ECB ECD EDA EDC 
ADE BEC BED CDE CEA CED DAE DBE DCE DEC EBD ECB ECD EDB EDC 
ADE BEC BED CDE CEB CED DAE DBE DCE DEC EBD ECA ECD EDB EDC 
ADE BEC BED CDE CEB CED DAE DBE DCE DEC EBD ECB ECD EDA EDC 
AEC BCE BDE CBE CDE CED DCE DEA DEB DEC EAD EBD ECD EDB EDC 
AEC BCE BDE CDE CEA CED DBE DCE DEB DEC EAD EBD ECD EDB EDC 
AEC BCE BDE CDE CEB CED DBE DCE DEA DEC EAD EBD ECD EDB EDC 
AEC BCE BDE CDE CEB CED DBE DCE DEB DEC EAD EBD ECD EDA EDC 
AEC BCE BED CAE CDE CED DBE DCE DEB DEC EBD ECD EDA EDB EDC 
AEC BCE BED CBE CDE CED DAE DCE DEB DEC EBD ECD EDA EDB EDC 
AEC BCE BED CBE CDE CED DBE DCE DEB DEC EAD ECD EDA EDB EDC 
AEC BCE BED CDE CEB CED DAE DBE DCE DEC EBD ECD EDA EDB EDC 
AEC BDE BED CAE CDE CED DBE DCE DEA DEC EBD ECB ECD EDB EDC 
AEC BDE BED CAE CDE CED DBE DCE DEB DEC EBD ECA ECD EDB EDC 
AEC BDE BED CAE CDE CED DBE DCE DEB DEC EBD ECB ECD EDA EDC 
AEC BDE BED CBE CDE CED DAE DCE DEA DEC EBD ECB ECD EDB EDC 
AEC BDE BED CBE CDE CED DAE DCE DEB DEC EBD ECA ECD EDB EDC 
AEC BDE BED CBE CDE CED DAE DCE DEB DEC EBD ECB ECD EDA EDC 
AEC BDE BED CBE CDE CED DBE DCE DEA DEC EAD ECB ECD EDB EDC 
AEC BDE BED CBE CDE CED DBE DCE DEB DEC EAD ECA ECD EDB EDC 
AEC BDE BED CBE CDE CED DBE DCE DEB DEC EAD ECB ECD EDA EDC 
AEC BDE BED CDE CEA CED DAE DBE DCE DEC EBD ECB ECD EDB EDC 
AEC BDE BED CDE CEB CED DAE DBE DCE DEC EBD ECA ECD EDB EDC 
AEC BDE BED CDE CEB CED DAE DBE DCE DEC EBD ECB ECD EDA EDC 
AED BCE BDE CAE CDE CED DCE DEA DEB DEC EBC EBD ECD EDB EDC 
AED BCE BDE CBE CDE CED DCE DEA DEB DEC EAC EBD ECD EDB EDC 
AED BCE BDE CBE CDE CED DCE DEA DEB DEC EAD EBC ECD EDB EDC 
AED BCE BDE CDE CEA CED DAE DCE DEB DEC EBC EBD ECD EDB EDC 
AED BCE BDE CDE CEA CED DBE DCE DEB DEC EAC EBD ECD EDB EDC 
AED BCE BDE CDE CEA CED DBE DCE DEB DEC EAD EBC ECD EDB EDC 
AED BCE BDE CDE CEB CED DAE DCE DEA DEC EBC EBD ECD EDB EDC 
AED BCE BDE CDE CEB CED DAE DCE DEB DEC EBC EBD ECD EDA EDC 
AED BCE BDE CDE CEB CED DBE DCE DEA DEC EAC EBD ECD EDB EDC 
AED BCE BDE CDE CEB CED DBE DCE DEA DEC EAD EBC ECD EDB EDC 
AED BCE BDE CDE CEB CED DBE DCE DEB DEC EAC EBD ECD EDA EDC 
AED BCE BDE CDE CEB CED DBE DCE DEB DEC EAD EBC ECD EDA EDC 
AED BCE BEC CAE CDE CED DBE DCE DEB DEC EBD ECD EDA EDB EDC 
AED BCE BEC CBE CDE CED DAE DCE DEB DEC EBD ECD EDA EDB EDC 
AED BCE BEC CBE CDE CED DBE DCE DEB DEC EAD ECD EDA EDB EDC 
AED BCE BEC CDE CEB CED DAE DBE DCE DEC EBD ECD EDA EDB EDC 
AED BCE BED CAE CDE CED DBE DCE DEB DEC EBC ECD EDA EDB EDC 
AED BCE BED CBE CDE CED DAE DCE DEB DEC EBC ECD EDA EDB EDC 
AED BCE BED CBE CDE CED DBE DCE DEB DEC EAC ECD EDA EDB EDC 
AED BCE BED CDE CEB CED DAE DBE DCE DEC EBC ECD EDA EDB EDC 
AED BDE BEC CAE CDE CED DBE DCE DEA DEC EBD ECB ECD EDB EDC 
AED BDE BEC CAE CDE CED DBE DCE DEB DEC EBD ECA ECD EDB EDC 
AED BDE BEC CAE CDE CED DBE DCE DEB DEC EBD ECB ECD EDA EDC 
AED BDE BEC CBE CDE CED DAE DCE DEA DEC EBD ECB ECD EDB EDC 
AED BDE BEC CBE CDE CED DAE DCE DEB DEC EBD ECA ECD EDB EDC 
AED BDE BEC CBE CDE CED DAE DCE DEB DEC EBD ECB ECD EDA EDC 
AED BDE BEC CBE CDE CED DBE DCE DEA DEC EAD ECB ECD EDB EDC 
AED BDE BEC CBE CDE CED DBE DCE DEB DEC EAD ECA ECD EDB EDC 
AED BDE BEC CBE CDE CED DBE DCE DEB DEC EAD ECB ECD EDA EDC 
AED BDE BEC CDE CEA CED DAE DBE DCE DEC EBD ECB ECD EDB EDC 
AED BDE BEC CDE CEB CED DAE DBE DCE DEC EBD ECA ECD EDB EDC 
AED BDE BEC CDE CEB CED DAE DBE DCE DEC EBD ECB ECD EDA EDC 
AED BDE BED CAE CDE CED DBE DCE DEA DEC EBC ECB ECD EDB EDC 
AED BDE BED CAE CDE CED DBE DCE DEB DEC EBC ECA ECD EDB EDC 
AED BDE BED CAE CDE CED DBE DCE DEB DEC EBC ECB ECD EDA EDC 
AED BDE BED CBE CDE CED DAE DCE DEA DEC EBC ECB ECD EDB EDC 
AED BDE BED CBE CDE CED DAE DCE DEB DEC EBC ECA ECD EDB EDC 
AED BDE BED CBE CDE CED DAE DCE DEB DEC EBC ECB ECD EDA EDC 
AED BDE BED CBE CDE CED DBE DCE DEA DEC EAC ECB ECD EDB EDC 
AED BDE BED CBE CDE CED DBE DCE DEB DEC EAC ECA ECD EDB EDC 
AED BDE BED CBE CDE CED DBE DCE DEB DEC EAC ECB ECD EDA EDC 
AED BDE BED CDE CEA CED DAE DBE DCE DEC EBC ECB ECD EDB EDC 
AED BDE BED CDE CEB CED DAE DBE DCE DEC EBC ECA ECD EDB EDC 
AED BDE BED CDE CEB CED DAE DBE DCE DEC EBC ECB ECD EDA EDC 
AED BEC BED CBE CDE CED DAE DBE DCE DEC ECB ECD EDA EDB EDC 

Counting the total tuples in this collection of the 130 sets of 15 tuples that met the criteria revealed some interesting insights. Below is this count, sorted by first position symbol and then by quantity found in the total collection of tuples:

ACE:          20
AEC:          20
ADE:          45
AED:          45
--------------------
BCE:          45
BEC:          45
BDE:          85
BED:          85
--------------------
CAE:          20
CEA:          20
CBE:          45
CEB:          45
CDE:         130
CED:         130
--------------------
DAE:          45
DEA:          45
DBE:          85
DEB:          85
DCE:         130
DEC:         130
--------------------
EAC:          20
ECA:          20
EAD:          45
EBC:          45
ECB:          45
EDA:          45
EBD:          85
EDB:          85
ECD:         130
EDC:         130

The first insight that jumped out to me is clearly there is a reflexive pair pattern. This makes sense, since effectively one could swap all the symbols in position 1 and 2 to yield the mirror result.

The next insight that surprised me is that subgroups C, D, and E shows tuples pairs that must appear in a valid solution, e.g. CDE/CED, DCE/DEC, ECD/EDC, and some tuple pairs in every sub group that never appear.

To see how the pattern extends, I repeated this process with the same initial collection of 5 permute 3, changing the criteria to A#2 B#3 C#4 D#5 E#6. This had a possibility of requiring 5.2E12 comparisons, though the optimizations reduced this to only ~1E9 tests required to find 50,202 valid solutions. The tuple count in the valid solutions, below, shows the same reflective pattern, as well as perhaps some other insights.

ABC:         561
ACB:         561
ABD:       1,144
ADB:       1,144
ABE:       3,131
AEB:       3,131
ACD:       5,140
ADC:       5,140
ACE:      13,792
AEC:      13,792
ADE:      26,434
AED:      26,434
--------------------
BAC:         561
BCA:         561
BAD:       1,144
BDA:       1,144
BAE:       3,131
BEA:       3,131
BCD:       9,889
BDC:       9,889
BCE:      24,351
BEC:      24,351
BDE:      36,227
BED:      36,227
--------------------
CAB:         561
CBA:         561
CAD:       5,140
CDA:       5,140
CBD:       9,889
CDB:       9,889
CAE:      13,792
CEA:      13,792
CBE:      24,351
CEB:      24,351
CDE:      46,671
CED:      46,671
--------------------
DAB:       1,144
DBA:       1,144
DAC:       5,140
DCA:       5,140
DBC:       9,889
DCB:       9,889
DAE:      26,434
DEA:      26,434
DBE:      36,227
DEB:      36,227
DCE:      46,671
DEC:      46,671
--------------------
EAB:       3,131
EBA:       3,131
EAC:      13,792
ECA:      13,792
EBC:      24,351
ECB:      24,351
EAD:      26,434
EDA:      26,434
EBD:      36,227
EDB:      36,227
ECD:      46,671
EDC:      46,671

Research is ongoing to see if I can derive a predictive formula, as well as ongoing optimizations to the exhaustive checks (taking advantage of the mirror reflection at least).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.