CODEWITHSUNDEEP
permutationkdb+
JejeBelfort
JejeBelfort

Reputation: 1663

Generate a list of unique permutations

Say I have a list of 3 symbols : 

l:`s1`s2`s3

What is the q-way to generate the following list of n*(n+1)/2 permutations?

(`s1;`s1),(`s1;`s2),(`s1;`s3),(`s2;`s2),(`s2;`s3),(`s3;`s3)

This can be seen as in the context of correlation matrix, where I want all the upper triangular part of the correlation matrix, including the diagonal.

Of course the size of my initial list will exceed 3, so I would like a generic function to perform this operation.

I know how to generate the diagonal elements:

q) {(x,y)}'[l;l]

(`s1`s1;`s2`s2;`s3`s3)

But I don't know how to generate the non-diagonal elements.

Upvotes: 3

Views: 419

Answers (3)

Eliot Robinson
Eliot Robinson

Reputation: 666

Another solution you might find useful:

q)l
`s1`s2`s3
q){raze x,/:'-1_{1_x}\[x]}l
s1 s1
s1 s2
s1 s3
s2 s2
s2 s3
s3 s3

This uses the scan accumulator to create a list of lists of symbols, with each dropping the first element:

q)-1_{1_x}\[l]
`s1`s2`s3
`s2`s3
,`s3

The extra -1_ is needed since the scan will also return an empty list at the end. Then join each element of the list onto this result using an each-right and an each:

{x,/:'-1_{1_x}\[x]}l
(`s1`s1;`s1`s2;`s1`s3)
(`s2`s2;`s2`s3)
,`s3`s3

Finally use a raze to get the distinct permutations.

EDIT: could also use 

q){raze x,/:'til[count x]_\:x}l
s1 s1
s1 s2
s1 s3
s2 s2
s2 s3
s3 s3

which doesnt need the scan at all and is very similar to the scan solution performance-wise!

Upvotes: 2

Anton Dovzhenko
Anton Dovzhenko

Reputation: 2569

I would try below code

{distinct asc each x cross x}`s1`s2`s3

It

  • cross generates all (s_i, s_j) pairs
  • asc each sorts every pair by index, so `s3`s1 becomes `s1`s3
  • distinct removes duplicates

Not the most efficient way by very short one.

Upvotes: 1

Dunny
Dunny

Reputation: 170

If I am understanding the question (apologies if I have missed something). Below should give you what you are looking for

q)test:`s1`s2`s3`s4`s5
q)(til cnt) _' raze (-1+cnt:count test)cut test,'/:test
(`s1`s1;`s2`s1;`s3`s1;`s4`s1;`s5`s1)
(`s2`s2;`s3`s2;`s4`s2;`s5`s2)
(`s3`s3;`s4`s3;`s5`s3)
(`s4`s4;`s5`s4)
,`s5`s5

Upvotes: 0

Related Questions