#! /usr/bin/env python
#
def perm1_check ( n, p ):

#*****************************************************************************80
#
## PERM1_CHECK checks a permutation of (1,...,N).
#
#  Discussion:
#
#    The routine verifies that each of the integers from 1 to
#    to N occurs among the N entries of the permutation.
#
#  Licensing:
#
#    This code is distributed under the GNU LGPL license. 
#
#  Modified:
#
#    25 August 2015
#
#  Author:
#
#    John Burkardt
#
#  Parameters:
#
#    Input, integer N, the number of entries.
#
#    Input, integer P(N), the array to check.
#
#    Output, logical CHECK:
#    True if P is a legal permutation of (1,...,N).
#    False if P is not a legal permutation of (1,...,N).
#
  from sys import exit

  check = True

  for value in range ( 1, n + 1 ):

    check = False

    for location in range ( 0, n ):
      if ( p[location] == value ):
        check = True
        break

    if ( not check ):
#     print ( '' )
#     print ( 'PERM1_CHECK - Warning!' )
#     print ( '  Permutation is missing the value %d.' % ( value ) )
      return check

  return check

def perm1_check_test ( ):

#*****************************************************************************80
#
## PERM1_CHECK_TEST tests PERM1_CHECK.
#
#  Licensing:
#
#    This code is distributed under the GNU LGPL license.
#
#  Modified:
#
#    24 May 2015
#
#  Author:
#
#    John Burkardt
#
  import numpy as np
  import platform

  n = 5
  p1 = np.array ( [ 5, 2, 3, 4, 1 ] )
  p2 = np.array ( [ 4, 1, 3, 0, 2 ] )
  p3 = np.array ( [ 0, 2, 1, 3, 2 ] )

  print ( '' )
  print ( 'PERM1_CHECK_TEST' )
  print ( '  Python version: %s' % ( platform.python_version ( ) ) )
  print ( '  PERM1_CHECK checks a permutation of 1,...,N.' )

  perm1_print ( n, p1, '  Permutation 1:' )
  check = perm1_check ( n, p1 )
  if ( check ):
    print ( '  This is a permutation.' )
  else:
    print ( '  This is not a permutation.' )

  perm1_print ( n, p2, '  Permutation 2:' )
  check = perm1_check ( n, p2 )
  if ( check ):
    print ( '  This is a permutation.' )
  else:
    print ( '  This is not a permutation.' )

  perm1_print ( n, p3, '  Permutation 3:' )
  check = perm1_check ( n, p3 )
  if ( check ):
    print ( '  This is a permutation.' )
  else:
    print ( '  This is not a permutation.' )
#
#  Terminate.
#
  print ( '' )
  print ( 'PERM1_CHECK_TEST:' )
  print ( '  Normal end of execution.' )
  return

def perm1_enum ( n ):

#*****************************************************************************80
#
## PERM1_ENUM enumerates the permutations on N digits.
#
#  Licensing:
#
#    This code is distributed under the GNU LGPL license. 
#
#  Modified:
#
#    25 August 2015
#
#  Author:
#
#    John Burkardt
#
#  Parameters:
#
#    Input, integer N, the number of values being permuted.
#    N must be nonnegative.
#
#    Output, integer VALUE, the number of distinct elements.
#
  from i4_factorial import i4_factorial

  value = i4_factorial ( n )

  return value

def perm1_enum_test ( ):

#*****************************************************************************80
#
## PERM1_ENUM_TEST tests PERM1_ENUM.
#
#  Licensing:
#
#    This code is distributed under the GNU LGPL license. 
#
#  Modified:
#
#    25 August 2015
#
#  Author:
#
#    John Burkardt
#
  import platform

  print ( '' )
  print ( 'PERM1_ENUM_TEST' )
  print ( '  Python version: %s' % ( platform.python_version ( ) ) )
  print ( '  PERM1_ENUM enumerates the permutations of 1,...,N.' )
  print ( '' )
  print ( '         N      PERM1_ENUM' )
  print ( '' )

  for n in range ( 1, 11 ):

    value = perm1_enum ( n )

    print ( '  %8d  %12d' % ( n, value ) )   
#
#  Terminate.
#
  print ( '' )
  print ( 'PERM1_ENUM_TEST' )
  print ( '  Normal end of execution.' )
  return

