Permutations are not all that difficult, but doing so with an extra rule has me stumped. Here is the problem...
I want to do every permutation for the string ABCDEFGHIJKLMNOPQR, but I want the output to show only certain permutations.
The A, D, G, J, M, and P can only be in the 1st, 4th, 7th, 10th, 13th, or 16th position (i.e., any of the letters mentioned can be in the 1st position; any of what's left can be in the 4th position, etc.).
Likewise, the B, E, H, K, N, and Q can only be in the 2nd, 5th, 8th, 11th, 14th, or 17th position... leaving us with C, F, I, L, O, and R in the 3rd, 6th, 9th, 12th, 15th, or 18th position.
How can I do the permutation for the string ABCDEFGHIJKLMNOPQR with the extra rule mentioned above?
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
Since you have said that you want to generate all possible permutations (even ones that don't match the rules), for each permutation, simply test against the rules you specified:
... well you get the idea - a large conditional -requires 12 lines like the ones above to encode the whole rule.
Now there are several ways to be smarter. You could use the mathematial relationships between the letters and their
positions.
bool valid = true ;
for( int i = 0; valid && i < 16; i++ )
{
if( ((perm[i] - 'A') % 3) != (i % 3) )
{
valid = false ;
}
}
if( valid )
{
outputPermutation( perm ) ;
}
Finally, if you only ever need the permutations that match the rule (which is contrary to your original statement, but people do not always say what they mean in my experience), then a more efficient method is to generate permutations for the three separate groups:
1) ADGJMP
2) BEHKNQ
3) CFILOR
such that for every permutation of (1) you generate every permutation of (2), and for every permutation of (2) you generate all permutations of (3). Then for each permutation of (3) you output the current permutation of (1)(2) and (3) appropriately interleaved (one from each group in turn). This way you generate far fewer permutations by only generating the ones that meet the constraints in the first instance.
Clifford
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
Permutations are not all that difficult, but doing so with an extra rule has me stumped. Here is the problem...
I want to do every permutation for the string ABCDEFGHIJKLMNOPQR, but I want the output to show only certain permutations.
The A, D, G, J, M, and P can only be in the 1st, 4th, 7th, 10th, 13th, or 16th position (i.e., any of the letters mentioned can be in the 1st position; any of what's left can be in the 4th position, etc.).
Likewise, the B, E, H, K, N, and Q can only be in the 2nd, 5th, 8th, 11th, 14th, or 17th position... leaving us with C, F, I, L, O, and R in the 3rd, 6th, 9th, 12th, 15th, or 18th position.
How can I do the permutation for the string ABCDEFGHIJKLMNOPQR with the extra rule mentioned above?
Well there are naive ways and smart ways.
Since you have said that you want to generate all possible permutations (even ones that don't match the rules), for each permutation, simply test against the rules you specified:
if(
(perm[0] == 'A' || perm[0] == 'D' || perm[0] == 'G' || perm[0] == 'J' || perm[0] == 'M') &&
(perm[4] == 'A' || perm[4] == 'D' || perm[4] == 'G' || perm[4] == 'J' || perm[4] == 'M') &&
(perm[7] == 'A' || perm[7] == 'D' || perm[7] == 'G' || perm[7] == 'J' || perm[7] == 'M') &&
(perm[10] == 'A' || perm[10] == 'D' || perm[10] == 'G' || perm[10] == 'J' || perm[10] == 'M') &&
(perm[13] == 'A' || perm[13] == 'D' || perm[13] == 'G' || perm[13] == 'J' || perm[13] == 'M') &&
(perm[16] == 'A' || perm[16] == 'D' || perm[16] == 'G' || perm[16] == 'J' || perm[16] == 'M') &&
(perm[1] == 'B' || perm[1] == 'E' || perm[1] == 'H' || perm[1] == 'K' || perm[0] == 'N') &&
... well you get the idea - a large conditional -requires 12 lines like the ones above to encode the whole rule.
Now there are several ways to be smarter. You could use the mathematial relationships between the letters and their
positions.
bool valid = true ;
for( int i = 0; valid && i < 16; i++ )
{
if( ((perm[i] - 'A') % 3) != (i % 3) )
{
valid = false ;
}
}
if( valid )
{
outputPermutation( perm ) ;
}
Finally, if you only ever need the permutations that match the rule (which is contrary to your original statement, but people do not always say what they mean in my experience), then a more efficient method is to generate permutations for the three separate groups:
1) ADGJMP
2) BEHKNQ
3) CFILOR
such that for every permutation of (1) you generate every permutation of (2), and for every permutation of (2) you generate all permutations of (3). Then for each permutation of (3) you output the current permutation of (1)(2) and (3) appropriately interleaved (one from each group in turn). This way you generate far fewer permutations by only generating the ones that meet the constraints in the first instance.
Clifford