Lindo Systems

! 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