def perm1_inverse ( n, p ):

#*****************************************************************************80
#
#% PERM1_INVERSE computes the inverse of a 1-based permutation.
#
#  Licensing:
#
#    This code is distributed under the GNU LGPL license.
#
#  Modified:
#
#    25 August 2015
#
#  Author:
#
#    John Burkardt
#
#  Reference:
#
#    Donald Kreher, Douglas Simpson,
#    Combinatorial Algorithms,
#    CRC Press, 1998,
#    ISBN: 0-8493-3988-X,
#    LC: QA164.K73.
#
#  Parameters:
#
#    Input, integer N, the number of values being permuted.
#    N must be positive.
#
#    Input, integer P(N), describes the permutation.
#    P(I) is the item which is permuted into the I-th place
#    by the permutation.
#
#    Output, integer P_INV(N), the inverse permutation.
#
  import numpy as np

  perm1_check ( n, p )

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

  for i in range ( 0, n ):
    p_inv[p[i]-1] = i + 1

  return p_inv

def perm1_inverse_test ( ):

#*****************************************************************************80
#
## PERM1_INVERSE_TEST tests PERM1_INVERSE
#
#  Licensing:
#
#    This code is distributed under the GNU LGPL license.
#
#  Modified:
#
#    25 August 2015
#
#  Author:
#
#    John Burkardt
#
  import numpy as np
  import platform

  n = 7
  p1 = np.array ( [ 4, 3, 5, 1, 7, 6, 2 ] )

  print ( '' )
  print ( 'PERM1_INVERSE_TEST' )
  print ( '  Python version: %s' % ( platform.python_version ( ) ) )
  print ( '  PERM1_INVERSE inverts a permutation of (1,...,N)' )

  perm1_print ( n, p1, '  The original permutation:' )
 
  p2 = perm1_inverse ( n, p1 )
 
  perm1_print ( n, p2, '  The inverted permutation:' )
#
#  Terminate.
#
  print ( '' )
  print ( 'PERM1_INVERSE_TEST:' )
  print ( '  Normal end of execution.' )
  return

def perm1_lex_next ( n, p, rank ):

#*****************************************************************************80
#
## PERM1_LEX_NEXT computes the lexicographic permutation successor.
#
#  Example:
#
#    RANK  Permutation
#
#       0  1 2 3 4
#       1  1 2 4 3
#       2  1 3 2 4
#       3  1 3 4 2
#       4  1 4 2 3
#       5  1 4 3 2
#       6  2 1 3 4
#       ...
#      23  4 3 2 1
#
#  Licensing:
#
#    This code is distributed under the GNU LGPL license. 
#
#  Modified:
#
#    25 August 2015
#
#  Author:
#
#    John Burkardt
#
#  Reference:
#
#    Donald Kreher, Douglas Simpson,
#    Combinatorial Algorithms,
#    CRC Press, 1998,
#    ISBN: 0-8493-3988-X,
#    LC: QA164.K73.
#
#  Parameters:
#
#    Input, integer N, the number of values being permuted.
#    N must be positive.
#
#    Input, integer P(N), the input permutation.
#
#    Input, integer RANK, the rank of the input permutation.
#    If RANK = -1, then the input permutation is ignored, and the
#    function returns the first permutation in the ordered list,
#    with RANK = 1.
#
#    Output, integer P(N), the successor permutation.  
#    If the input permutation was the last in the ordered list,
#    then the output permutation is the first permutation.
#
#    Output, integer RANK, the rank of the output permutation.
#
  from i4vec_indicator1 import i4vec_indicator1
#
#  If RANK <= -1, return the first permutation.
#
  if ( rank <= -1 ):
    p = i4vec_indicator1 ( n )
    rank = 0
    return p, rank
#
#  Make sure the input permutation is legal.
#
  check = perm1_check ( n, p )

  if ( not check ):
    print ( '' )
    print ( 'PERM1_LEX_NEXT - Fatal error!' )
    print ( '  PERM1_CHECK failed.' )
    exit ( 'PERM1_LEX_NEXT - Fatal error!' )
#
#  Seek I, the highest index for which the next element is bigger.
#
  i = n - 2

  while ( True ):

    if ( i < 0 ):
      break

    if ( p[i] <= p[i+1] ):
      break

    i = i - 1
