cancel
Showing results for 
Search instead for 
Did you mean: 

How to implement combinations of a list

James1
New Contributor
Hi, All

I need to get the combinations and permutations of a list.

A function have been implemented for permutations.
perm:{[N;l]$[N=1;l;raze .z.s[N-1;l]{x,/:y except x}\:l]}

However, I have no idea about combinations, just like this:

l: 1 2 3
comb[2;l]
1 2
1 3
2 3

l: 1 2 3 4
comb[3;l]
1 2 3
1 2 4
1 3 4
2 3 4

Thanks!
--
Roy
6 REPLIES 6

Flying
New Contributor III
Ignoring the question about efficiency, wouldn't changing {x,/:y except x} to {x,/:y where y>max x} be sufficient?

LamHinYan
New Contributor
I have NOT tested this
https://lifeisalist.wordpress.com/2009/09/21/p26-generate-the-combinations-of-k-distinct-objects-chosen-from-the-n-elements-of-a-list/

joebo
New Contributor
Searching for comb on the wiki found this:

comb:{m:x:key x;do[y-1;x:{raze{y,/:(1+max y)_x}[y]each x}[x;m]];x}; //permutations

q)(1 2 3)@comb[3;2]
1 2
1 3
2 3

q)(1 2 3 4)@comb[4;3]
1 2 3
1 2 4
1 3 4
2 3 4


[1] - http://code.kx.com/wiki/Contrib/DataMiner

James1
New Contributor
To Flying:
Your method is nice. I complete it as the following:

q)comb:{[N;l]$[N=1;l;raze .z.s[N-1;l]{x,/:y where y>max x}\:l]}
q)perm:{[N;l]$[N=1;l;raze .z.s[N-1;l]{x,/:y except x}\:l]}

q)l:`a`b`c
q)l@comb[2;til count l]
q)l@perm[2;til count l]

To YanYan:
I try this link. It's slow for the consequence of recursion.

sohagan
New Contributor
fyi, most of the work can be done in 

{raze count[x](x cross)\x} l

but we have to add checks into to avoid 1 cross 1 for example...

q)f:{foo where {distinct[x]~x} each raze each foo:raze count[x](x cross)\x}
q)f l  //will give the same results as your perm func
q)(l@raze perm[;til count l] each 1+ til count l)~f l
1b

To get the comb, you could ascend each and take the distinct records of the above results....

q)(l@asc each raze each raze comb[;til count l] each 1+til count l)~distinct asc each raze each f l
1b

HTH,
Sean

How about this? assumes you feed it a list of indices

q)combs:{[l;c] {raze y,/:'(1+last each y)_\:x}[l;]/[c-1;l]}

q)combs[til 4;2]

0 1

0 2

0 3

1 2

1 3

2 3

q)combs[til 4;3]

0 1 2

0 1 3

0 2 3

1 2 3

q)1 2 3 4 combs[til 4;3]

1 2 3

1 2 4

1 3 4

2 3 4