Permutations: Difference between revisions

===Permutations from integers===

A console application in Free Pascal, created with the Lazarus IDE.

<lang pascal>

program Permutations;

(*

Demonstrates four closely related ways of establishing a bijection between

permutations of 0..(n-1) and integers 0..(n! - 1).

Each integer in that range is represented by mixed-base digits d[0..n-1],

where each d[j] satisfies 0 <= d[j] <=j.

The integer represented by d[0..n-1] is

d[n-1]*(n-1)! + d[n-2]*(n-2)! + ... + d[1]*1! + d[0]*0!

where the last term can be omitted in practice because d[0] is always 0.

See the section "Numbering permutations" in the Wikipedia article

"Permutation" (NB their digit array d is 1-based).

*)

uses SysUtils, TypInfo;

type TPermIntMapping = (map_I, map_J, map_K, map_L);

type TPermutation = array of integer;

// Function to map an integer to a permutation.

function IntToPerm( map : TPermIntMapping;

nrItems, z : integer) : TPermutation;

var

d, lookup : array of integer;

x, y : integer;

h, j, k, m : integer;

begin

SetLength( result, nrItems);

SetLength( lookup, nrItems);

SetLength( d, nrItems);

m := nrItems - 1;

// Convert z to digits d[0..m] (see comment at head of program).

d[0] := 0;

y := z;

for j := 1 to m - 1 do begin

x := y div (j + 1);

d[j] := y - x*(j + 1);

y := x;

end;

d[m] := y;

// Set up the permutation elements

case map of

map_I, map_L: for j := 0 to m do lookup[j] := j;

map_J, map_K: for j := 0 to m do lookup[j] := m - j;

end;

for j := m downto 0 do begin

k := d[j];

case map of

map_I: result[lookup[k]] := m - j;

map_J: result[j] := lookup[k];

map_K: result[lookup[k]] := j;

map_L: result[m - j] := lookup[k];

end;

// When lookup[k] has been used, it's removed from the lookup table

// and the elements above it are moved down one place.

for h := k to j - 1 do lookup[h] := lookup[h + 1];

end;

end;

// Function to map a permutation to an integer; inverse of the above.

// Put in for completeness, not required for Rosetta Code task.

function PermToInt( map : TPermIntMapping;

p : TPermutation) : integer;

var

m, i, j, k : integer;

d : array of integer;

begin

m := High(p); // number of items in permutation is m + 1

SetLength( d, m + 1);

for k := 0 to m do d[k] := 0; // initialize all digits to 0

// Looking for inversions

for i := 0 to m - 1 do begin

for j := i + 1 to m do begin

if p[j] < p[i] then begin

case map of

map_I : inc( d[m - p[j]]);

map_J : inc( d[j]);

map_K : inc( d[p[i]]);

map_L : inc( d[m - i]);

end;

end;

end;

end;

// Get result from its digits (see comment at head of program).

result := d[m];

for j := m downto 2 do result := result*j + d[j - 1];

end;

// Main routine to generate permutations of the integers 0..(n-1),

// where n is passed as a command-line parameter, e.g. Permutations 4

var

n, n_fac, z, j : integer;

nrErrors : integer;

perm : TPermutation;

map : TPermIntMapping;

lineOut : string;

pinfo : TypInfo.PTypeInfo;

begin

n := SysUtils.StrToInt( ParamStr(1));

n_fac := 1;

for j := 2 to n do n_fac := n_fac*j;

pinfo := System.TypeInfo( TPermIntMapping);

lineOut := 'integer';

for map := Low( TPermIntMapping) to High( TPermIntMapping) do begin

lineOut := lineOut + ' ' + TypInfo.GetEnumName( pinfo, ord(map));

end;

WriteLn( lineOut);

for z := 0 to n_fac - 1 do begin

lineOut := SysUtils.Format( '%7d', [z]);

for map := Low( TPermIntMapping) to High( TPermIntMapping) do begin

perm := IntToPerm( map, n, z);

// Check the inverse mapping (not required for Rosetta Code task)

Assert( z = PermToInt( map, perm));

lineOut := lineOut + ' ';

for j := 0 to n - 1 do

lineOut := lineOut + SysUtils.Format( '%d', [perm[j]]);

end;

WriteLn( lineOut);

end;

end.

</lang>

{{out}}

<pre>

integer map_I map_J map_K map_L

0 0123 0123 0123 0123

1 0132 1023 1023 0132

2 0213 0213 0213 0213

3 0312 2013 1203 0231

4 0231 1203 2013 0312

5 0321 2103 2103 0321

6 1023 0132 0132 1023

7 1032 1032 1032 1032

8 2013 0312 0231 1203

9 3012 3012 1230 1230

10 2031 1302 2031 1302

11 3021 3102 2130 1320

12 1203 0231 0312 2013

13 1302 2031 1302 2031

14 2103 0321 0321 2103

15 3102 3021 1320 2130

16 2301 2301 2301 2301

17 3201 3201 2310 2310

18 1230 1230 3012 3012

19 1320 2130 3102 3021

20 2130 1320 3021 3102

21 3120 3120 3120 3120

22 2310 2310 3201 3201

23 3210 3210 3210 3210

</pre>