There are n %&! n-k ways of choosing k items out of n .
Example for n=5 and k=2 , the 20 choices transposed:
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
The question is how to generate the choices in lexicographical order.
Since each choice is a permutation of an item of k comb n , a possible
solution is
chs1=: 4 : '/:~ ,/ |:"2 (([EMAIL PROTECTED] A. i.)x) { |:x comb y'
NB. /:~ is required for lexicographical order
|: 2 chs1 5
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
I found a more efficient and much more elegant way:
chs=: 4 : ';(,/@:(([,. ]+ <:)"0 _) )&.>/ |.<@i."0 (>:y-x)+i.x'
|: 2 chs 5
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
5 ts'6 chs 12'
0.21896923 71315968
5 ts'6 chs1 12'
0.59873691 1.428105e8
Notice that for k=n one gets all the permutations of i.n.
In http://www.jsoftware.com/help/dictionary/dacapdot.htm the table of all
permutations is generated by
tap=: [EMAIL PROTECTED] A. i.
10 (chs-: [EMAIL PROTECTED]) 10
1
Also here chs is more efficient:
ts'10 chs 10'
2.8916359 1.10731e9
ts'tap 10'
3.8993473 1.1156877e9
R.E. Boss
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
