Welcome Guest [Log In] [Register]
Welcome to Crypto. We hope you enjoy your visit.


You're currently viewing our forum as a guest. This means you are limited to certain areas of the board and there are some features you can't use. If you join our community, you'll be able to access member-only sections, and use many member-only features such as customizing your profile, sending personal messages, and voting in polls. Registration is simple, fast, and completely free.


Join our community!


If you're already a member please log in to your account to access all of our features:

Username:   Password:
Add Reply
Indexing permutations with repeated elements
Topic Started: Mar 25 2014, 05:18 PM (212 Views)
mok-kong shen
NSA worthy
[ *  *  *  *  *  * ]
Code:
 
#[space]Indexing[space]permutations[space]with[space]repeated[space]elements.


#[space]Prologue.

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

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

#[space]In[space]steganography[space]one[space]could[space]arrange[space]to[space]have[space]in[space]a[space]picture[space]certain[space]objects[space]be
#[space]ordered[space]in[space]a[space]way[space]such[space]that[space]their[space]permutation[space]index[space]serves[space]to[space]inconspicuously
#[space]transmit[space]a[space]number[space]to[space]the[space]recipient.[space]See
#[space]http://s13.zetaboards.com/Crypto/topic/7173275/1/[space]for[space]similar[space]methods.

#[space]The[space]code[space]for[space]the[space]special[space]case[space]of[space]2[space]kinds[space]of[space]elements[space]is[space]given[space]in[space]the[space]Appendix
#[space]further[space]below.

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


#[space]Version[space]1.0,[space]released[space]on[space]25.03.2014.

#[space]Code[space]lines[space]of[space]documents[space]with[space]the[space]same[space]version[space]number[space]are[space]always[space]identical.
#[space]There[space]may[space]be[space]interim[space]modifications[space]of[space]comment[space]lines.[space]The[space]most[space]recent[space]document
#[space]of[space]this[space]software[space]can[space]be[space]obtained[space]from:
#[space]http://s13.zetaboards.com/Crypto/topic/7174259/1/

#[space]Email[space]address[space]of[space]the[space]author:[space]mok-kong.shen@t-online.de



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



import[space]math


def[space]fac(n):
[space][space]return(math.factorial(n))


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


#[space]Initialization.[space]User[space]has[space]to[space]define[space]card.

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


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


#[space]Given[space]an[space]index[space]permindex,[space]find[space]the[space]corresponding[space]permutation.

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


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


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


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

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



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



#[space]Test[space]program.

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

card=[2,1,1]

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

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



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



#[space]Appendix.

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


import[space]math


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


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


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

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


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

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


#[space]For[space]testing.

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


#[space]Test.

print("Test[space]of[space]the[space]code[space]for[space]the[space]special[space]case")
proc(2,3)
Edited by mok-kong shen, Apr 5 2014, 03:34 PM.
Offline Profile Quote Post Goto Top
 
1 user reading this topic (1 Guest and 0 Anonymous)
« Previous Topic · General · Next Topic »
Add Reply