Note: this is not homework or for a class, as I'm no longer in school.
Let's say I have a list of characters {1,2,...,N} and I want to generate all permutations.
For example, if I had {1,2,3} the permutations would be {1,2,3} {1,3,2} {2,1,3} {2,3,1} {3,1,2} {3,2,1}
Of course we could come up with a number of algorithms do solve this that work for various reasons, but I'm interested in the combinatorial theory behind the following algorithm.
The Algorithm
In brief: I'll generate a round of subsets by swapping the ith value with the Nth for all existing subsets generated in previous rounds. In the same round, I'll generate more subsets by swapping the ith value with the (N-1)th, and then with the (N-2)th etc. until (N-j) = i
Some definitions:
Let List be a container of characters.
List(List) is a container of containers of characters
Containers are 1 indexed,
i.e., List[1] gives the first element, and List[N] gives the last one
In our example, the original list {1,2,...,N} is a List, and the set of permutations is a List(List)
In pseudocode:
L = {1,2,...,N}
Permutations = {}
For(i=1 to N){
List(List) thisRound
For each permutation p in Permutations{
For(j=N; j > i; --j)
{
List t = p
Swap(t[i],t[j])
thisRound.Insert(t)
}
}
Permutations.AddAll(thisRound) //add all the permutations in thisRound
}
Full C++ Implementation
- Assumes that we're generating permutations of strings
- Simple I/O: Asks for a string of characters
- Outputs each permutation as well as the total count
#include <iostream> #include <string> #include <vector> using namespace std; void GeneratePermutations(vector<string>& _permutations); int main(){ string input; cout << "Input a string: " << endl; cin >> input; vector<string> permutations; permutations.push_back(input); cout << "Generating all permutations..." << endl; GeneratePermutations(permutations); cout << "Permutations: " << endl; size_t count = 0; for (vector<string>::iterator vecIter = permutations.begin(); vecIter != permutations.end(); ++vecIter){ cout << *vecIter << endl; ++count; } cout << "Total: " << count << endl; } void GeneratePermutations(vector<string>& permutations) { size_t i = 0; size_t length = permutations.front().size(); for(size_t i=0;i<length;++i){ vector<string> tmp; for(vector<string>::iterator strIter = permutations.begin(); strIter != permutations.end(); ++strIter){ for(size_t j=(*strIter).size()-1; j > i; --j){ string nextStr = *strIter; std::swap(nextStr[i],nextStr[j]); tmp.push_back(nextStr); } } permutations.insert(permutations.end(), tmp.begin(), tmp.end()); } }
Example run
Input a string:
1234
Generating all permutations...
Permutations:
1234
4231
3214
2134
1432
1324
4132
4321
3412
3124
2431
2314
1243
4213
3241
2143
1423
1342
4123
4312
3421
3142
2413
2341
Total: 24
My Question
I have only a moderate intuition about why this method works. First we generate all permutations of the first column, which gets reused over and over (4321,4321), and then we do something similar for the second column, but it excludes the values we generated the first time around.
I just can't come up with a real pattern/explanation for WHY it works. I've looked (briefly) online for similar implementations to generate string permutations, and I haven't found anything like this.
Can you determine why it works?