- Posts:
- 1,874
- Group:
- Members
- Member
- #3,310
- Joined:
- December 12, 2009
|
- 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)
|