生成唯一排列列表

Question

假设我有一个包含 3 个符号的列表：

l:`s1`s2`s3

生成以下 n*(n+1)/2 个排列列表的 q 方式是什么？

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

这可以看作是在相关矩阵的上下文中，我想要相关矩阵的所有上三角部分，包括对角线。

当然我的初始列表的大小会超过3，所以我想要一个通用的函数来执行这个操作。

我知道如何生成对角线元素：

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

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

但是我不知道如何生成非对角线元素。

Answer 1

我会尝试下面的代码

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

它

cross 生成所有 (s_i, s_j) 对
asc each 按索引对每对进行排序，因此 `s3`s1 变为 `s1`s3
distinct 删除重复项

不是最有效的方法，非常短。

Answer 2

如果我理解这个问题（如果我遗漏了什么，请道歉）。下面应该给你你要找的东西

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

Answer 3

您可能会发现有用的另一个解决方案：

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

这使用 scan accumulator 创建符号列表的列表，每个符号列表删除第一个元素：

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

需要额外的 -1_，因为扫描最后也会 return 一个空列表。然后使用 each-right 和 each:

将列表中的每个元素加入到这个结果中

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

最后使用 raze 得到不同的排列。

编辑：也可以使用

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

根本不需要扫描，并且在性能方面与扫描解决方案非常相似！

生成唯一排列列表

Generate a list of unique permutations

permutation

kdb