17

给定输入数组

[a,b,c,d,e]

和一个“加入”功能(a,b) => (a+b)

我的代码返回以下数组数组，其中包含通过将连接函数应用于各种元素对同时保持顺序而获得的每个可能的变化：

[
  [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], ...]

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

描述非相邻元素分区的图表

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

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

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

4

5 回答 5

5

After your edit - these are all partitions of an array (and their count is 2^(n-1), because you can replace any divider(colon) by joiner(+)).

Note - these are array partitions, not set partitions.

于 2013-04-16T14:30:43.093 回答
5

正如 mbeckish 在评论中所说，这些集合（一旦原始集合上的顺序固定）同构于顺序相关的整数分区，这显然通常被称为composition。每组恰好有 2 n-1 个组合。对于每个1≤ k≤ n，都有元素组成(n-1) choose (k-1)集合，保持你开始时集合的顺序。为了将其可视化，请考虑按顺序排列的集合中的元素以及按该顺序相邻的元素之间的空间；将您的示例视为. 您会注意到确实存在可能的边界。要创建 k-composition，您只需选择nkA|B|C|D|En-1k-1在那些可能的边界中，这可能是也可能不是您生成集合的方式。(n-1) choose (k-1)对kfrom1到nthen求和，我们得到 2 n-1作为可能组合的数量。

于 2013-04-16T17:02:10.457 回答
1

[张贴者的主要编辑使我的答案过时了，这是关于发布的原始问题：] 整数序列的在线百科全书将这些简短地提到为“区间子集”。（http://oeis.org/A000124）我会坚持这个，它很有描述性。

于 2013-04-16T11:42:53.543 回答
0

It's a directed tree that points away from the root node:

在此处输入图像描述

It's important to note that you do not declare the order of your sets important, only that order is maintained with each set. The python code to generate your "partitions" via your "join":

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')
于 2013-04-16T15:16:52.120 回答
0

How about myArray.possibleChainings() or myArray.possibleLinkings() ?

The idea is that it looks like you are chaining or linking at least two elements together. I find it also intuitive because you cannot chain or link elements together which are not neighbors.

于 2013-04-16T15:17:59.533 回答