# 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.)