How to implement combinations of a list

[Roy Liu]

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

[Yan Yan]

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/

[Flying]

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

On Wednesday, April 1, 2015 at 7:06:14 AM UTC+8, Roy wrote:

[joebo]

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

[Roy Liu]

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.

--

You received this message because you are subscribed to the Google Groups "Kdb+ Personal Developers" group.
To unsubscribe from this group and stop receiving emails from it, send an email to personal-kdbpl...@googlegroups.com.
To post to this group, send email to personal...@googlegroups.com.
Visit this group at http://groups.google.com/group/personal-kdbplus.
For more options, visit https://groups.google.com/d/optout.

[Sean O'Hagan]

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

[José Pablo Cambronero]

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