如何最大程度地划分集合？

Question

我正在尝试解决欧拉计划问题之一。因此，我需要一种算法来帮助我以任意顺序找到集合中所有可能的分区。

例如，给定集合2 3 3 5：

2 | 3 3 5
2 | 3 | 3 5
2 | 3 3 | 5
2 | 3 | 3 | 5
2 5 | 3 3

等等。几乎该组成员的所有可能组合。当然，我已经在网上搜索过，但没有找到太多对我直接有用的东西，因为我说的是程序员的语言而不是高级数学的语言。

谁能帮我解决这个问题吗？我几乎可以阅读任何编程语言，从 BASIC 到 Haskell，所以可以用你想要的任何语言发布。

Answer 1

我很快编写了一些代码来做到这一点。然而，我遗漏了分隔给定列表的每种可能的组合，因为我不确定它是否确实需要，但如果需要的话，它应该很容易添加。

无论如何，代码在少量情况下运行得很好，但是，正如 CodeByMoonlight 已经提到的，可能性的数量变得非常高非常快，因此运行时间相应增加。

无论如何，这是 python 代码：

import time

def separate(toseparate):
  "Find every possible way to separate a given list."
  #The list of every possibility
  possibilities = []
  n = len(toseparate)
  #We can distribute n-1 separations in the given list, so iterate from 0 to n
  for i in xrange(n):
    #Create a copy of the list to avoid modifying the already existing list
    copy = list(toseparate)
    #A boolean list indicating where a separator is put. 'True' indicates a separator
    #and 'False', of course, no separator.
    #The list will contain i separators, the rest is filled with 'False'
    separators = [True]*i + [False]*(n-i-1)
    for j in xrange(len(separators)):
      #We insert the separators into our given list. The separators have to
      #be between two elements. The index between two elements is always
      #2*[index of the left element]+1.
      copy.insert(2*j+1, separators[j])
    #The first possibility is, of course, the one we just created
    possibilities.append(list(copy))
    #The following is a modification of the QuickPerm algorithm, which finds
    #all possible permutations of a given list. It was modified to only permutate
    #the spaces between two elements, so it finds every possibility to insert n
    #separators in the given list.
    m = len(separators)
    hi, lo = 1, 0
    p = [0]*m
    while hi < m:
      if p[hi] < hi:
        lo = (hi%2)*p[hi]
        copy[2*lo+1], copy[2*hi+1] = copy[2*hi+1], copy[2*lo+1]
        #Since the items are non-unique, some possibilities will show up more than once, so we
        #avoid this by checking first.
        if not copy in possibilities:
          possibilities.append(list(copy))
        p[hi] += 1
        hi = 1
      else:
        p[hi] = 0
        hi += 1
  return possibilities

t1 = time.time()
separations = separate([2, 3, 3, 5])
print time.time()-t1
sepmap = {True:"|", False:""}
for a in separations:
  for b in a:
    if sepmap.has_key(b):
      print sepmap[b],
    else:
      print b,
  print "\n",

它基于 QuickPerm 算法，您可以在此处阅读更多相关信息： QuickPerm

基本上，我的代码生成一个包含 n 个分隔的列表，将它们插入到给定列表中，然后在列表中查找分隔的所有可能排列。

因此，如果我们使用您的示例，我们将得到：

2  3  3  5 
2 | 3  3  5 
2  3 | 3  5 
2  3  3 | 5 
2 | 3 | 3  5 
2  3 | 3 | 5 
2 | 3  3 | 5 
2 | 3 | 3 | 5 

在 0.000154972076416 秒内。

但是，我通读了您正在做的问题的问题描述，并且了解了您如何尝试解决这个问题，但是看到运行时间增加的速度，我认为它不会像您期望的那样快。请记住，欧拉计划的问题应该在一分钟左右就能解决。

Answer 2

你考虑过搜索树吗？每个节点代表对放置元素的位置的选择，叶节点是答案。我不会给你代码，因为这是欧拉项目的乐趣的一部分；）

Answer 3

请查看：

计算机编程艺术，第 4 卷，分册 3：生成所有组合和分区

7.2.1.5。生成所有设置分区

Answer 4

一般来说，我会查看用于计算配置数量的递归结构，并构建一个类似的递归来枚举它们。最好的方法是计算整数和配置之间的一对一映射。这对于排列、组合等非常有效，并确保每个配置仅枚举一次。

现在，即使是 某些相同项的分区数的递归 也相当复杂的。

对于多重集的划分，计数相当于解决Project Euler Problem 181 到任意多重集。

Answer 5

嗯，问题有两个方面。

首先，项目可以按任何顺序排列。所以对于 N 个项目，有 N 个！排列（假设这些项目被视为唯一）。
其次，您可以将分组想象为每个项目之间指示划分的位标志。这些标志将有 N-1 个，因此对于给定的排列，将有 2^(N-1) 种可能的分组。
这意味着对于 N 个项目，总共会有 N!*(2^(N-1)) 种分组/排列，而且它会变得非常非常快。

在您的示例中，前四项是一种排列的分组。最后一项是另一个排列的分组。您的商品可以查看为：

2 on 3 off 3 off 5
2上3上3下5
2上3下 3上5
2对3对3对5
2 off 5 on 3 off 3

排列（显示顺序）可以通过像树一样查看它们来导出，正如其他两个所提到的。这几乎肯定会涉及递归，例如此处。
该分组在许多方面独立于它们。获得所有排列后，如果需要，您可以将它们与分组链接起来。

Answer 6

这是解决这部分问题所需的代码：

def memoize(f):
    memo={}
    def helper(x):
        if x not in memo:
            memo[x]=f(x)
        return memo[x]
    return helper

@memoize
def A000041(n):
    if n == 0: return 1
    S = 0
    J = n-1
    k = 2
    while 0 <= J:
        T = A000041(J)
        S = S+T if k//2%2!=0 else S-T
        J -= k if k%2!=0 else k//2
        k += 1
    return S

print A000041(100) #the 100's number in this series, as an example