[Jprogramming] Choosing k items out of n

[R.E. Boss]

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 ((i.@! 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=: i.@! A. i.

   10 (chs-: tap@]) 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