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
Ignoring the question about efficiency, wouldn’t changing {x,/:y except x} to {x,/:y where y>max x} be sufficient?
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/
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
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:ab`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.
fyi, most of the work can be done in
{raze count(x cross)\x} l
but we have to add checks into to avoid 1 cross 1 for example…
q)f:{foo where {distinct~x} each raze each foo:raze count(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