我试图解决的项目欧拉问题之一。 因此，我需要一个算法，将帮助我找到了一组所有可能的分区，以任何顺序。
例如，给定一组2 3 3 5 ：
2 | 3 3 5
2 | 3 | 3 5
2 | 3 3 | 5
2 | 3 | 3 | 5
2 5 | 3 3
等等。 相当多的一组成员的每一个可能的组合。 我已经搜查过程中的净，但还没有找到太多这是我的直接有用的，因为我讲程序员ESE没有先进的数学偏东。
谁能帮我这个？ 我可以阅读几乎任何编程语言，从基础到Haskell的，所以在发布你想要的任何一种语言。
你有没有考虑搜索树？ 每个节点将代表在那里把一个元件与叶节点是答案选择。 我不会给你的代码，因为这是项目欧拉的乐趣的一部分;）
看一眼：
计算机程序设计，第4卷的艺术，分册3：生成所有组合和分区
7.2.1.5。 生成所有分区组
一般来说，我会看用来计算配置的数量的递归结构，并建立一个类似的递归枚举它们。 最好是计算整数和配置之间的一对一的映射。 这非常适用于排列，组合等，并确保每个配置被枚举只有一次。
现在，即使是对于一些相同的物品分区的数量递归是相当复杂的。
对于多集的分区计数相当于求解的推广项目欧拉问题181任意多集。
好了，这个问题有两个方面。
Firsty，该项目可以以任意顺序排列。 因此，对于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关闭
的排列（显示顺序）可以通过查看他们就像一棵树中导出，如由其他两个提及。 这几乎肯定会涉及到递归，如这里 。 分组是独立于它们在许多方面。 一旦你把所有的排列组合，你可以根据需要与集团联系他们。
以下是你需要为你的问题，这部分的代码：
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
我迅速刮起了一些代码来做到这一点。 不过，我离开了分离给定列表中的每一个可能的组合，因为我不知道它实际上是需要的，但它应该是很容易添加如果必要的。
无论如何，代码运行得很好金额较小，但作为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秒。
但是，我通过你正在做的问题的问题描述阅读，我看你是如何试图解决这个问题，但看到我是如何快速运行时增加不认为它会以最快的速度，你会期望工作。 请记住，项目欧拉的问题应解决在1分钟左右。
