Я быстро набрал код для этого. Однако я исключил разделение каждой возможной комбинации данного списка, потому что я не был уверен, что это действительно необходимо, но при необходимости его легко добавить.
В любом случае, код работает достаточно хорошо для небольших объемов, но, как уже упоминалось в 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 должны быть решены примерно за минуту.