Выведите все способы сложения n целых чисел, чтобы они составили заданную сумму. - PullRequest
1 голос
/ 07 апреля 2010

Я пытаюсь придумать алгоритм, который распечатает все возможные способы суммирования N целых чисел, чтобы они составляли заданное значение.

Пример. Выведите все способы суммирования 4 целых чисел, чтобы они суммировались до 5.

Результат должен выглядеть примерно так:

5 0 0 0
4 1 0 0
3 2 0 0
3 1 1 0
2 3 0 0
2 2 1 0
2 1 2 0
2 1 1 1
1 4 0 0
1 3 1 0 
1 2 2 0
1 2 1 1
1 1 3 0
1 1 2 1
1 1 1 2

Ответы [ 7 ]

2 голосов
/ 09 апреля 2010

В чистой математике способ суммирования целых чисел для получения заданной суммы называется разбиением. Существует много информации, если вы гуглите «целочисленный раздел». Вы ищете целочисленные разделы, где есть определенное количество элементов. Я уверен, что вы могли бы взять один из известных механизмов генерации и приспособиться к этому дополнительному условию. В Википедии есть хороший обзор темы Partition_ (number_theory) . Mathematica даже имеет функцию, которая делает то, что вы хотите: IntegerPartitions[5, 4].

2 голосов
/ 07 апреля 2010

Это основано на коде Alinium.
Я изменил его так, чтобы он распечатывал все возможные комбинации, поскольку он уже выполняет все перестановки.
Кроме того, я не думаю, что вам нужен цикл for, когда n = 1, потому что в этом случае только одно число должно привести к тому, что сумма будет равна. Различные другие модификации, чтобы заставить граничные случаи работать.

def sum(n, value):
    arr = [0]*n  # create an array of size n, filled with zeroes
    sumRecursive(n, value, 0, n, arr);

def sumRecursive(n, value, sumSoFar, topLevel, arr):
    if n == 1:
        if sumSoFar <= value:
            #Make sure it's in ascending order (or only level)
            if topLevel == 1 or (value - sumSoFar >= arr[-2]):
                arr[(-1)] = value - sumSoFar #put it in the n_th last index of arr
                print arr
    elif n > 0:
        #Make sure it's in ascending order
        start = 0
        if (n != topLevel):
            start = arr[(-1*n)-1]   #the value before this element

        for i in range(start, value+1): # i = start...value
            arr[(-1*n)] = i  # put i in the n_th last index of arr
            sumRecursive(n-1, value, sumSoFar + i, topLevel, arr)

Возвращенные суммы (4, 5):
[0, 0, 0, 5]
[0, 0, 1, 4]
[0, 0, 2, 3]
[0, 1, 1, 3]
[1, 1, 1, 2]

1 голос
/ 07 апреля 2010

Ключом к решению проблемы является рекурсия. Вот рабочая реализация в Python. Он распечатывает все возможные перестановки, которые суммируются до общей суммы. Возможно, вы захотите избавиться от дублирующих комбинаций, возможно, используя какой-то набор или механизм хеширования для их фильтрации.

def sum(n, value):
    arr = [0]*n  # create an array of size n, filled with zeroes
    sumRecursive(n, value, 0, n, arr);

def sumRecursive(n, value, sumSoFar, topLevel, arr):
    if n == 1:
        if sumSoFar > value:
            return False
        else:
            for i in range(value+1): # i = 0...value
                if (sumSoFar + i) == value:
                    arr[(-1*n)] = i # put i in the n_th last index of arr
                    print arr;
                    return True

    else:
        for i in range(value+1): # i = 0...value
            arr[(-1*n)] = i  # put i in the n_th last index of arr
            if sumRecursive(n-1, value, sumSoFar + i, topLevel, arr):
                if (n == topLevel):
                    print "\n"

С некоторыми дополнительными усилиями это, вероятно, можно упростить, чтобы избавиться от некоторых параметров, которые я передаю рекурсивной функции. Как подсказывает псевдокод redcayuga, лучше использовать стек вместо ручного управления массивом.

0 голосов
/ 17 марта 2014

Попробуйте этот код. Я надеюсь, что это легче понять. Я проверил это, он генерирует правильную последовательность.

void partition(int n, int m = 0)
{
    int i;
    // if the partition is done
    if(n == 0){
        // Output the result
        for(i = 0; i < m; ++i)
            printf("%d ", list[i]);
        printf("\n");
        return;
    }
    // Do the split from large to small int
    for(i = n; i > 0; --i){
        // if the number not partitioned or
        // willbe partitioned no larger than 
        // previous partition number
        if(m == 0 || i <= list[m - 1]){
            // store the partition int
            list[m] = i;
            // partition the rest
            partition(n - i, m + 1);
        }
    }
}

При необходимости попросите разъяснений.

Один из выходных

6 
5 1 
4 2 
4 1 1 
3 3 
3 2 1 
3 1 1 1 
2 2 2 
2 2 1 1 
2 1 1 1 1 
1 1 1 1 1 1 


