Print all ways to sum n integers so that they total a given sum.

I'm trying to come up with an algorithm that will print out all possible ways to sum N integers so that they total a given value.

Example. Print all ways to sum 4 integers so that they sum up to be 5.

Result should be something like:

5 0 0 0
开发者_如何学JAVA4 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

---

This is based off Alinium's code.
I modified it so it prints out all the possible combinations, since his already does all the permutations.
Also, I don't think you need the for loop when n=1, because in that case, only one number should cause the sum to equal value.
Various other modifications to get boundary cases to work.

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)

Runing sums(4, 5) returns:
[0, 0, 0, 5]
[0, 0, 1, 4]
[0, 0, 2, 3]
[0, 1, 1, 3]
[1, 1, 1, 2]

---

In pure math, a way of summing integers to get a given total is called a partition. There is a lot of information around if you google for "integer partition". You are looking for integer partitions where there are a specific number of elements. I'm sure you could take one of the known generating mechanisms and adapt for this extra condition. Wikipedia has a good overview of the topic Partition_(number_theory). Mathematica even has a function to do what you want: IntegerPartitions[5, 4].

---

The key to solving the problem is recursion. Here's a working implementation in python. It prints out all possible permutations that sum up to the total. You'll probably want to get rid of the duplicate combinations, possibly by using some Set or hashing mechanism to filter them out.

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"

With some extra effort, this can probably be simplified to get rid of some of the parameters I am passing to the recursive function. As suggested by redcayuga's pseudo code, using a stack, instead of manually managing an array, would be a better idea too.

---

I haven't tested this:

  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

I'm sure there's a better way to do this.

---

i've find a ruby way with domain specification based on Alinium's code

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

---

If you're interested in generating (lexically) ordered integer partitions, i.e. unique unordered sets of S positive integers (no 0's) that sum to N, then try the following. (unordered simply means that [1,2,1] and [1,1,2] are the same partition)

The problem doesn't need recursion and is quickly handled because the concept of finding the next lexical restricted partition is actually very simple...

In concept: Starting from the last addend (integer), find the first instance where the difference between two addends is greater than 1. Split the partition in two at that point. Remove 1 from the higher integer (which will be the last integer in one part) and add 1 to the lower integer (the first integer of the latter part). Then find the first lexically ordered partition for the latter part having the new largest integer as the maximum addend value. I use Sage to find the first lexical partition because it's lightening fast, but it's easily done without it. Finally, join the two portions and voila! You have the next lexical partition of N having S parts.

e.g. [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]

So, in Python and calling Sage for the minor task of finding the first lexical partition given n and s parts...

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

If you want zeros (not actual integer partitions), then the functions only need small modifications.

---

Try this code. I hope it is easier to understand. I tested it, it generate correct sequence.

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);
        }
    }
}

Ask for clarification, if required.

The is One of the output

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