LINUX.ORG.RU

Найти все возможные наборы натуральных чисел, с суммой равной данному

 ,


1

4

Есть некоторое целое число R>0. Нужно найти все наборы натуральных чисел, суммы которых равны R. Числа в наборе должны быть упорядоченны, допускается несколько одинаковых чисел.

При реализации я под набором понимаю список. Т.е. хочется функцию (например splitR), которая принимает R и возвращает список списков.

Например

splitR(1) ==> [[1]]
splitR(2) ==> [[1,2], [2]]
splitR(3) ==> [[1,1,1], [1,2], [3]]
splitR(4) ==> [[1,1,1,1], [1,1,2], [1,3], [2,2], [4]]
splitR(5) ==> [[1,1,1,1,1], [1,1,1,2], [1,2,2], [1,1,3], [1,4], [2,3], [5]]

Че то голова не варит... про рекурсию я знаю;-)

★★★★★

Ответ на: комментарий от O02eg

Надо что бы работало, рекурсивно просто красивше. max R порядка первых десятков, но лудить R вложенных циклов не хочется.

AIv ★★★★★ ()
splitR(N):=splitR0(N,1)
splitR0(N,m):= for i = m .. N
 [[i] ++ splitR0(N-i,i)]

В общем как-то так. Питона не знаю.

O02eg ★★★★★ ()
Ответ на: комментарий от O02eg

Если бы... «если хочешь что то сделать, придется делать это самому»(ц)

_split = lambda Rmin, R: sum([ [ [i]+l for l in _split(i, R-i)] for i in range(Rmin, R+1) ], []) if Rmin<R else [[R]]
splitR = lambda R: sorted(set( tuple(sorted(filter(None, l))) for l in _split(1, R) ))
AIv ★★★★★ ()
def splitR0(t,N):
    if N==0:
        yield []
    else:
        for i in xrange(t,N):
            for lst in splitR0(i,N-(i+1)):
                yield [i+1] + lst
    
def splitR(N):
    lst = []
    for i in splitR0(0,N):
        lst += [i]
    return lst
anonymous ()
Ответ на: комментарий от O02eg

Че то не вышло, пришлось грубой силой...

AIv ★★★★★ ()
Ответ на: комментарий от anonymous

О, у Вас изящней, спасибо. Надо будет только понять как оно работает;-)

AIv ★★★★★ ()
splitR n = n `splitStartingWith` 1
n `splitStartingWith` i | n < i = []
                        | n < 2*i = [[n]]
                        | otherwise = [k:ks | k <- [i..n `div` 2], ks <- (n-k) `splitStartingWith` k] ++ [[n]]
Miguel ★★★★★ ()
Ответ на: комментарий от anonymous
def f(l):
    a=[[l]]
    for rl in xrange(1,l):
	for i in f(l-rl):
	    if i[0]<=rl:
		a.append([rl]+i)
    return a
alfix ()
def main(R):
    def q(t,m,prt):
        if(t<=0):
            return [prt]
        if(m>t):
            m=t
        o=[]
        while(m>0):
            o+=q(t-m,m,[m]+prt)
            m-=1
        return o
    return q(R,R,[])
qulinxao ★★☆ ()

в теории можно избежать глубокой рекурсии и длинных-длинных списков, заюзав итератор(функцию) а-ля «next permutation», если сформулировать подругому: все способы расстановки парных скобок на векторе за N едениц.

MKuznetsov ★★★★★ ()
Ответ на: комментарий от MKuznetsov

Да нет, в принципе это не самое узкое место как выяснилось. То, как потом это дело обратывается тормозит гораздо сильнее;-)

AIv ★★★★★ ()
def splitR0(t, N):
    for i in xrange(t, N/2+1):
        lst_i = [i]
        for lst in splitR0(i, N-i):
            yield lst_i+lst
    yield[N]
    
def splitR(N):
    if N<=0:
        return []
    return list(splitR0(1, N))
anonymous ()
Ответ на: комментарий от anonymous
def splitR0(t, N, head):
    for i in xrange(t, N/2+1):
        for lst in splitR0(i, N-i, head+[i]):
            yield lst
    yield head+[N]
    
def splitR(N):
    if N<=0:
        return []
    return list(splitR0(1, N, []))
anonymous ()

Кнут, integer partitions. Там несколько алгоритмов, выбирай по вкусу. Все простые и нерекурсивные, что есть гуд.

cdshines ★★★★★ ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.