! 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
|