-- permute.adb

procedure PERMUTE ( VECTOR : in out VECTOR_TYPE ;
                    PERMUTERS : in out PERMUTERS_TYPE ;  -- Scratch
                    IF_LAST : out BOOLEAN ) is

--
--      PURPOSE: Test driver routine, generate permutations of
--               the  N=VECTOR'LENGTH  ITEM'S in VECTOR .
--
--      CAUTION: N factorial permutations is a bunch for N > 9
--               The precise definition of a bunch is 3,628,800 up
--               7! =   5,040
--               8! =  40,320
--               9! = 362,880
--
--      INPUT:   VECTOR - input and output vector that is permuted
--                        This must be set up befor the first call
--                        and then used as the next permutation on
--                        each return
--
--               PERMUTERS(PERMUTERS'FIRST) /= PERMUTERS'FIRST on first call
--               e.g. PERMUTERS(PERMUTERS'FIRST) = PERMUTERS'LAST on first call
--
--      OUTPUT:  VECTOR - the next permuted vector
--               IF_LAST   = FALSE  if more permutations to be returned
--                         = TRUE   if the last permutation is being
--                                  returned (done)
--
--      Copyright 1985 by Westinghouse Electric Corporation
--                        Written 1 May, 1985 by Jon Squire
--
--
  J , K , L : INDEX ;
  T : ITEM ;
begin
  IF_LAST := FALSE ;
  if PERMUTERS'LENGTH = 1 then
    IF_LAST := TRUE ;
  elsif PERMUTERS ( PERMUTERS'FIRST ) /= PERMUTERS'FIRST then

--        Initialization ( user must set up VECTOR befor first call )
    for I in PERMUTERS'RANGE loop
      PERMUTERS ( I ) := I ;
    end loop ;
  else

--
--       find last in sequence of permuters 1's i.e. PERMUTERS'FIRST
--       reset permuters(k) to k as we go
--
    K := PERMUTERS'FIRST ;
    while PERMUTERS ( K + 1 ) = PERMUTERS'FIRST loop
      K := K + 1 ;
      PERMUTERS ( K ) := K ;
    end loop ;

--
--            reverse sequence  in  PERMUTERS'FIRST .. K
--
    L := ( PERMUTERS'FIRST + K ) / 2 ;
    for I in PERMUTERS'FIRST .. L loop
      J := K - I + PERMUTERS'FIRST ;
      T := VECTOR ( I ) ;
      VECTOR ( I ) := VECTOR ( J ) ;
      VECTOR ( J ) := T ;
    end loop ;

--
--               swap next higher item and decrement pointer
--
    K := K + 1 ;
    PERMUTERS ( K ) := PERMUTERS ( K ) - 1 ;
    J := PERMUTERS ( K ) ;
    T := VECTOR ( K ) ;
    VECTOR ( K ) := VECTOR ( J ) ;
    VECTOR ( J ) := T ;

--
--               find out if this is the last permutation
--
    K := PERMUTERS'LAST ;
    if PERMUTERS ( K ) = PERMUTERS'FIRST then
      while K > PERMUTERS'FIRST loop
        K := K - 1 ;
        if PERMUTERS ( K ) /= PERMUTERS'FIRST then
          return ;
        end if ;
      end loop ;
      IF_LAST := TRUE ;
    end if ;
  end if ;
end PERMUTE ;