Lindo Systems

! Enumerate all integer points in an n-dimensional box; 
!( Enumr8Box.lng);
! Keywords: Enumeration, Combinations, Depth first search;
SETS:
! Each item has a lower bound and an upper bound;
  ITEM: LBX, UBX, IX;
ENDSETS

DATA:
  ITEM = F34  F24  F15  F18  F10;! Items;
  LBX  =   0   0    3    0    0;! Min copies of each;
  UBX  =   1   2    4    1    1;! Max copies of each;
ENDDATA

PROCEDURE ENUMR8:
 ! Get next feasible integer point in a box;
 ! Inputs:
    NITEMS = number of items/dimensions,
    LBX(i) = lowest integer value for IX(i), for i= 1, 2, ... NITEMS,
    UBX(i) = highest integer value for IX(i),
    IX( ) = previous combination, initial combination
            is LBX(1), LBX(2),..., LBX(NITEMS).
   Outputs:
    ii = 1 if all combinations enumerated, else 0,
    IX( ) = next combination;

 ! The depth first algorithm;
  ! Find the highest index, ii, for which IX(ii) #LT# UB(ir);
   ii = NITEMS + 1;
   @WHILE( ii #GT# 1:
     ii = ii - 1;
      @IFC( IX(ii) #LT# UBX(ii):
   !   and increase it by 1; 
        IX(ii) = IX(ii) + 1;
        ii = 0;  ! This means we found one to increase;
        @ELSE
          IX(ii) = LBX(ii);
         ); ! @IFC( IX(ii ;
        ); ! @WHILE( ir;
   ! After falling through, ii = 1 means all were at UB;
ENDPROCEDURE

CALC:
  NITEMS = @SIZE(ITEM);
! Enumerate all integer points in the box, LBX( ) <= IX() <= UB();
  PASSES = 0;
  ii = 0;
! Initial solution is all at LBX();
  @FOR( ITEM(i): IX(i) = LBX(i););
  ! Loop over all combinations, We are done
   when ii = 1;
   @WHILE( ii #NE# 1:
    PASSES = PASSES+1;
    @WRITE( @FORMAT( PASSES, '4.0f'),':');
    @FOR( ITEM(i):
      @WRITE( @FORMAT( ix(i),' 3.0f'));
       );
    @WRITE( @NEWLINE(1));
     ENUMR8; ! Get next combo;
      );  
ENDCALC