INDEXINGPERMUTATIONS

Return to main page




# INDEXINGPERMUTATIONS, Indexing permutations with repeated elements


# Prologue.

# January 2012 in a thread of comp.programming "Q: Indexing a special kind of
# permutations" I asked for code of indexing permutations with 2 kinds of
# elements that are equal in number. A follow-up kindly provided code for the
# general case of arbitrary number of kinds of elements without restrictions.
# However, the part of the code for computing the indices for given permutations
# was missing. Later I did the coding myself for the special case of 2 kinds of
# elements. Subsequently on 26.2.2012 I posted a C code for the general case.
# That code has now been ported to Python in the following, which has the
# advantage that an upper limit on the system parameter dimperm no longer
# exists.

# The list card (at least 2 elements) is to be declared and the function
# initpermsys() invoked. card[*] are the cardinalities of (dimcard) sets of
# different objects. perm[*] represent a permutation of all (dimperm) objects,
# with designations of different kinds of objects being given by numerical
# values in [0, dimcard-1]. permindex gives the index of a permutaion in the
# lexicographic ordering (in the sense of 0 < 1 < 2 ... etc., which may not
# necessarily correspond to the "lexicographic" ordering of the "names" of the
# kinds of objects which the user chooses to associate with the numerical
# designations).

# In steganography one could arrange to have in a picture certain objects be
# ordered in a way such that their permutation index serves to inconspicuously
# transmit a number to the recipient. 
#
# The code for the special case of 2 kinds of elements is given in the Appendix
# further below.

# (Users who for whatever reasons prefer nonetheless to use my C code should in
# the function checkperm() there change the "dimperm" to "dimcard" in the line:
# for (i=0; i < dimperm; i++) cardsub[i]=0;)


# Version 1.0, released on 25.03.2014.

# Code lines of documents with the same version number are always identical.
# There may be interim modifications of comment lines. 


# This software may be freely used:

# 1. for all personal purposes unconditionally and

# 2. for all other purposes under the condition that its name, version number 
#    and authorship are explicitly mentioned and that the author is informed of
#    all eventual code modifications done.


# A list of present author's software that are currently directly maintained by
# himself is available at http://mok-kong-shen.de. Users are advised to
# download such software from that home page only.



################################################################################



import math


def fac(n):
  return(math.factorial(n))


def numperm():
  s=fac(scard)
  for i in range(dimcard):
    s//=fac(card[i])
  return(s)


# Initialization. User has to define card.

def initpermsys():
  global card,dimcard,dimperm,scard,nperm,cardsub,perm
  dimcard=len(card)
  assert(dimcard >= 2)
  cardsub=card[:]
  s=0
  for i in range(dimcard):
    assert(card[i] >= 1)
    s+=card[i]
  dimperm=s
  perm=[0 for i in range(dimperm)]
  scard=s
  nperm=numperm()
  print("Valid range of permutation index value: 0 ..",nperm-1)
  return


def findpermsub(permindex,permi,perm,card,scard,nperm):
  np=nperm
  for ii in range(dimcard-1,-1,-1):
    if card[ii] > 0:
      np-=(nperm*card[ii])//scard
      if np <= permindex:
        iss=ii
        break
  perm[permi]=iss
  permindex-=np
  nperm=(nperm*card[iss])//scard
  card[iss]-=1
  scard-=1
  if scard==0:
    return
  findpermsub(permindex,permi+1,perm,card,scard,nperm)
  return


# Given an index permindex, find the corresponding permutation.

def findperm(permindex,perm,card,cardsub,scard,nperm):
  assert(0 <= permindex < nperm)
  cardsub=card[:]
  findpermsub(permindex,0,perm,cardsub,scard,nperm)
  return


def checkperm(perm,card,cardsub):
  for i in range(dimcard):
    cardsub[i]=0
  for i in range(dimperm):
    ii=perm[i]
    assert(0 <= ii < dimcard)
    cardsub[ii]+=1
  assert(card == cardsub)
  return


def findindexsub(gpermindex,permi,perm,card,scard,nperm):
  p0=perm[permi]
  for ii in range(0,p0):
    if card[ii] > 0:
      gpermindex[0]+=(nperm*card[ii])//scard
  nperm=(nperm*card[p0])//scard
  scard-=1
  if scard==0:
    return
  card[p0]-=1
  findindexsub(gpermindex,permi+1,perm,card,scard,nperm)
  return


# Given a permutation perm[*], find its index in the lexicographic ordering.

def findindex(perm,card,cardsub,scard,nperm):
  assert(len(perm)==dimperm)
  checkperm(perm,card,cardsub)
  gpermindex=[0]
  for ii in range(dimcard):
    cardsub[ii]=card[ii]
  findindexsub(gpermindex,0,perm,cardsub,scard,nperm)
  return(gpermindex[0])



################################################################################



# Test program.

# Example:  2 oranges, 1 apple, 1 banana (designated by 0, 1, 2 in perm[*])

card=[2,1,1]

def test():
  initpermsys()
  for i in range(nperm):
    findperm(i,perm,card,cardsub,scard,nperm)
    permindex=findindex(perm,card,cardsub,scard,nperm)
    print(i,perm,permindex)
    if i!=permindex:
      print("programming error:",i,permindex)
      exit(1)
  return

print("Test of the code for the general case")
test()
print()



################################################################################



# Appendix.

# This appendix contains the much simpler coding of the special case where there
# are only two different kinds of objects.


import math


def comb(n1,n2):
  return(math.factorial(n1+n2)//(math.factorial(n1)*math.factorial(n2)))


def perm(z,n1,n2):
  global gg
  if n1==0 or n2==0:
# If no more alternatives are possible, the prefix determined so far is complete
# and we can add the rest.
    gg+=n1*[0]+n2*[1]
    return
  ff=comb(n1-1,n2)
  if z < ff:
    gg+=[0]
    perm(z,n1-1,n2)
  else:
    gg+=[1]
    perm(z-ff,n1,n2-1)
  return


# Let there be n1 objects denoted by 0 and n2 objects denoted by 1. Their
# permutations are indexed starting from 0. This function returns the
# permutation having the index idx.

def permutation(idx,n1,n2):
  global gg
  gg=[]
  perm(idx,n1,n2)
  return(gg)


# Given a permuation u (of n1 objects 0 and n2 objects 1), this fuction returns
# its index.

def index(u,n1,n2):
  if n1==0 or n2==0:
    return(0)
  if u[0]==0:
    return(index(u[1:],n1-1,n2))
  else:
    return(comb(n1-1,n2)+index(u[1:],n1,n2-1))


# For testing.

def proc(n1,n2):
  h=comb(n1,n2)
  print("Valid range of permutation index value: 0 ..",h-1)
  for idx in range(h):
    u=permutation(idx,n1,n2)
    print(idx,u,index(u,n1,n2))
  return


# Test.

print("Test of the code for the special case")
proc(2,3)



#################################################################################



# Epilouge


# It may be mentioned that an algorithm to generate permutations of n digits
# 1, 2, ..., n lexicographically is given by the present author in a paper
# On the Generation of Permutations and Combinations, BIT 2 (1962), pp.228-221.
# Any set of n objects with an ordering can of course be similarly treated, i.e.
# the algorithm is general. (The reference appears to be relatively unknown.)



Return to main page