我正在尝试解决 Project Euler 问题之一。因此，我需要一种算法来帮助我以任何顺序找到集合中所有可能的分区。
例如，给定集合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，所以可以用任何你喜欢的语言发帖。
你考虑过搜索树吗？每个节点将代表放置元素的位置的选择，叶节点是答案。我不会给你代码，因为那是 Project Euler 乐趣的一部分；）
一般来说，我会查看用于计算配置数量的递归结构，并构建一个类似的递归来枚举它们。最好的方法是计算整数和配置之间的一对一映射。这适用于排列、组合等，并确保每个配置仅枚举一次。
现在甚至一些相同项目的分区数的递归也相当复杂。
对于多重集的分区，计数相当于解决Project Euler 问题 181对任意多重集的推广。
这是解决这部分问题所需的代码：
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
嗯，这个问题有两个方面。
首先，项目可以按任何顺序排列。所以对于 N 个项目，有 N! 排列（假设项目被视为唯一）。
其次，您可以将分组设想为每个项目之间的位标志，指示划分。这些标志中有 N-1 个，因此对于给定的排列，将有 2^(N-1) 个可能的分组。
这意味着对于 N 个项目，总共会有 N!*(2^(N-1)) 个分组/排列，它变得非常非常快。
在您的示例中，前四项是一个排列的分组。最后一项是另一个排列的分组。您的项目可以被视为：
2 开 3 关 3 关 5
2 开 3 开 3 关 5
2 开 3 关 3 开 5
2 开 3 开 3 开 5
2 关 5 开 3 关 3
排列（显示顺序）可以通过将它们视为一棵树来得出，正如其他两个所提到的。这几乎肯定会涉及递归，例如这里。分组在许多方面独立于它们。获得所有排列后，如果需要，您可以将它们与分组链接。
我迅速编写了一些代码来执行此操作。但是，我没有将给定列表的所有可能组合分开，因为我不确定它是否真的需要，但如果需要，它应该很容易添加。
无论如何，少量代码运行得很好，但是，正如 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 秒内。
但是，我通读了您正在做的问题的问题描述，我看到了您是如何尝试解决这个问题的，但是看到运行时间增加的速度有多快，我认为它不会像您期望的那样快速工作。请记住，Project Euler 的问题应该在大约一分钟内解决。