#! /usr/bin/env python
#
def comp_unrank_grlex ( kc, rank ):
#*****************************************************************************80
#
## COMP_UNRANK_GRLEX computes the composition of given grlex rank.
#
# Licensing:
#
# This code is distributed under the GNU LGPL license.
#
# Modified:
#
# 30 October 2014
#
# Author:
#
# John Burkardt
#
# Parameters:
#
# Input, int KC, the number of parts of the composition.
# 1 <= KC.
#
# Input, int RANK, the rank of the composition.
# 1 <= RANK.
#
# Output, int XC[KC], the composition XC of the given rank.
# For each I, 0 <= XC[I] <= NC, and
# sum ( 1 <= I <= KC ) XC[I] = NC.
#
from i4_choose import i4_choose
from sys import exit
import numpy as np
#
# Ensure that 1 <= KC.
#
if ( kc < 1 ):
print ( '' )
print ( 'COMP_UNRANK_GRLEX - Fatal error!' )
print ( ' KC < 1' )
exit ( 'COMP_UNRANK_GRLEX - Fatal error!' )
#
# Ensure that 1 <= RANK.
#
if ( rank < 1 ):
print ( '' )
print ( 'COMP_UNRANK_GRLEX - Fatal error!' )
print ( ' RANK < 1' )
exit ( 'COMP_UNRANK_GRLEX - Fatal error!' )
#
# Determine the appropriate value of NC.
# Do this by adding up the number of compositions of sum 0, 1, 2,
# ..., without exceeding RANK. Moreover, RANK - this sum essentially
# gives you the rank of the composition within the set of compositions
# of sum NC. And that's the number you need in order to do the
# unranking.
#
rank1 = 1
nc = -1
while ( True ):
nc = nc + 1
r = i4_choose ( nc + kc - 1, nc )
if ( rank < rank1 + r ):
break
rank1 = rank1 + r
rank2 = rank - rank1
#
# Convert to KSUBSET format.
# Apology: an unranking algorithm was available for KSUBSETS,
# but not immediately for compositions. One day we will come back
# and simplify all this.
#
ks = kc - 1
ns = nc + kc - 1
xs = np.zeros ( ks, dtype = np.int32 )
nksub = i4_choose ( ns, ks )
j = 1
for i in range ( 1, ks + 1 ):
r = i4_choose ( ns - j, ks - i )
while ( r <= rank2 and 0 < r ):
rank2 = rank2 - r
j = j + 1
r = i4_choose ( ns - j, ks - i )
xs[i-1] = j
j = j + 1
#
# Convert from KSUBSET format to COMP format.
#
xc = np.zeros ( kc, dtype = np.int32 )
xc[0] = xs[0] - 1
for i in range ( 2, kc ):
xc[i-1] = xs[i-1] - xs[i-2] - 1
xc[kc-1] = ns - xs[ks-1]
return xc
def comp_unrank_grlex_test ( ):
#*****************************************************************************80
#
## COMP_UNRANK_GRLEX_TEST tests COMP_UNRANK_GRLEX.
#
# Licensing:
#
# This code is distributed under the GNU LGPL license.
#
# Modified:
#
# 30 October 2014
#
# Author:
#
# John Burkardt
#
import platform
from i4vec_sum import i4vec_sum
kc = 3
print ( '' )
print ( 'COMP_UNRANK_GRLEX_TEST' )
print ( ' Python version: %s' % ( platform.python_version ( ) ) )
print ( ' A COMP is a composition of an integer N into K parts.' )
print ( ' Each part is nonnegative. The order matters.' )
print ( ' COMP_UNRANK_GRLEX determines the parts' )
print ( ' of a COMP from its rank.' )
print ( '' )
print ( ' Rank: -> NC COMP ' )
print ( ' ----: -- ------------ ' )
for rank in range ( 1, 72 ):
xc = comp_unrank_grlex ( kc, rank )
nc = i4vec_sum ( kc, xc )
print ( ' %3d: ' % ( rank ) ),
print ( ' %2d = ' % ( nc ) ),
for j in range ( 0, kc - 1 ):
print ( '%2d + ' % ( xc[j] ) ),
print ( '%2d' % ( xc[kc-1] ) )
#
# When XC(1) == NC, we have completed the compositions associated with
# a particular integer, and are about to advance to the next integer.
#
if ( xc[0] == nc ):
print ( ' ----: -- ------------' )
#
# Terminate.
#
print ( '' )
print ( 'COMP_UNRANK_GRLEX_TEST:' )
print ( ' Normal end of execution.' )
return
if ( __name__ == '__main__' ):
from timestamp import timestamp
timestamp ( )
comp_unrank_grlex_test ( )
timestamp ( )