#
#  If no I could be found, then we have reach the final permutation,
#  N, N-1, ..., 2, 1.  Time to start over again.
#
  if ( i == -1 ):
    p = i4vec_indicator1 ( n )
    rank = -1
  else:
#
#  Otherwise, look for the the highest index after I whose element
#  is bigger than I's.  We know that I+1 is one such value, so the
#  loop will never fail.
#
    j = n - 1
    while ( p[j] < p[i] ): 
      j = j - 1
#
#  Interchange elements I and J.
#
    t    = p[i]
    p[i] = p[j]
    p[j] = t
#
#  Reverse the elements from I+1 to N-1.
#
    k_hi = ( n + i ) // 2

    for k in range ( i + 1, k_hi + 1 ):
      l = n + i - k
      t    = p[k]
      p[k] = p[l]
      p[l] = t

    rank = rank + 1

  return p, rank

def perm1_lex_next_test ( ):

#*****************************************************************************80
#
## PERM1_LEX_NEXT_TEST tests PERM1_LEX_NEXT.
#
#  Licensing:
#
#    This code is distributed under the GNU LGPL license.
#
#  Modified:
#
#    25 August 2015
#
#  Author:
#
#    John Burkardt
#
  import numpy as np
  import platform

  n = 4

  print ( '' )
  print ( 'PERM1_LEX_NEXT_TEST' )
  print ( '  Python version: %s' % ( platform.python_version ( ) ) )
  print ( '  PERM1_LEX_NEXT generates 1-based permutations in lexicographic order.' )
  print ( '' )

  more = False
  p = np.zeros ( n, dtype = np.int32 )
  rank = -1

  while ( True ):

    p, rank = perm1_lex_next ( n, p, rank )

    if ( rank == -1 ):
      break

    print ( '  %2d:' % ( rank ), end = '' )
    for i in range ( 0, n ):
      print ( '  %2d' % ( p[i] ), end = '' )
    print ( '' )
#
#  Terminate.
#
  print ( '' )
  print ( 'PERM1_LEX_NEXT_TEST:' )
  print ( '  Normal end of execution.' )
  return

def perm1_lex_rank ( n, p ):

#*****************************************************************************80
#
## PERM1_LEX_RANK computes the lexicographic rank of a 1-based permutation.
#
#  Discussion:
#
#    The original code altered the input permutation.  
#
#  Licensing:
#
#    This code is distributed under the GNU LGPL license. 
#
#  Modified:
#
#    26 August 2015
#
#  Author:
#
#    John Burkardt
#
#  Reference:
#
#    Donald Kreher, Douglas Simpson,
#    Combinatorial Algorithms,
#    CRC Press, 1998,
#    ISBN: 0-8493-3988-X,
#    LC: QA164.K73.
#
#  Parameters:
#
#    Input, integer N, the number of values being permuted.
#    N must be positive.
#
#    Input, integer P(N), describes the permutation.
#    P(I) is the item which is permuted into the I-th place
#    by the permutation.
#
#    Output, integer RANK, the rank of the permutation.
#
  import numpy as np
  from i4_factorial import i4_factorial
#
#  Check.
#
  check = perm1_check ( n, p )

  if ( not check ):
    print ( '' )
    print ( 'PERM1_LEX_RANK - Fatal error!' )
    print ( '  PERM1_CHECK failed!' )
    exit ( 'PERM1_LEX_RANK - Fatal error!' )

  rank = 0
  p2 = np.zeros ( n, dtype = np.int32 )
  for i in range ( 0, n ):
    p2[i] = p[i]

  for j in range ( 0, n ):

    rank = rank + ( p2[j] - 1 ) * i4_factorial ( n - j - 1 )

    for i in range ( j + 1, n ):
      if ( p2[j] < p2[i] ):
        p2[i] = p2[i] - 1

  return rank

def perm1_lex_rank_test ( ):

