按顺序生成列表的所有分区的算法

Question

我需要一种逃避我的特殊形式的“设置”分区，因为它不是很分区。或者更确切地说，它是特定列表的所有分区的子集，可以保持原始顺序。

我按特定顺序列出了n个元素。[a,b,c,...,n]

我需要获取保持顺序的所有分区离散变量。

因此，对于四个元素，结果将是：

[{a,b,c,d}]
[{a,b,c},{d}]
[{a,b},{c,d}]
[{a,b},{c},{d}]
[{a},{b,c,d}]
[{a},{b,c},{d}]
[{a},{b},{c,d}]
[{a},{b},{c},{d}]

---

我需要这样做，以便在必须保持其顺序的列表中生成所有可能的标记分组，以便在更广泛的模式匹配算法中使用。

我发现只有一个，涉及到这个问题的其他问题在这里，但它的红宝石。因为我不了解该语言，所以好像有人将代码放入混合器中，并且不会特别想为了解密算法而学习某种语言，我觉得我没有选择的余地。

我已经尝试了很多次以数学方式进行计算，结果越来越痛苦。我以为我会通过生成分区列表并以不同的方式对其进行遍历而变得越来越近，但是每个元素的数量都需要不同的“模式”进行迭代，因此我不得不手动进行调整。

我无法知道可能有多少个元素，而且我不想在处理过程中加人为限制，以将其限制为仅调整到一起的大小。

Answer 1

您可以考虑以下问题：每个所需分区的特征是0到2 ^（n-1）之间的整数。这样的数字的二进制表示中的每个1对应于两个连续数字（例如，

 a b|c|d e|f
  0 1 1 0 1

所以数字01101对应于分区{a,b},{c},{d,e},{f}。要从已知的分区号生成分区，请在列表中循环并在设置相应位时切出一个新的子集。

通过阅读时尚的功能编程风格的Ruby示例，我可以理解您的痛苦。如果有帮助，这是Python中的完整示例。

array = ['a', 'b', 'c', 'd', 'e']
n = len(array)

for partition_index in range(2 ** (n-1)):

    # current partition, e.g., [['a', 'b'], ['c', 'd', 'e']]
    partition = []

    # used to accumulate the subsets, e.g., ['a', 'b']
    subset = []

    for position in range(n):

        subset.append(array[position])

        # check whether to "break off" a new subset
        if 1 << position & partition_index or position == n-1:
            partition.append(subset)
            subset = []

    print partition