#! /usr/bin/env python
#
def ubvec_next_grlex ( n, ubvec ):

#*****************************************************************************80
#
## UBVEC_NEXT_GRLEX generates the next UBVEC in GRLEX order.
#
#  Discussion:
#
#    N = 3
#
#    Input      Output
#    -----      ------
#    0 0 0  =>  0 0 1
#    0 0 1  =>  0 1 0
#    0 1 0  =>  1 0 0
#    1 0 0  =>  0 1 1
#    0 1 1  =>  1 0 1
#    1 0 1  =>  1 1 0
#    1 1 0  =>  1 1 1
#    1 1 1  =>  0 0 0
#
#    A UBVEC is a vector of N binary digits.
#
#    A UBVEC can be interpreted as a binary representation of an
#    unsigned integer, with the first entry being the coefficient of
#    2^(N-1) and the last entry the coefficient of 1.
#
#    UBVEC   #
#    -----  --
#    00000   0
#    00001   1
#    00010   2
#    10000  16
#
#  Licensing:
#
#    This code is distributed under the GNU LGPL license.
#
#  Modified:
#
#    23 November 2015
#
#  Author:
#
#    John Burkardt
#
#  Parameters:
#
#    Input, integer N, the dimension.
#
#    Input, integer UBVEC(N), the binary vector whose 
#    successor is desired.
#
#    Output, integer UBVEC(N), the successor to the input vector.
#
  import numpy as np
#
#  Initialize locations of 0 and 1.
#
  if ( ubvec[0] == 0 ):
    z = 0
    o = -1
  else:
    z = -1
    o = 0
#
#  Moving from right to left, search for a "1", preceded by a "0".
#
  for i in range ( n - 1, 0, -1 ):
    if ( ubvec[i] == 1 ):
      o = i
      if ( ubvec[i-1] == 0 ):
        z = i - 1
        break
#
#  UBVEC = 0
#
  if ( o == -1 ):

    ubvec[n-1] = 1
#
#  01 never occurs.  So for sure, B(0) = 1.
#
  elif ( z == -1 ):

    s = np.sum ( ubvec )

    if ( s == n ):
      for i in range ( 0, n ):
        ubvec[i] = 0
    else:
      for i in range ( 0, n - s - 1 ):
        ubvec[i] = 0
      for i in range ( n - s - 1, n ):
        ubvec[i] = 1
#
#  Found the rightmost "01" string.
#  Replace it by "10".
#  Shift following 1's to the right.
#
  else:

    ubvec[z] = 1
    ubvec[o] = 0
    s = 0
    for i in range ( o + 1, n ):
      s = s + ubvec[i]
    for i in range ( o + 1, n - s ):
      ubvec[i] = 0
    for i in range ( n - s, n ):
      ubvec[i] = 1

  return ubvec

def ubvec_next_grlex_test ( ):

#*****************************************************************************80
#
## UBVEC_NEXT_GRLEX_TEST tests UBVEC_NEXT_GRLEX.
#
#  Licensing:
#
#    This code is distributed under the GNU LGPL license. 
#
#  Modified:
#
#    23 November 2015
#
#  Author:
#
#    John Burkardt
#
  import numpy as np
  import platform

  n = 4

  print ( '' )
  print ( 'UBVEC_NEXT_GRLEX_TEST' )
  print ( '  Python version: %s' % ( platform.python_version ( ) ) )
  print ( '  UBVEC_NEXT_GRLEX computes unsigned binary vectors in GRLEX order.' )
  print ( '' )

  b = np.zeros ( n, dtype = np.int32 )

  for i in range ( 0, 17 ):
    print ( '  %2d:  ' % ( i ), end = '' )
    for j in range ( 0, n ):
      print ( '%d' % ( b[j] ), end = '' )
    print ( '' )
    b = ubvec_next_grlex ( n, b )
#
#  Terminate.
#
  print ( '' )
  print ( 'UBVEC_NEXT_GRLEX_TEST' )
  print ( '  Normal end of execution.' )
  return

if ( __name__ == '__main__' ):
  from timestamp import timestamp
  timestamp ( )
  ubvec_next_grlex_test ( )
  timestamp ( )