A template c++ class for generating all permutations of a set of 'N' items. Here's an example showing how the class is typically used:
template <typename T>
void show(Permute<T> &p)
{
p.reset();
while(true)
{
const vector<T> *current = p.getNext();
if(!current)
break;
cout << Permute<T>::toString(current) << endl;
}
}
static int main()
{
Permute<char> pLetters("abcd");
show(pLetters);
int numbers[] = { 1, 2, 3, 4 };
Permute<int> pNumbers(numbers, 4);
show(pNumbers);
}
The output from the above would look like ...
a b c d
b a c d
c a b d
a c b d
b c a d
c b a d
d a b c
a d b c
b d a c
...
1 2 3 4
2 1 3 4
3 1 2 4
1 3 2 4
2 3 1 4
...
The interesting thing about this class is that way the permutations are generated. The algorithm used is one I created myself and it works as follows:
Suppose we have a list containing the letters
a, b, c, d
Now, here are the first 10 permutations ...
a b c d 0
a b d c 1
a c d b 2
a c b d 3
a d b c 4
a d c b 5
b c d a 6
b c a d 7
b d a c 8
b d c a 9
...
Notice that each permutation is produced by reversing
a part of the previous permutation, for example:
a b c d 0
a b d c 1
Here we're reversing the sub string "c d" to get from
permutation 0 to permutation 1. Similarly ...
a c b d 3
a d b c 4
a d c b 5
b c d a 6
Here, to get from 3 to 4 we're reversing the string "c b d", to
get from 5 to 6 we're reversing "a d c b". Each time we're
reversing the last n characters of the string, the pattern
looks like this ...
Last 'n' characters Permutation
------------------- -----------
N/A 0
2 1
3 2
2 3
3 4
2 5
4 6
2 7
3 8
2 9
...
Now, for each permutation number { 1, ..., 23 } we find the
largest factorial value that divides evenly into the
permutation number. The factorial values less than 23 are:
1! -> 1
2! -> 2
3! -> 6
permutation number biggest divisor reverse last n chars
------------------ --------------- --------------------
4 2! 3
5 1! 2
6 3! 4
 Source Code
Return to Main |
