# 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