10 
9 1 
8 2 
8 1 1 
7 3 
7 2 1 
7 1 1 1 
6 4 
6 3 1 
6 2 2 
6 2 1 1 
6 1 1 1 1 
5 5 
5 4 1 
5 3 2 
5 3 1 1 
5 2 2 1 
5 2 1 1 1 
5 1 1 1 1 1 
4 4 2 
4 4 1 1 
4 3 3 
4 3 2 1 
4 3 1 1 1 
4 2 2 2 
4 2 2 1 1 
4 2 1 1 1 1 
4 1 1 1 1 1 1 
3 3 3 1 
3 3 2 2 
3 3 2 1 1 
3 3 1 1 1 1 
3 2 2 2 1 
3 2 2 1 1 1 
3 2 1 1 1 1 1 
3 1 1 1 1 1 1 1 
2 2 2 2 2 
2 2 2 2 1 1 
2 2 2 1 1 1 1 
2 2 1 1 1 1 1 1 
2 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 
0 голосов
/ 06 февраля 2013

Если вы заинтересованы в создании (лексически) упорядоченных целочисленных разделов, то есть уникальных неупорядоченных наборов из S натуральных чисел (без 0), которые суммируются с N, попробуйте следующее. (неупорядоченный просто означает, что [1,2,1] и [1,1,2] являются одним и тем же разделом)

Проблема не требует рекурсии и быстро решается, потому что концепция поиска следующего лексического ограниченного раздела на самом деле очень проста ...

В концепции: начиная с последнего добавления (целое число), найдите первый экземпляр, где разница между двумя добавлениями больше 1. Разбейте раздел на две в этой точке. Удалите 1 из более высокого целого числа (которое будет последним целым числом в одной части) и добавьте 1 к более низкому целому числу (первое целое число последней части). Затем найдите первый лексически упорядоченный раздел для последней части, имеющей новое наибольшее целое число в качестве максимального значения добавления. Я использую Sage, чтобы найти первый лексический раздел, потому что он быстро освещается, но это легко сделать без него. Наконец, объедините две части и вуаля! У вас есть следующий лексический раздел N с частями S.

например. [6,5,3,2,2] -> [6,5], [3,2,2] -> [6,4], [4,2,2] -> [6,4], [ 4,3,1] -> [6,4,4,3,1]

Итак, в Python и вызове Sage для незначительной задачи поиска первого лексического раздела по n и s частям ...

from sage.all import *

def most_even_partition(n,s): # The main function will need to recognize the most even partition possible (i.e. last lexical partition) so it can loop back to the first lexical partition if need be
    most_even = [int(floor(float(n)/float(s)))]*s
    _remainder = int(n%s)

    j = 0
    while _remainder > 0:
        most_even[j] += 1
        _remainder -= 1
        j += 1
    return most_even

def portion(alist, indices): 
    return [alist[i:j] for i, j in zip([0]+indices, indices+[None])]


def next_restricted_part(p,n,s):
    if p == most_even_partition(n,s):return Partitions(n,length=s).first()

    for i in enumerate(reversed(p)):
        if i[1] - p[-1] > 1:
            if i[0] == (s-1):
                return Partitions(n,length=s,max_part=(i[1]-1)).first()
            else:
                parts = portion(p,[s-i[0]-1]) # split p (soup?)
                h1 = parts[0]
                h2 = parts[1]
                next = list(Partitions(sum(h2),length=len(h2),max_part=(h2[0]-1)).first())
                return h1+next

Если вам нужны нули (а не фактические целочисленные разбиения), то функции нуждаются только в небольших модификациях.

0 голосов
/ 20 января 2013

я нашел способ ruby ​​со спецификацией домена, основанной на коде Alinium

class Domain_partition

    attr_reader :results,
                :domain,
                :sum,
                :size

    def initialize(_dom, _size, _sum)
        _dom.is_a?(Array) ? @domain=_dom.sort : @domain= _dom.to_a
        @results, @sum, @size = [], _sum, _size
        arr = [0]*size  # create an array of size n, filled with zeroes
        sumRecursive(size, 0, arr)
    end

    def sumRecursive(n, sumSoFar, arr)

        if n == 1
            #Make sure it's in ascending order (or only level)
            if sum - sumSoFar >= arr[-2] and @domain.include?(sum - sumSoFar)
                final_arr=Array.new(arr)
                final_arr[(-1)] = sum - sumSoFar #put it in the n_th last index of arr
                @results<<final_arr
            end

        elsif n > 1

            #********* dom_selector ********

            n != size ? start = arr[(-1*n)-1] : start = domain[0]
            dom_bounds=(start*(n-1)..domain.last*(n-1))

            restricted_dom=domain.select do |x|

                if x < start 
                    false; next
                end

                if size-n > 0
                    if dom_bounds.cover? sum-(arr.first(size-n).inject(:+)+x) then true
                    else false end  
                else 
                    dom_bounds.cover?(sum+x) ? true : false
                end
            end # ***************************

            for i in restricted_dom
                _arr=Array.new(arr)
                _arr[(-1*n)] = i 
                sumRecursive(n-1, sumSoFar + i, _arr)
            end
        end
    end
end 

a=Domain_partition.new (-6..6),10,0 
p a

b=Domain_partition.new [-4,-2,-1,1,2,3],10,0 
p b
0 голосов
/ 07 апреля 2010

Я не проверял это:

  procedure allSum (int tot, int n, int desiredTotal) return int
       if n > 0
           int i = 
           for (int i = tot; i>=0; i--) {
               push i onto stack;
               allSum(tot-i, n-1, desiredTotal);
               pop top of stack
            }
        else if n==0
            if stack sums to desiredTotal then print the stack   end if
        end if

Я уверен, что есть лучший способ сделать это.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...