1
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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).$$

$\endgroup$
  • $\begingroup$ +1 for giving an example... $\endgroup$ – draks ... Oct 19 '13 at 21:20
  • $\begingroup$ Forgive my naivete, but what do you mean by (1 j)'s? $\endgroup$ – AndyG Oct 19 '13 at 22:45
  • 1
    $\begingroup$ @AndyG the transposition $(i\ j)$ is the permutation which maps $i\mapsto j, j\mapsto i$ and leaves every other point fixed. It's well-known that every cycle (and therefore every permutation) can be represented as a product of transpositions. $\endgroup$ – Jonathan Y. Oct 19 '13 at 22:49
  • $\begingroup$ @JonathanY. Thanks. I don't understand a lot about group theory, but I think I get it. $\endgroup$ – AndyG Oct 19 '13 at 23:54

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.