Generate permutations from set of numbers

[Jsel]

hello, I am trying to write a recursive function to generate all permutations from a given set of numbers. For example, say the numbers 4, 6, and 8 are given. The function should generate 6 sets of numbers like this:
468
648
684
486
846
864

The recursive function should generate all permutations for the first n-1 numbers. Then the nth number can be added into every position of the n-1 permutations to generate all permutations. For example, say our function is given the numbers 1,2 and 3. the first call to the recursive function will attempt to find permutations for 1 and 2. The second call will find permutations for the number 1. Since this can only be 1, the current recursive call is exited (This is the base case) and the recursive call above it inserts 2 like this:
12
21.

Once this recursive call exits, the one above it inserts 3 like this:
312
132
123
321
231
213

This is the general idea of how to design this recursive function. But I just don't know how to implement the numbers. The book recommends either linked lists of nodes, linked lists of vectors, arrays, ect. I would be very thankful if anyone could give me a little more guidance.

[onur]

First you should try to get an algorithm.
Then try to implement it.

So whether you use linked list of nodes or list of vectors is secondary.

So what's your suggested algorithm (in plain text or pseudo code)?

[tition]

std::vector is one of the simplest ways I can think of to implement the numbers.

#include<iostream>
#include<vector>

int main()
{ std::vector<int> theVector;
  theVector.push_back(4);
  theVector.push_back(6);
  theVector.push_back(8);
  for (unsigned int i=0; i<theVector.size(); i++)
    std::cout << theVector[i] << ",";
  int x;
  std::cin >> x;
}

[rapidcoder]

This is one of those algorithms that are terribly hard to get right (and efficient) in imperative languages, yet it is a piece of cake in functional paradigm - like 3-4 short lines of code giving overall computational and memory complexity of O(n!).

The algorithm in pseudocode:

function permutations(S):
  if S is empty set then return { empty sequence }
  else return { (e) + p:  e in S, p in permutations(S \ e) }

where {} denotes a set, () denotes a sequence and + denotes joining two sequences

In C++, neither storing permutations in a std::vector or a std::list will give you O(n!) complexity, the best you can get without rolling your own container is O(n * n!)

[tition]

@rapidcoder
Ahem, is

void generateAllPermutations(std::vector<int>& toBePermuted, unsigned int nextIndex)
{ if (nextIndex==toBePermuted.size())  { printVector(toBePermuted); return;}
  for (unsigned int i=nextIndex; i<toBePermuted.size(); i++)
  { swap(toBePermuted[i], toBePermuted[nextIndex]);
    generateAllPermutations(toBePermuted, nextIndex+1);
    swap(toBePermuted[i], toBePermuted[nextIndex]);
  }
}

so complicated?

[quirkyusername]

@tition
my god that's some horribly formatted code, did you do that just to make it look shorter so that your snyde comment might seem more valid?

[tition]

Actually that is how I format my code. I like it ... it's called "Horstmann style"

http://en.wikipedia.org/wiki/Indent_style

[rapidcoder]

@titon:
It is not complicated if you do it in O(n * n!), like you did, istead of O(n!).
And yours is not even a function generating permutations - and the original task was:

The function should generate 6 sets of numbers

Permuting in place is easy. Generating (and memoizing) all possible permutations efficiently is not.

[tition]

Alright, I read carefully what you wrote.

