Generating Permutations

Many solutions on the DelphiForFun website rely on a "brute-force" approach whereby all permutations of a list are generated and tested to find out if they match the required criteria. The favoured permutation-generating algorithm of Gary Darby, creator of the website, is SEPA. We have used some of Gary's SEPA code in this console program that explains the generation of each combination from its predecessor. A copy of the output follows the code.

program Permutations;
  {Using some of Gary Darby's code at
   http://delphiforfun.org/programs/Source_Listings/Permutes1Source.html which was
   ported from Jeffrey A. Johnson's C code of SEPA now available at
   http://www.quickperm.org/soda_submit.php
   Gary's copyright statement follows.
   Copyright 2002, Gary Darby, Intellitech Systems Inc., www.DelphiForFun.org

   This program may be used or modified for any non-commercial purpose
   so long as this original notice remains in place.
   All other rights are reserved

  }
var
  x: array[0..3] of byte;
  MyChar, PermutationNum: integer;

function nextpermute(var a: array of byte): boolean;
var
  i, j, key, temp, rightmost: integer;
begin
  {1. Find Key, the leftmost byte of rightmost in-sequence pair
      If none found, we are done

      Characters to the right of key are the "tail"
      Example 1432
      Step 1:  check pair 3,2 - not in sequence
               check pair 4,3 - not in sequence
               check pair 1,4 - in sequence ==> key is a[0]=1, tail is 432
  }
  rightmost := high(a);
  i := rightmost - 1; {Start at right end -1}
  while (i >= 0) and (a[i] >= a[i+1]) do
    dec(i); {Find in-sequence pair}
  if i >= 0 then  {Found it, so there is another permutation}
    begin
      result := true;
      key := a[i];
      write('  Key = ', chr(key), ' (leftmost byte of rightmost in-sequence pair)'#13#10);
      // 2A. Find rightmost in tail that is > key
      j := rightmost;
      while (j > i) and (a[j] < a[i]) do
        dec(j);
      // 2B. and swap them
      writeln('Swapping key with ', chr(a[j]), ' (rightmost byte in tail that is greater than key)');
      a[i] := a[j];
      a[j] := key;
      {Example: 1432  1 = key  432 = tail
       Step 2:  check 1 vs 2,  2 > 1 so swap them producing 2431}

      {3. Sort tail characters in ascending order
          By definition, the tail is in descending order now,
          so we can do a swap sort by exchanging first with last,
          second with next-to-last, etc.
          Example - 2431  431 = tail
          Step 3: compare 4 vs 1 - 4 is greater so swap producing 2134
          tail sort is done.
          final array for this permutation = 2134
       }

      inc(i); {point i to tail start, j to tail end}
      j := rightmost;
      while j > i do
        begin
          if a[i] > a[j] then
            begin {swap}
              // output interim sequence before sort of tail
              write('Interim sequence with tail starting at ', chr(x[i]), ': ');
              for MyChar := 0 to 3 do
                write(chr(x[MyChar]));
              writeln;
              temp := a[i];
              a[i] := a[j];
              a[j] := temp;
              writeln('Sorting tail into ascending order by exchanging first with last, ');
              writeln('second with next-to-last, etc. as necessary');
            end;
          inc(i);
          dec(j);
        end;
    end
  else
    result := false; {else please don't call me any more!}
end;

begin
  x[0] := ord('1');
  x[1] := ord('2');
  x[2] := ord('3');
  x[3] := ord('4');
  write('Initial permutation: ');
  PermutationNum := 1;
  for MyChar := 0 to 3 do
    write(chr(x[MyChar]));
  while nextpermute(x) do
    begin
      inc(PermutationNum);
      write(#13#10, 'Permutation no ', PermutationNum, ': ');
      for MyChar:= 0 to 3 do
        write(chr(x[MyChar]));
    end;
  writeln;
  readln;
end.
    

Output:

Initial permutation: 1234  Key = 3 (leftmost byte of rightmost in-sequence pair)
Swapping key with 4 (rightmost byte in tail that is greater than key)

Permutation no 2: 1243  Key = 2 (leftmost byte of rightmost in-sequence pair)
Swapping key with 3 (rightmost byte in tail that is greater than key)
Interim sequence with tail starting at 4: 1342
Sorting tail into ascending order by exchanging first with last,
second with next-to-last, etc. as necessary

Permutation no 3: 1324  Key = 2 (leftmost byte of rightmost in-sequence pair)
Swapping key with 4 (rightmost byte in tail that is greater than key)

Permutation no 4: 1342  Key = 3 (leftmost byte of rightmost in-sequence pair)
Swapping key with 4 (rightmost byte in tail that is greater than key)
Interim sequence with tail starting at 3: 1432
Sorting tail into ascending order by exchanging first with last,
second with next-to-last, etc. as necessary

Permutation no 5: 1423  Key = 2 (leftmost byte of rightmost in-sequence pair)
Swapping key with 3 (rightmost byte in tail that is greater than key)

Permutation no 6: 1432  Key = 1 (leftmost byte of rightmost in-sequence pair)
Swapping key with 2 (rightmost byte in tail that is greater than key)
Interim sequence with tail starting at 4: 2431
Sorting tail into ascending order by exchanging first with last,
second with next-to-last, etc. as necessary

Permutation no 7: 2134  Key = 3 (leftmost byte of rightmost in-sequence pair)
Swapping key with 4 (rightmost byte in tail that is greater than key)

Permutation no 8: 2143  Key = 1 (leftmost byte of rightmost in-sequence pair)
Swapping key with 3 (rightmost byte in tail that is greater than key)
Interim sequence with tail starting at 4: 2341
Sorting tail into ascending order by exchanging first with last,
second with next-to-last, etc. as necessary

Permutation no 9: 2314  Key = 1 (leftmost byte of rightmost in-sequence pair)
Swapping key with 4 (rightmost byte in tail that is greater than key)

Permutation no 10: 2341  Key = 3 (leftmost byte of rightmost in-sequence pair)
Swapping key with 4 (rightmost byte in tail that is greater than key)
Interim sequence with tail starting at 3: 2431
Sorting tail into ascending order by exchanging first with last,
second with next-to-last, etc. as necessary

Permutation no 11: 2413  Key = 1 (leftmost byte of rightmost in-sequence pair)
Swapping key with 3 (rightmost byte in tail that is greater than key)

Permutation no 12: 2431  Key = 2 (leftmost byte of rightmost in-sequence pair)
Swapping key with 3 (rightmost byte in tail that is greater than key)
Interim sequence with tail starting at 4: 3421
Sorting tail into ascending order by exchanging first with last,
second with next-to-last, etc. as necessary

Permutation no 13: 3124  Key = 2 (leftmost byte of rightmost in-sequence pair)
Swapping key with 4 (rightmost byte in tail that is greater than key)

Permutation no 14: 3142  Key = 1 (leftmost byte of rightmost in-sequence pair)
Swapping key with 2 (rightmost byte in tail that is greater than key)
Interim sequence with tail starting at 4: 3241
Sorting tail into ascending order by exchanging first with last,
second with next-to-last, etc. as necessary

Permutation no 15: 3214  Key = 1 (leftmost byte of rightmost in-sequence pair)
Swapping key with 4 (rightmost byte in tail that is greater than key)

Permutation no 16: 3241  Key = 2 (leftmost byte of rightmost in-sequence pair)
Swapping key with 4 (rightmost byte in tail that is greater than key)
Interim sequence with tail starting at 2: 3421
Sorting tail into ascending order by exchanging first with last,
second with next-to-last, etc. as necessary

Permutation no 17: 3412  Key = 1 (leftmost byte of rightmost in-sequence pair)
Swapping key with 2 (rightmost byte in tail that is greater than key)

Permutation no 18: 3421  Key = 3 (leftmost byte of rightmost in-sequence pair)
Swapping key with 4 (rightmost byte in tail that is greater than key)
Interim sequence with tail starting at 3: 4321
Sorting tail into ascending order by exchanging first with last,
second with next-to-last, etc. as necessary

Permutation no 19: 4123  Key = 2 (leftmost byte of rightmost in-sequence pair)
Swapping key with 3 (rightmost byte in tail that is greater than key)

Permutation no 20: 4132  Key = 1 (leftmost byte of rightmost in-sequence pair)
Swapping key with 2 (rightmost byte in tail that is greater than key)
Interim sequence with tail starting at 3: 4231
Sorting tail into ascending order by exchanging first with last,
second with next-to-last, etc. as necessary

Permutation no 21: 4213  Key = 1 (leftmost byte of rightmost in-sequence pair)
Swapping key with 3 (rightmost byte in tail that is greater than key)

Permutation no 22: 4231  Key = 2 (leftmost byte of rightmost in-sequence pair)
Swapping key with 3 (rightmost byte in tail that is greater than key)
Interim sequence with tail starting at 2: 4321
Sorting tail into ascending order by exchanging first with last,
second with next-to-last, etc. as necessary

Permutation no 23: 4312  Key = 1 (leftmost byte of rightmost in-sequence pair)
Swapping key with 2 (rightmost byte in tail that is greater than key)

Permutation no 24: 4321
Programming - a skill for life!

Challenges from the DelphiForFun Website