! Generating all permuations on N items in lexico order;
! Keywords: Permutation generation;
SETS:
ITEM: INPOS;
ENDSETS DATA:
ITEM = 1..4; ! Number of items to permute;
ENDDATA
PROCEDURE WRITEOUT:
! Write current permuation;
@WRITE( @FORMAT(iter,'6.0f'),') ');
@FOR( ITEM(ii):
@WRITE( INPOS(ii),' ');
);
@WRITE( @NEWLINE(1));
ENDPROCEDURE
CALC:
! At each iteration, INPOS(i) will give the item/integer
in position i at the current iteration;
@SET('TERSEO',2); ! Set default output to terse;
NT = @SIZE(ITEM); ! Number of items in the permutation;
! Initial increasing order;
@FOR( ITEM(i):
INPOS(i) = i;
);
! Write the first permutation;
iter = 1;
WRITEOUT; ! Write out current permutation;
k = 1; ! Next time k = 0 we are done;
@WHILE( k #GT# 0: ! Loop over all permutations;
! Find largest k for which INPOS(k) < INPOS(k+1);
k = 0; ! Default is, no such k;
i = NT;
@WHILE( i #GT# 1:
i = i - 1;
@IFC( INPOS(i) #LT# INPOS(i+1):
k = i;
i = 0;
);
);
@IFC( k #GT# 0: ! Still more to do? ;
! Find largest r for which INPOS(k) < INPOS(r);
INPK = INPOS(k);
i = NT+1;
@WHILE( i #GT# 0:
i = i - 1;
@IFC( INPK #LT# INPOS(i) :
r = i;
i = 0;
);
);
! Swap INPOS(k) and INPOS(r);
INPOS(k) = INPOS(r);
INPOS(r) = INPK;
! Reverse the sequence INPOS(k+1:NT);
i = k;
j = NT;
@WHILE( i #LT# j:
i = i + 1;
ITMP = INPOS(i);
INPOS(i) = INPOS(j);
INPOS(j) = ITMP;
j = j - 1;
);
iter = iter + 1;
WRITEOUT; ! Write out current permutation;
);
);
ENDCALC
|