Define a (k,n)-choice to be an ordered subset of k elements from a set of n elements and a (k,n)-combination to be an unordered subset of k elements from a set of n elements, than the question (see (*0) below) naturally arises: What is the index of a (k,n)-combination in the lexicographically ordered set of (k,n)-choices?
Let cmb generates all (k,n)-combinations (see also (*1) below): cmb=: [:,.^:(2>[EMAIL PROTECTED])@; [:(,.&.><@;\.)/ >:@[EMAIL PROTECTED] and chs all (k,n)-choices, see http://www.jsoftware.com/pipermail/programming/2008-August/011683.html chs=: 4 : ';(,/@:(([,. ]+ <:)"0 _) )&.>/ (<i.1 0),~ i.&.>x{.(-i.)y' Example: |:2 chs 5 NB. (2,5)-choices in columns 0 0 0 0 1 1 1 1 2 2 2 2 3 3 3 3 4 4 4 4 1 2 3 4 0 2 3 4 0 1 3 4 0 1 2 4 0 1 2 3 |:2 cmb 5 NB. (2,5)-combinations in columns 0 0 0 0 1 1 1 2 2 3 1 2 3 4 2 3 4 3 4 4 Indexes of second in first: 0 1 2 3 5 6 7 10 11 15 Straightforward the following works: A1=: 4 : '(x{.(-i.)y) #. (-({:+/@:>}:)\)"1 x cmb y' Although it is no (mathematical) proof, correctness is suggested by: ((>:@i.) (cmb-: A1{chs)"0 ])10 1 1 1 1 1 1 1 1 1 1 However, a solution based on the method used in cmb appeared to be much more efficient than A1: A0=: [:; [:(+&.><@;\.)/ >:@-~ ({. (*"1 0 (1 */\.@|.@, ])) }.) [EMAIL PROTECTED] ((>:@i.) (cmb-: A0{chs)"0 ])10 1 1 1 1 1 1 1 1 1 1 Of course, A0 is much more efficient: 5 ts'((>:@i.) A1"0 ])15' 0.3413993 1790464 5 ts'((>:@i.) A0"0 ])15' 0.0029998221 1426176 If a (k,n)-choice has index j (in the set of all (k,n)-choices), then this (k,n)-choice appears for the first time in permutation (j*!n-k) A. i.n as is shown by: (['j k n'=: 130 3 7); (j{k chs n);((j*!n-k) A. i.n) +-------+-----+-------------+ |130 3 7|4 2 0|4 2 0 1 3 5 6| +-------+-----+-------------+ Now this can be used in answering the question What is the index of an equal sized partition in the lexicographically ordered set of all permutations? >From http://www.jsoftware.com/pipermail/programming/2008-July/011482.html EqPrts=: 4 : '(-y%x)<\"1 ,/"3^:([EMAIL PROTECTED]) (y%x) ep i.y' you get A. ;"1 [2 EqPrts 6 0 6 12 18 30 36 42 60 66 90 but also 2 EPinA 6 0 6 12 18 30 36 42 60 66 90 with EPinA=: 4 : 0 NB. A0 is required t=. y%x ,/^:_ ((-t) */\|.>:i.y) #. 0,"1~> { t <@A0&<:"0 }: t* (-i.)x ) It goes without saying that EPinA is much more efficient R.E. Boss (*0) Actually, this question came up in solving the problem of the equally sized subsets, cf. http://www.jsoftware.com/pipermail/programming/2008-July/011431.html . (*1) A remark on comb, the (famous) verb to produce all (k,n)-combinations, cf. http://www.jsoftware.com/jwiki/Essays/Combinations . After my discovery of the more efficient comb1 in http://www.jsoftware.com/pipermail/programming/2007-August/007819.html I found an even more efficient and far more elegant solution comb3 in http://www.jsoftware.com/pipermail/programming/2008-January/009488.html . Since comb3 had the same problem as Miller noted for chs in http://www.jsoftware.com/pipermail/programming/2008-August/011585.html a simple adjustment was made and I renamed it to cmb: cmb=:[:,.^:(2>[EMAIL PROTECTED])@; [:(,.&.><@;\.)/ >:@[EMAIL PROTECTED] ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
