permutations

Community Support
1

Does Q have any inbuilt functions for getting the permutations of a list?

2

Do you want “all” permutations, or “some”?

For all, here’s something (by Arthur):

q)g:{[N;l]$[N=1;l;raze .z.s[N-1;l]{x,/:y except x}:l]}
q)g[3;`a`b`c]
a b c
a c b
b a c
b c a
c a b
c b a
q)

For “some”:

q)v@(neg a)?a:count v: abc acb
q)v@(neg a)?a:count v: abc cba
q)

3

> For all, here’s something (by Arthur):

Forgive me, I’m about to get zapped and banished, try this:? {$[x=1;y;raze .z.s[x-1;y]{x,/:y except x}:y]}

4

I did something like this, which includes “smaller” variants:

s:ab
v:s@{:[x v
(a<br> b
b a
b b)

Regards,

5

Thanks for the responses exactly what I was after

6

?q)t:abcd

/borrow arthur’s code:

q)s:{neg#flip 0b vs/:til prd x#2}

q)t where@'1_flip s count t

,`d

,`c

cd

,`b

bd

bc

bc`d

,`a

ad

ac

ac`d

ab

ab`d

ab`c

abcd

Regards,

Xi

7

Isn’t this creating a powerset?<o:p></o:p>

<o:p> </o:p>

From: personal-kdbplus@googlegroups.com [mailto:personal-kdbplus@googlegroups.com] On Behalf Of Xi Chen
Sent: Wednesday, November 23, 2011 3:13 AM
To: personal-kdbplus@googlegroups.com
Subject: Re: [personal kdb+] permutations<o:p></o:p>

<o:p> </o:p>

 q)t:abcd<o:p></o:p>

/borrow arthur’s code:<o:p></o:p>

q)s:{neg#flip 0b vs/:til prd x#2}<o:p></o:p>

q)t where@'1_flip s count t<o:p></o:p>

,`d<o:p></o:p>

,`c<o:p></o:p>

cd<o:p></o:p>

,`b<o:p></o:p>

bd<o:p></o:p>

bc<o:p></o:p>

bc`d<o:p></o:p>

,`a<o:p></o:p>

ad<o:p></o:p>

ac<o:p></o:p>

ac`d<o:p></o:p>

ab<o:p></o:p>

ab`d<o:p></o:p>

ab`c<o:p></o:p>

abcd<o:p></o:p>

<o:p> </o:p>

Regards,<o:p></o:p>

Xi<o:p></o:p>

On 22 November 2011 01:08, Don Nguyen <don@unswrc.com> wrote:<o:p></o:p>

Does Q have any inbuilt functions for getting the permutations of a list?

–
Submitted via Google Groups

8

yep, play around s function you can get combination and permutation.

Xi

9

Regarding the following permutations function

perms: {$[x=1;y;raze .z.s[x-1;y]{x,/:y except x}:y]}

How would I modify to handle repeat cases?  For example

perms[4; 1 2 3 4]

Works perfectly however

perms[4; 1 2 3 3]

Returns nothing.  I have tried replacing

y except x 

with

y _ (y?x)

But I keep getting an error.

10

distinct<o:p></o:p>

<o:p> </o:p>

From: personal-kdbplus@googlegroups.com [mailto:personal-kdbplus@googlegroups.com] On Behalf Of Don Nguyen
Sent: Monday, November 28, 2011 3:05 PM
To: personal-kdbplus@googlegroups.com
Subject: Re: [personal kdb+] permutations<o:p></o:p>

<o:p> </o:p>

Regarding the following permutations function<o:p></o:p>

<o:p> </o:p>

perms: {$[x=1;y;raze .z.s[x-1;y]{x,/:y except x}:y]}<o:p></o:p>

<o:p> </o:p>

How would I modify to handle repeat cases?  For example<o:p></o:p>

<o:p> </o:p>

perms[4; 1 2 3 4]<o:p></o:p>

<o:p> </o:p>

Works perfectly however<o:p></o:p>

<o:p> </o:p>

perms[4; 1 2 3 3]<o:p></o:p>

<o:p> </o:p>

Returns nothing.  I have tried replacing<o:p></o:p>

<o:p> </o:p>

y except x <o:p></o:p>

<o:p> </o:p>

with<o:p></o:p>

<o:p> </o:p>

y _ (y?x)<o:p></o:p>

<o:p> </o:p>

But I keep getting an error.<o:p></o:p>

<o:p> </o:p>

On Tue, Nov 22, 2011 at 4:39 PM, Rohit Tripathi <rohit.x.tripathi@gmail.com> wrote:<o:p></o:p>

> For all, here’s something (by Arthur):<o:p></o:p>

Forgive me, I’m about to get zapped and banished, try this:  {$[x=1;y;raze .z.s[x-1;y]{x,/:y except x}:y]}<o:p></o:p>

On Tue, Nov 22, 2011 at 10:39 AM, Rohit Tripathi <rohit.x.tripathi@gmail.com> wrote:<o:p></o:p>

Do you want “all” permutations, or “some”?

<o:p></o:p>

q)g:{[N;l]$[N=1;l;raze .z.s[N-1;l]{x,/:y except x}:l]}
q)g[3;`a`b`c]
a b c
a c b
b a c
b c a
c a b
c b a
q)

For “some”:

q)v@(neg a)?a:count v: abc acb
q)v@(neg a)?a:count v: abc cba
q)<o:p></o:p>

<o:p></o:p>

On Tue, Nov 22, 2011 at 6:38 AM, Don Nguyen <don@unswrc.com> wrote:<o:p></o:p>

Does Q have any inbuilt functions for getting the permutations of a list?

–
Submitted via Google Groups

11

Apologies if this seems like excessive hand holding but where does distinct go?  I have tried

