алгоритм суммирования списка чисел для всех комбинаций

Question

У меня есть список чисел, и я хочу сложить все различные комбинации. Например:

• число как 1,4,7 и 13
• вывод будет:

1+4=5
1+7=8
1+13=14
4+7=11
4+13=17
7+13=20
1+4+7=12
1+4+13=18
1+7+13=21
4+7+13=24
1+4+7+13=25

Есть ли формула для вычисления этого с разными числами?

Answer 1

set - набор сумм, а list - список исходных чисел.

Это Java.

public void subSums() {
    Set<Long> resultSet = new HashSet<Long>();
    for(long l: list) {
        for(long s: set) {
            resultSet.add(s);
            resultSet.add(l + s);
        }
        resultSet.add(l);
        set.addAll(resultSet);
        resultSet.clear();
    }
}

Answer 2

v=[1,2,3,4]#variables to sum
i=0
clis=[]#check list for solution excluding the variables itself
def iterate(lis,a,b):
    global i
    global clis
    while len(b)!=0 and i<len(lis):
        a=lis[i]
        b=lis[i+1:]
        if len(b)>1:
            t=a+sum(b)
            clis.append(t)
        for j in b:
            clis.append(a+j)
        i+=1
        iterate(lis,a,b)
iterate(v,0,v)

написано на python. Идея состоит в том, чтобы разбить список в одно целое число и список, например. [1,2,3,4] в 1, [2,3,4]. мы добавляем общую сумму сейчас, добавляя целое число и сумму оставшегося списка. Также мы берем каждую отдельную сумму, т.е. 1,2; 1,3; 1,4. контрольный список теперь должен быть [1 + 2 + 3 + 4,1 + 2,1 + 3,1 + 4], тогда мы будем называть новый список рекурсивно, т.е. теперь int = 2, list = [3,4]. Теперь контрольный список будет добавлен [2 + 3 + 4,2 + 3,2 + 4], соответственно мы добавляем контрольный список, пока список не станет пустым.

Answer 3

Спасибо, Зак,

Я создаю решение по банковской сверке. Я поместил ваш код на jsbin.com, чтобы провести небольшое тестирование, и создал его в Javascript:

function f(numbers,ids, index,  sum, output, outputid, find )
{
    if (index == numbers.length){
          var x ="";
          if (find == sum) {
              y= output + " } = " + sum + "  " + outputid + " }<br/>" ;
          }
        return;
    }
    f(numbers,ids, index + 1, sum + numbers[index], output + " " + numbers[index], outputid + " " + ids[index], find);
    f(numbers,ids, index + 1, sum, output, outputid,find);
}

var y;

f( [1.2,4,7,13,45,325,23,245,78,432,1,2,6],[1,2,3,4,5,6,7,8,9,10,11,12,13], 0, 0, '{','{', 24.2);
if (document.getElementById('hello')) {
  document.getElementById('hello').innerHTML = y;
}

Мне нужно создать список идентификаторов, чтобы исключить их из следующего совпадающего номера.

Я отправлю свое окончательное решение, используя vb.net

Answer 4

Возможно, вас заинтересует Научная библиотека GNU, если вы хотите избежать затрат на обслуживание. Фактический процесс суммирования более длинных последовательностей станет очень дорогостоящим (более того, чем генерация одной перестановки на пошаговой основе), большинство архитектур имеют SIMD / векторные инструкции, которые могут обеспечить довольно впечатляющее ускорение (я бы привел примеры таких реализаций, но Я пока не могу разместить URL).

Answer 5

Это не код для генерации сумм, но он генерирует перестановки. В вашем случае:

1; 1,4; 1,7; 4,7; 1,4,7; ...

Если у меня есть время на выходных, и если это интересно, я могу изменить это, чтобы получить суммы.

Это просто забавный кусок кода LINQ из блога Игоря Островского под названием «7 трюков для упрощения ваших программ с помощью LINQ» (http://igoro.com/archive/7-tricks-to-simplify-your-programs-with-linq/).

T[] arr = …;
var subsets = from m in Enumerable.Range(0, 1 << arr.Length)
              select
                  from i in Enumerable.Range(0, arr.Length)
                  where (m & (1 << i)) != 0
                  select arr[i];