#*****************************************************************************80
#
## PERM1_LEX_RANK_TEST tests PERM1_LEX_RANK.
#
#  Licensing:
#
#    This code is distributed under the GNU LGPL license.
#
#  Modified:
#
#    26 August 2015
#
#  Author:
#
#    John Burkardt
#
  import numpy as np
  import platform

  print ( '' )
  print ( 'PERM1_LEX_RANK_TEST' )
  print ( '  Python version: %s' % ( platform.python_version ( ) ) )
  print ( '  PERM1_LEX_RANK returns the lexicographic rank of' )
  print ( '  a permutation of (1,...,N).' )

  n = 4
  p = np.array ( [ 4, 1, 3, 2 ] )
  perm1_print ( n, p, '  A 1-based permutation:' )
  rank = perm1_lex_rank ( n, p )

  print ( '' )
  print ( '  Rank = %d' % ( rank ) )
#
#  Terminate.
#
  print ( '' )
  print ( 'PERM1_LEX_RANK_TEST' )
  print ( '  Normal end of execution.' )
  return

def perm1_lex_unrank ( n, rank ):

#*****************************************************************************80
#
## PERM1_LEX_UNRANK computes the 1-based permutation of given lexicographic rank.
#
#  Licensing:
#
#    This code is distributed under the GNU LGPL license. 
#
#  Modified:
#
#    26 August 2015
#
#  Author:
#
#    John Burkardt
#
#  Reference:
#
#    Donald Kreher, Douglas Simpson,
#    Combinatorial Algorithms,
#    CRC Press, 1998,
#    ISBN: 0-8493-3988-X,
#    LC: QA164.K73.
#
#  Parameters:
#
#    Input, integer N, the number of values being permuted.
#    N must be positive.
#
#    Input, integer RANK, the rank of the permutation.
#
#    Output, integer P(N), describes the permutation.
#
  import numpy as np
  from i4_factorial import i4_factorial
  from sys import exit
#
#  Check.
#
  if ( n < 1 ):
    print ( '' )
    print ( 'PERM1_LEX_UNRANK - Fatal error!' )
    print ( '  Input N is illegal.' )
    exit ( 'PERM1_LEX_UNRANK - Fatal error!' )

  nperm = perm1_enum ( n )

  if ( rank < 0 or nperm < rank ):
    print ( '' )
    print ( 'PERM1_LEX_UNRANK - Fatal error!' )
    print ( '  The input rank is illegal.' )
    exit ( 'PERM1_LEX_UNRANK - Fatal error!' )
 
  p = np.zeros ( n, dtype = np.int32 )

  p[n-1] = 1

  for j in range ( 1, n ):

    d = ( rank % i4_factorial ( j + 1 ) ) // i4_factorial ( j )
    rank = rank - d * i4_factorial ( j )
    p[n-j-1] = d + 1

    for i in range ( n - j + 1, n + 1 ):

      if ( d < p[i-1] ):
        p[i-1] = p[i-1] + 1

  return p

def perm1_lex_unrank_test ( ):

#*****************************************************************************80
#
## PERM1_LEX_UNRANK_TEST tests PERM1_LEX_UNRANK.
#
#  Licensing:
#
#    This code is distributed under the GNU LGPL license.
#
#  Modified:
#
#    26 August 2015
#
#  Author:
#
#    John Burkardt
#
  import numpy as np
  import platform
  from i4_uniform_ab import i4_uniform_ab

  print ( '' )
  print ( 'PERM1_LEX_UNRANK_TEST' )
  print ( '  Python version: %s' % ( platform.python_version ( ) ) )
  print ( '  PERM1_LEX_UNRANK returns the 1-based permutation' )
  print ( '  of given lexicographic rank.' )

  n = 4
  n_perm = perm1_enum ( n )

  seed = 123456789
  rank, seed = i4_uniform_ab ( 0, n_perm, seed )

  print ( '' )
  print ( '  Rank = %d' % ( rank ) )

  p = perm1_lex_unrank ( n, rank )
  perm1_print ( n, p, '  The corresponding permutation:' )
#
#  Terminate.
#
  print ( '' )
  print ( 'PERM1_LEX_UNRANK_TEST' )
  print ( '  Normal end of execution.' )
  return

def perm1_print ( n, p, title ):