{$[x=1;y;raze .z.s[x-1;y]{x,/: distinct y}:y]}[4;1 2 3 3]

But this produces 1 1 1 1 among others which is not really a permutation.  I have tried hard to break down the code myself but I can’t understand what it means to have the recursive function

.z.s[x-1;y]

Followed immediately by the lambda

{x,/: distinct y}

12

Hi Don,

You could just permute the underlying indices. Is this the kind of thing you want?

Andrew?

q){y@/:perms[x;til count y]}[4;1 2 3 3]

1 2 3 3

1 2 3 3

1 3 2 3

1 3 3 2

1 3 2 3

1 3 3 2

2 1 3 3

2 1 3 3

2 3 1 3

2 3 3 1

2 3 1 3

2 3 3 1

3 1 2 3

3 1 3 2

3 2 1 3

3 2 3 1

3 3 1 2

3 3 2 1

3 1 2 3

3 1 3 2

3 2 1 3

3 2 3 1

3 3 1 2

3 3 2 1

13

Hi Andrew, yes it is.  Clever solution thank you

14

I was only on my way out and when I glimpsed at your post, the one word I managed to type before the keyboard was yanked away from my pious hands was the word “distinct”<o:p></o:p>

<o:p> </o:p>

From: personal-kdbplus@googlegroups.com [mailto:personal-kdbplus@googlegroups.com] On Behalf Of Don Nguyen
Sent: Monday, November 28, 2011 3:31 PM
To: personal-kdbplus@googlegroups.com
Subject: Re: [personal kdb+] permutations<o:p></o:p>

<o:p> </o:p>

Apologies if this seems like excessive hand holding but where does distinct go?  I have tried<o:p></o:p>

<o:p> </o:p>

{$[x=1;y;raze .z.s[x-1;y]{x,/: distinct y}:y]}[4;1 2 3 3]<o:p></o:p>

<o:p> </o:p>

But this produces 1 1 1 1 among others which is not really a permutation.  I have tried hard to break down the code myself but I can’t understand what it means to have the recursive function<o:p></o:p>

<o:p> </o:p>

.z.s[x-1;y]<o:p></o:p>

<o:p> </o:p>

Followed immediately by the lambda<o:p></o:p>

<o:p> </o:p>

{x,/: distinct y}<o:p></o:p>

<o:p> </o:p>

<o:p> </o:p>

On Mon, Nov 28, 2011 at 8:39 PM, Tripathi, Rohit <rohit.tripathi@capgemini.com> wrote:<o:p></o:p>

distinct<o:p></o:p>

 <o:p></o:p>

From: personal-kdbplus@googlegroups.com [mailto:personal-kdbplus@googlegroups.com] On Behalf Of Don Nguyen
Sent: Monday, November 28, 2011 3:05 PM<o:p></o:p>

To: personal-kdbplus@googlegroups.com
Subject: Re: [personal kdb+] permutations<o:p></o:p>

 <o:p></o:p>

Regarding the following permutations function<o:p></o:p>

 <o:p></o:p>

perms: {$[x=1;y;raze .z.s[x-1;y]{x,/:y except x}:y]}<o:p></o:p>

 <o:p></o:p>

How would I modify to handle repeat cases?  For example<o:p></o:p>

 <o:p></o:p>

perms[4; 1 2 3 4]<o:p></o:p>

 <o:p></o:p>

Works perfectly however<o:p></o:p>

 <o:p></o:p>

perms[4; 1 2 3 3]<o:p></o:p>

 <o:p></o:p>

Returns nothing.  I have tried replacing<o:p></o:p>

 <o:p></o:p>

y except x <o:p></o:p>

 <o:p></o:p>

with<o:p></o:p>

 <o:p></o:p>

y _ (y?x)<o:p></o:p>

 <o:p></o:p>

But I keep getting an error.<o:p></o:p>

 <o:p></o:p>

On Tue, Nov 22, 2011 at 4:39 PM, Rohit Tripathi <rohit.x.tripathi@gmail.com> wrote:<o:p></o:p>

> For all, here’s something (by Arthur):<o:p></o:p>

Forgive me, I’m about to get zapped and banished, try this:  {$[x=1;y;raze .z.s[x-1;y]{x,/:y except x}:y]}<o:p></o:p>

On Tue, Nov 22, 2011 at 10:39 AM, Rohit Tripathi <rohit.x.tripathi@gmail.com> wrote:<o:p></o:p>

Do you want “all” permutations, or “some”?<o:p></o:p>

q)g:{[N;l]$[N=1;l;raze .z.s[N-1;l]{x,/:y except x}:l]}
q)g[3;`a`b`c]
a b c
a c b
b a c
b c a
c a b
c b a
q)

For “some”:

q)v@(neg a)?a:count v: abc acb
q)v@(neg a)?a:count v: abc cba
q)<o:p></o:p>

<o:p> </o:p>

On Tue, Nov 22, 2011 at 6:38 AM, Don Nguyen <don@unswrc.com> wrote:<o:p></o:p>

Does Q have any inbuilt functions for getting the permutations of a list?

–
Submitted via Google Groups

15

Though not the need of the hour, I was browsing the archives. 

and here is my solution :perm:{[s] $[(count s)=1;s;[p:(rotate[1])s;raze((string first each p),/:'perm each 1_/:p)]]}

16

a: 1 8 5 4 9 2

/ get the combaination first, somehow i cannot get the Convert func working, so i use Last of Iterate, do you guys know how to fix this?

comb : last a cross \ (-1+count a)#enlist(a)
/ reduce from combination to permutation

perm : comb where (count a)=count each distinct each comb

?

I cannot figure out how to get? permuation in one go. Above approach doesn’t work for large list