Я быстро взломал код, чтобы сделать это. Однако я не разделял все возможные комбинации данного списка, потому что я не был уверен, что это действительно необходимо, но при необходимости его легко добавить.
В любом случае, код работает достаточно хорошо для небольших сумм, но, как уже упоминалось в CodeByMoonlight, количество возможностей становится действительно высоким очень быстро, поэтому время выполнения увеличивается соответственно.
Во всяком случае, вот код питона:
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
В принципе, мой код создает список, содержащий п разделения, вставки их в данный список, а затем находит все возможные перестановки разделов в списке.
Таким образом, если мы используем ваш пример мы получим:
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
In +0,000154972076416 секунд.
Однако я прочитал описание проблемы проблемы, которую вы выполняете, и я вижу, как вы пытаетесь решить эту проблему, но, видя, как быстро увеличивается время выполнения, я не думаю, что она будет работать так же быстро, как вы ожидаете , Помните, что проблемы Project Euler должны решаться примерно через минуту.
На самом деле, эти списки, не устанавливает. Сожалею. Будут повторяющиеся значения. –
В чем проблема, над которой вы работаете? –
159, но я оставлю его вам, почему я хочу этот алгоритм –