Generating all possible permutations of N items

One of the simplest methods to generate all possible permutations of N items is Heap’s algorithm. This algorithm was proposed by B. R. Heap in 1963, and remains popular until today due to its simplicity. I came across the need to generate permutations for a quick tool a while ago and this algorithm works really well. So I decided to share it here.

As simple illustration, all possible permutations of 123 are 213, 312, 132, 231 and 321 (there are 6 permutations including 123 itself). All possible permutations of 1234 are 2134, 3124, 1324, 2314, 3214, 4231, 2431, 3421, 4321, 2341, 3241, 4132, 1432, 3412, 4312, 1342, 3142, 4123, 1423, 2413, 4213, 1243 and 2143 (there are 24 permutations including 1234 itself. In general, the number of possible permutations of N items from a set of N can be calculated as N! (N factorial = 1 * 2 * 3 * … * N). If the set is larger, then the number of possible permutations of K items from a set of N can be calculated as N! / (N-K)!

 

[toggle title=”Main Algorithm”]

procedure GeneratePermutation(N: Integer);
var i : Integer;
begin
  if N=1 then
    arrPermutation.Append(sPermutationBaseString)
  else begin
    for i := 1 to N do begin
      GeneratePermutation(N-1);
      if (N mod 2)=1 then
        Swap(sPermutationBaseString[1],sPermutationBaseString[N])
      else
        Swap(sPermutationBaseString[i],sPermutationBaseString[N]);
    end;
  end;
end;

[/toggle]

 

[toggle title=”Caller”]

var arrPermutation : TStrings;
    sPermutationBaseString : String;
    N, i : Integer;
begin
  arrPermutation.Clear;
  sPermutationBaseString := '';
  N := StrToInt(editN.Text);
  for i := 1 to N do
    sPermutationBaseString := sPermutationBaseString + IntToStr(i);
  GeneratePermutation(N);
end;

[/toggle]

 

I wrote this code using Embarcadero Delphi XE6. The algorithm should be very straightforward and it should be easy to rewrite it in any programming language of your choice. Admittedly, it does not really follow good practices in object oriented programming as I use global variable in a lazy way. Well, it was a quick tool and I simply needed to get it done so there was not much time. The code worked perfectly and I hope it would be useful for you.