这个集合/数组操作有特定的名称吗？

Question

考虑输入数组

[a,b,c,d,e]

和一个 'join' 函数(a,b) => (a+b)

我的代码返回以下数组，包含应用 join 函数到不同元素对的所有可能变化，同时保持顺序：

[
  [a,b,c,d,e],
  [a,b+c,d,e],
  [a,b+c+d,e],
  [a,b,c+d,e],
  [a+b,c,d,e],
  [a+b,c+d,e],
  [a+b+c,d,e],
  [a+b+c+d,e],
  [a,b,c,d+e],
  [a,b+c,d+e],
  [a,b+c+d+e],
  [a,b,c+d+e],
  [a+b,c,d+e],
  [a+b,c+d+e],
  [a+b+c,d+e],
  [a+b+c+d+e],
]

在视觉上，我想做的是这样的：

代码可以工作，但我不知道该称呼它什么——如果这个操作已经存在一种名字，我希望使用其他开发人员熟悉的名称。它不是幂集，但它类似于幂集......这种特定的集合/数组操作有一个名字吗？

编辑：好的，它们不是排列；排列都是由不同顺序的5个元素数组组成的[[a,b,c,d,e], [e,d,c,b,a], [a,d,b,c,e], ...]

它们不是划分，因为任何子集只能包含输入中相邻的元素。换句话说，划分将允许这样的操作：

（这可能源于纯集合论没有有序集合的概念。）

它们不是组合，因为输出的每个元素恰好使用输入集的每个成员一次。

我认为myArray.OrderedPartitions((a,b) => (a+b))可能是一个合适的简洁和解释性的名称。

- Dylan Beattie

---

为什么 [a+b+c+d+e] 没有出现？ - Landei

@Landei 我的错误 :) 已经编辑问题，包括缺失的排列。 - Dylan Beattie

它们绝对不是任何类型的排列！排列的定义是重新排列相同项目集。然而，在这里，没有两个列表具有相同的项目。 - Elmar Peise

类似于受限分区，但是你只有一个基数大于1的组（即我看不到 [ a+b, c+d, e ]）。 - LSerni

我会称这为“依赖顺序的整数分割”。它基本等同于将一个数字写成多个整数之和的所有方法： 1+1+1+1+1 1+1+1+2 1+1+2+1 1+1+3 1+2+1+1 1+2+2 ... - mbeckish

Answer 1

在您的编辑之后，这些都是数组的分区（它们的数量为 2^(n-1)，因为您可以通过替换任何分隔符（冒号）来使用连接符（加号））。请注意- 这些是数组分区，而不是集合分区。

- MBo

Answer 2

正如mbeckish在评论中所说，那些集合（一旦确定原始集合的顺序）是同构于有序整数分割，显然通常称为组合。每个集合恰好有2^n-1种组合。对于每个 1 ≤ k ≤ n，恰好有 (n-1) choose (k-1) 种将 n 个元素分成 k 个集合的组合方式，并保留原始集合的顺序。为了直观理解，可以将集合的元素按顺序排列，并在相邻元素之间添加一个空格；将示例看作 A|B|C|D|E。你会注意到，恰好有 n-1 种可能的边界。要创建一个 k-组合，您只需要选择其中可能的边界之一，这可能与您生成集合的方法是否相同无关。将 k 从 1 到 n 的所有 (n-1) choose (k-1) 相加，就得到了2^n-1作为可能组合的数量。

- G. Bach

---

很好的解释。也许值得补充说明的是，总和等于2^(n-1)。 - rliu

它们似乎确实是组合物。谢谢 :) - Dylan Beattie

Answer 3

海因数列百科全书简要提到这些为“区间子集”。 (http://oeis.org/A000124) 我会坚持使用这个，它相当描述性。

- elias

---

我不会说它对于它正在做的事情有那么详细的描述（如果我看到这个名字，我不知道我会期望这个函数做什么 - 我可以看出在很多思考之后这个名字是如何适合的）。 - Chris

Answer 4

这是一个指向远离根节点的有向树：

需要注意的是，您不需要声明集合的顺序很重要，只需要保持每个集合的顺序即可。使用Python代码通过“join”生成“partitions”的方法如下：

A = map(list, list('abcde'))

def join(A):
    B = []
    for x1,x2 in zip(A,A[1:]):
        B.append((x1,x2,sorted(list(set(x1+x2)))))
    return B
def label(x):
    return '+'.join(x)

# Draw the graph with networkx
import networkx as nx
G = nx.DiGraph()

while len(A)>1:
    B = join(A)
    for x1,x2,pair in B:
        print label(x1), label(pair)
        G.add_edge(label(x1),label(pair))
        G.add_edge(label(x2),label(pair))
    A = [x[2] for x in B]

nx.write_dot(G,'test.dot')

# Render the graph to an image
import os
os.system('dot -Tpng test.dot > test.png')

- Hooked

Answer 5

如何使用myArray.possibleChainings()或者myArray.possibleLinkings()？

这个概念是看起来你正在将至少两个元素链接在一起。我认为这样也很直观，因为你不能将不相邻的元素链接在一起。

- Thorsten S.