#*****************************************************************************80
#
## PERM1_PRINT prints a permutation of (1,...,N).
#
#  Example:
#
#    Input:
#
#      P = 7 2 4 1 5 3 6
#
#    Printed output:
#
#      "This is the permutation:"
#
#      1 2 3 4 5 6 7
#      7 2 4 1 5 3 6
#
#  Licensing:
#
#    This code is distributed under the GNU LGPL license. 
#
#  Modified:
#
#    23 June 2015
#
#  Author:
#
#    John Burkardt
#
#  Parameters:
#
#    Input, integer N, the number of objects permuted.
#
#    Input, integer P(N), the permutation, in standard index form.
#
#    Input, string TITLE, an optional title.
#    If no title is supplied, then only the permutation is printed.
#
  inc = 20

  if ( len ( title ) != 0 ):

    print ( '' )
    print ( title )

    for ilo in range ( 0, n, inc ):
      ihi = min ( n, ilo + inc )

      print ( '' )
      print ( '  ', end = '' )
      
      for i in range ( ilo, ihi ):
        print ( '%4d' % ( i + 1 ), end = '' )
      print ( '' )

      print ( '  ', end = '' )
      for i in range ( ilo, ihi ):
        print ( '%4d' % ( p[i] ), end = '' )
      print ( '' )

  else:

    for ilo in range ( 0, n, inc ):
      ihi = min ( n, ilo + inc )
      print ( '  ', end = '' )
      for i in range ( ilo, ihi ):
        print ( '%4d' % ( p[i] ), end = '' )
      print ( '' )

  return

def perm1_print_test ( ):

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

  print ( '' )
  print ( 'PERM1_PRINT_TEST' )
  print ( '  Python version: %s' % ( platform.python_version ( ) ) )
  print ( '  PERM1_PRINT prints a permutation of (1,...,N).' )

  n = 7
  p = np.array ( [ 7, 2, 4, 1, 5, 3, 6 ] )
  perm1_print ( n, p, '  A 1-based permutation:' )
#
#  Terminate.
#
  print ( '' )
  print ( 'PERM1_PRINT_TEST' )
  print ( '  Normal end of execution.' )
  return

def perm1_random ( n, seed ):

#*****************************************************************************80
#
## PERM1_RANDOM selects a random 1-based permutation of N objects.
#
#  Discussion:
#
#    An I4VEC is a vector of I4 values.
#
#    The algorithm is known as the Fisher-Yates or Knuth shuffle.
#
#  Licensing:
#
#    This code is distributed under the GNU LGPL license.
#
#  Modified:
#
#    25 August 2015
#
#  Author:
#
#    John Burkardt
#
#  Parameters:
#
#    Input, integer N, the number of entries in the vector.
#
#    Input, integer SEED, a seed for the random number generator.
#
#    Output, integer P[N], a permutation of the digits 0 through N-1.
#
#    Output, integer SEED, an updated seed.
#
  import numpy as np
  from i4_uniform_ab import i4_uniform_ab

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

  for i in range ( 0, n ):
    p[i] = i + 1

  for i in range ( 0, n - 1 ):
    j, seed = i4_uniform_ab ( i, n - 1, seed )
    k    = p[i]
    p[i] = p[j]
    p[j] = k

  return p, seed

def perm1_random_test ( ):

#*****************************************************************************80
#
## PERM1_RANDOM_TEST tests PERM1_RANDOM.
#
#  Licensing:
#
#    This code is distributed under the GNU LGPL license.
#
#  Modified:
#
#    25 August 2015
#
#  Author:
#
#    John Burkardt
#
  import platform

  n = 10

  print ( '' )
  print ( 'PERM1_RANDOM_TEST' )
  print ( '  Python version: %s' % ( platform.python_version ( ) ) )
  print ( '  PERM1_RANDOM randomly selects a 1-based permutation.' )
  print ( '' )

  seed = 123456789

  for test in range ( 0, 5 ):
    p, seed = perm1_random ( n, seed )
    perm1_print ( n, p, '' )
#
#  Terminate.
#
  print ( '' )
  print ( 'PERM1_RANDOM_TEST' )
  print ( '  Normal end of execution.' )
  return

if ( __name__ == '__main__' ):
  from timestamp import timestamp
  timestamp ( )
  perm1_check_test ( )
  perm1_enum_test ( )
  perm1_inverse_test ( )
  perm1_lex_next_test ( )
  perm1_lex_rank_test ( )
  perm1_lex_unrank_test ( )
  perm1_print_test ( )
  perm1_random_test ( )
  timestamp ( )