At any rate, if you want your result to be the printout of all permutations, your memory use will be proportional to n*n! O(n*n!). So, you need to specify what final answer you want. What I wrote is proportional to n*n! O(n*n!) computational complexity and proportional to n O(n) memory footprint (as I don't store the permutations).

If you store the permutations, however, you must have a O(n*n!) computational and memory footprint proportional to n*n!.

[Edit:] As far as whether the simple algorithm I posted generates all permutations: here is the whole program, formatted in Horstmann style.

#include<iostream>
#include<vector>

void swap(int& a, int& b)
{ int x=a;
  a=b;
  b=x;
}

void printVector(std::vector<int>& theVector)
{ for (unsigned int i=0; i<theVector.size(); i++)
    std::cout << theVector[i] << ",";
  std::cout << "\n";
}

void generateAllPermutations(std::vector<int>& toBePermuted, unsigned int nextIndex)
{ if (nextIndex==toBePermuted.size())
  { printVector(toBePermuted);
    return;
  }
  for (unsigned int i=nextIndex; i<toBePermuted.size(); i++)
  { swap(toBePermuted[i], toBePermuted[nextIndex]);
    generateAllPermutations(toBePermuted, nextIndex+1);
    swap(toBePermuted[i], toBePermuted[nextIndex]);
  }
}

void generateAllPermutations(std::vector<int>& toBePermuted)
{ generateAllPermutations(toBePermuted, 0);
}

int main()
{ std::vector<int> theVector;

  theVector.push_back(4);
  theVector.push_back(3);
  theVector.push_back(2);
  theVector.push_back(1);
  theVector.push_back(6);
  theVector.push_back(8);
  generateAllPermutations(theVector);
  int x;
  std::cin >> x;
}

[rapidcoder]

If you store the permutations, however, you must have a O(n*n!) computational and memory footprint proportional to n*n!.

No, it is possible to store all of them in O(n!), using single-linked lists, sharing most of their elements. But you have to roll your own list for doing that, STL list doesn't allow for sharing list elements.
Look:

1, 2, 3, 4
      4, 3
   3, 4, 2
      2, 4
   4, 2, 3
      3, 2
2, 1, 3, 4   
      4, 3
   3, 1, 4
      4, 1
   4, 1, 3
      3, 1
...

It is k * n! list elements required to keep all the permutations, where k <= 3 for all n >= 4 (heads are on the right, tails are on the left).

Exactly it is: n! (1 + sum_{i = 1}^n (1 / i!))

[Jsel]

Thanks tition that was very helpful.

[tition]

@rapidcoder:

I see your point, however, what you say calls for a discussion.

In order to "unfold" one of your permutations, you need approximately n operations. However, you can "unfold" any permutation without storing anything to begin with (Fisher–Yates shuffle according to wikipedia, although it's pretty easy to come up with it yourself).

The idea is:

you start with a sequence of numbers

d[0], d[2], .... ,d[n-1]
such that d[i]<=n-i

Now all you do to generate a permutation from these numbers is to call the function generateAllPermutations, however you substitute the line

for (unsigned int i=nextIndex; i<toBePermuted.size(); i++)

with
int i=d[nextIndex];.

Something more, two permutations are equal if and only if their presentations with array d[]
are identical.

So my argument is: with a linked list you don't really store all permutations in an array with constant access time. What you do, is you store the permutations in a semi-computed-form (i.e. linked list), postponing the final computation to the time it's accessed.

This is good, however, why do you need to do that at all, if we have means of writing down and "unfolding" an arbitrary permutation in O(n) time, without generating any of the remaining permutations?

[rapidcoder]

I'm not sure if I properly understood - Are you claiming you can unfold any arbitrary permutation, given only the:
1. original sequence
2. index of the permutation to get

in O(n)?

So that you could write a code like this:

for (int i = 0; i < n!; ++i)
  cout << permutation(collection, i);

and make it print all the permutations?

Unfolding a random permutation is easy, unfolding the next permutation, given the previous one, is easy too, but unfolding the i-th permutation? (the order can be easily defined, so that the i-th permutation is also well defined)

So my argument is: with a linked list you don't really store all permutations in an array with constant access time.

Actually I can store heads of the lists in an array, so that the access time to the i-th iteration is constant. How is vector of vectors better?

vector of lists approach:
- access time to the i-th permutation: O(1),
- reading a permutation fully: O(n),
- storage and preparation time required: < 3 * n! for n > 4

vector of vectors approach:
- access time to the i-th permutation: O(1),
- reading a permutation fully: O(n),
- storage and preparation time required: n * n!

[tition]

I'm not sure if I properly understood - Are you claiming you can unfold any arbitrary permutation, given only the:
1. original sequence
2. index of the permutation to get

in O(n)?

So that you could write a code like this:
1
2
for (int i = 0; i < n!; ++i)
cout << permutation(collection, i);


and make it print all the permutations?

Yes, that is exactly what I meant. Here is the code. The cycle you are talking about is at the bottom of int main(). And it looks like:

for (int i=0; i<NumPermutations; i++)
{ base.getFactorialNumberSystem(i, shorterNotation);//this operation is O(n)
theVector=theInitialVector;//so is this one
generateOnePermutationFromIndices(theVector, shorterNotation);//and so is this one
printVector(theVector);
}

I didn't do an excellent job, so the O(n) in question is has some quite a large constant, but anyways, the idea holds.

[Edit]One more note. The O(n) is only if we are to assume that integer division is O(1) (which practically is the case if you take into account hardware optimization). However, if we account the fact that division is a slow procedure, then wikipedia claims that the factorial notation thing needs approximately n^2/4 operations (but that again is practically constant).

Here is the entire code:

#include<iostream>
#include<vector>

void swap(int& a, int& b)
{ int x=a;
  a=b;
  b=x;
}

void printVector(std::vector<int>& theVector)
{ for (unsigned int i=0; i<theVector.size(); i++)
    std::cout << theVector[i] << ",";
  std::cout << "\n";
}

void generateOnePermutationFromIndices(std::vector<int>& toBePermuted, std::vector<int>& d)
{ for (unsigned int i=0; i< toBePermuted.size(); i++)
    swap(toBePermuted[i], toBePermuted[i+d[i]]);
}

int getFactorial(int n)
{ int result=1;
  for (int i=0; i<n; i++)
    result*=i+1;
  return result;
}

class FactorialNotation
{
  public:
  std::vector<int> FactorialVector;
  int FactorialBase;
  int FactorialBaseMinus1;
  void SetFactorialBase(int n)
  { this->FactorialBase=n;
    this->FactorialBaseMinus1=n-1;
    this->FactorialVector.resize(n);
    for (int i=0; i<n; i++)
      this->FactorialVector[i]=getFactorial(i+1);
  }
  bool getFactorialNumberSystem(int inputNumber, std::vector<int>& output)
  { output.resize(this->FactorialBase);
    for (int i=this->FactorialBaseMinus1-1; i>=0; i--)
    { int currentBase=this->FactorialVector[i];
      int x=inputNumber/currentBase;
      if (x>i+1)
        return false;
      output[this->FactorialBaseMinus1-1- i]=x;
      inputNumber=inputNumber% this->FactorialVector[i];
    }
    output[this->FactorialBaseMinus1]=0;
    return true;
  }
  FactorialNotation(){this->FactorialBase=0;}
};

int main()
{ std::vector<int> theInitialVector, theVector, shorterNotation;
  FactorialNotation base;
  theInitialVector.push_back(1);
  theInitialVector.push_back(2);
  theInitialVector.push_back(3);
  theInitialVector.push_back(4);
  theInitialVector.push_back(5);
  theInitialVector.push_back(6);
  base.SetFactorialBase(theInitialVector.size());
  theVector=theInitialVector;
  int x;
  std::cout << "\nAnd now enter the index of any permutation you want to have in O(n) if division is constant time operation: ";
  std::cin >> x;
  std::cout << "The permutation index " << x <<  " of ";
  printVector(theInitialVector);
  if (base.getFactorialNumberSystem(x, shorterNotation))
  { generateOnePermutationFromIndices(theVector, shorterNotation);
     std::cout << "\n is: ";
    printVector(theVector);
  } else
    std::cout << "\n is bad as your index is out of bounds";

  std::cin >> x;
  std::cout << "\nAnd now I enumerate for you all permutations using a for cycle.\n";
  int NumPermutations=getFactorial(theVector.size());
  for (int i=0; i<NumPermutations; i++)
  { base.getFactorialNumberSystem(i, shorterNotation);
    theVector=theInitialVector;
    generateOnePermutationFromIndices(theVector, shorterNotation);
//    printVector(shorterNotation); std::cout << "corresponds to: ";
    printVector(theVector);
  }
  std::cin >> x;
}

[Jsel]

tition, would you mind explaining to me how you came up with the generateAllPermutations function algorithm? I am pretty new to programming and I can't easily understand the process of the algorithm unless I trace each recursive call in my head or use the debugger. So basically I'm asking if this comes with experience or is there some trick to better understanding the function.

[tition]

Jsel,
Honestly I don't remember: I believe I have the algorithm from my high school teacher, but I will soon be 30, so my high school memories are extremely unreliable.

I cannot recommend you any good book on the subject, however, the Wikipedia article
http://en.wikipedia.org/wiki/Permutation
is excellent. The same article has a reference to the book:
D. E. Knuth, The Art of Computer Programming

I haven't read it, but since Knuth is a super famous guy, I presume it should be good.

[helios]

D. E. Knuth, The Art of Computer Programming

Oh, man.
You're a good candidate to understanding more than half that book. It's got math up the derriere.

I've been experimenting a bit, and I think there's some relationship between the binary representation of the permutation's index and how the initial state has to be modified to reach the permutation. Specifically, that the state of a given bit determines whether some rotation (in the sense of abc -> bca) will be applied to the elements in a given range. For example, if bit 0 is on, rotate elements 0-3 to the right by 1; if bit 1 is on, rotate elements 2-4 to the left by 2; etc. with each rotation being applied to the output of the last one.

[rapidcoder]

Ok, actually that was really nice, but it also confirms, that getting this to work in O(n!) is nontrivial, just as I have said at the beginning.