Prove why this algorithm to compute all list permutations works

Question

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 i^th value with the N^th for all existing subsets generated in previous rounds. In the same round, I'll generate more subsets by swapping the i^th 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?

Answer 1

Basically, the Swap command multiplies by the transposition $(i\ j)$ (I'm used to think of it as left-multiplication, but every other person would think of it as right-multiplication, so just pick what's comfortable to you and stick with it). So what we're doing is first including all $(1\ j)$'s, then adding all $(1\ j)(2\ k)$, and so on. In particular, pick a permutation and represent it as the product of disjoint cycles, and it becomes clear how it is generated. For example, $(1\ 3\ 4)(2\ 5)\in S_5$ is generated as follows: $$(1\ 3)\to(1\ 3)(2\ 5)\to(1\ 3)(2\ 5)(3\ 4) = (1\ 3)(3\ 4)(2\ 5) = (1\ 3\ 4)(2\ 5).$$