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

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

Простой способ сделать это - создать битовый набор с количеством битов, равным количеству. В вашем примере 4.

Затем посчитайте от 0001 до 1111 и сложите каждое число, которое имеет 1 в наборе:

Числа 1,4,7,13:

0001 = 13=13
0010 = 7=7
0011 = 7+13 = 20

1111 = 1+4+7+13 = 25

Answer 2

Вот как будет выглядеть простое рекурсивное решение в Java:

public static void main(String[] args)
{
    f(new int[] {1,4,7,13}, 0, 0, "{");
}

static void f(int[] numbers, int index, int sum, String output)
{
    if (index == numbers.length)
    {
        System.out.println(output + " } = " + sum);
        return;
    }

    // include numbers[index]
    f(numbers, index + 1, sum + numbers[index], output + " " + numbers[index]);

    // exclude numbers[index]
    f(numbers, index + 1, sum, output);
}

Выход:

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

Answer 3

Самый известный алгоритм требует экспоненциального времени. Если бы существовал алгоритм полиномиального времени, то вы бы решили проблему суммы подмножеств и, таким образом, проблему P = NP .

Алгоритм здесь - создать битовый вектор длины, равный количеству элементов вашего набора чисел. Исправьте перечисление (n_i) вашего набора чисел. Затем перечислите все возможные значения битового вектора. Для каждого перечисления (e_i) битового вектора вычислите сумму e_i * n_i.

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

Четвертый том TAOCP Кнута содержит алгоритмы для генерации всех возможных значений битового вектора.

Answer 4

Вот простая рекурсивная реализация Ruby:

a = [1, 4, 7, 13]

def add(current, ary, idx, sum)
    (idx...ary.length).each do |i|
        add(current + [ary[i]], ary, i+1, sum + ary[i])
    end
    puts "#{current.join('+')} = #{sum}" if current.size > 1
end    
add([], a, 0, 0)

Какие отпечатки

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

Если вам не нужно печатать массив на каждом шаге, код можно сделать еще проще и намного быстрее, поскольку не создаются дополнительные массивы:

def add(ary, idx, sum)
    (idx...ary.length).each do |i|
        add(ary, i+1, sum + ary[i])
    end
    puts sum
end
add(a, 0, 0)

Я не думаю, что вы можете сделать это намного проще, чем это.

Answer 5

C #:

Я пытался найти что-то более элегантное - но сейчас это должно сработать ...

//Set up our array of integers
int[] items = { 1, 3, 5, 7 };

//Figure out how many bitmasks we need... 
//4 bits have a maximum value of 15, so we need 15 masks.
//Calculated as:
//    (2 ^ ItemCount) - 1
int len = items.Length;
int calcs = (int)Math.Pow(2, len) - 1;

//Create our array of bitmasks... each item in the array
//represents a unique combination from our items array
string[] masks = Enumerable.Range(1, calcs).Select(i => Convert.ToString(i, 2).PadLeft(len, '0')).ToArray();

//Spit out the corresponding calculation for each bitmask
foreach (string m in masks)
{
    //Get the items from our array that correspond to 
    //the on bits in our mask
    int[] incl = items.Where((c, i) => m[i] == '1').ToArray();

    //Write out our mask, calculation and resulting sum
    Console.WriteLine(
        "[{0}] {1}={2}", 
        m, 
        String.Join("+", incl.Select(c => c.ToString()).ToArray()), 
        incl.Sum()
    );
}

Выходы как:

[0001] 7=7
[0010] 5=5
[0011] 5+7=12
[0100] 3=3
[0101] 3+7=10
[0110] 3+5=8
[0111] 3+5+7=15
[1000] 1=1
[1001] 1+7=8
[1010] 1+5=6
[1011] 1+5+7=13
[1100] 1+3=4
[1101] 1+3+7=11
[1110] 1+3+5=9
[1111] 1+3+5+7=16

Answer 6

Mathematica решение:

{#, Total@#}& /@ Subsets[{1, 4, 7, 13}]  //MatrixForm

Выход:

{}  0
{1} 1
{4} 4
{7} 7
{13}    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 7

Эта Perl-программа, кажется, делает то, что вы хотите. Он проходит различные способы выбора n предметов из k предметов . Легко подсчитать, сколько комбинаций существует, но получение сумм каждой комбинации означает, что вы должны в конечном итоге добавить их. У меня был похожий вопрос о Perlmonks , когда я спрашивал Как я могу рассчитать правильную комбинацию почтовых марок? .

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

#!/usr/bin/perl

use List::Util qw(sum);
use Math::Combinatorics;

my @n = qw(1 4 7 13);

foreach my $count ( 2 .. @n ) {
    my $c = Math::Combinatorics->new(
        count => $count,  # number to choose
        data => [@n],
        );

    print "combinations of $count from: [" . join(" ",@n) . "]\n";

    while( my @combo = $c->next_combination ){
        print join( ' ', @combo ), " = ", sum( @combo ) , "\n";
        }
    }

Answer 8

Вы можете перечислить все подмножества, используя битовый вектор.

В цикле for перейдите от 0 до 2 к N-й степени минус 1 (или начните с 1, если вас не интересует пустой набор).

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

ETA: поскольку природа этой проблемы связана с экспоненциальной сложностью, существует практическое ограничение на размер набора, который вы можете перечислить. Если выясняется, что вам не нужны все подмножества, вы можете найти «n выбирать k» для способов перечисления подмножеств k элементов.

Answer 9

PHP: Вот нерекурсивная реализация. Я не говорю, что это самый эффективный способ сделать это (это действительно экспоненциально 2 ^ N - см. Ответ и комментарии JasonTrue), но он работает для небольшого набора элементов. Я просто хотел написать что-то быстрое, чтобы получить результаты. Я основал алгоритм на ответе Мультяшки.

$set = array(3, 5, 8, 13, 19);

$additions = array();
for($i = 0; $i < pow(2, count($set)); $i++){
    $sum = 0;
    $addends = array();
    for($j = count($set)-1; $j >= 0; $j--) {
        if(pow(2, $j) & $i) {
            $sum += $set[$j];
            $addends[] = $set[$j];
        }
    }
    $additions[] = array($sum, $addends);
}

sort($additions);

foreach($additions as $addition){
    printf("%d\t%s\n", $addition[0], implode('+', $addition[1]));
}

Который выдаст:

0   
3   3
5   5
8   8
8   5+3
11  8+3
13  13
13  8+5
16  13+3
16  8+5+3
18  13+5
19  19
21  13+8
21  13+5+3
22  19+3
24  19+5
24  13+8+3
26  13+8+5
27  19+8
27  19+5+3
29  13+8+5+3
30  19+8+3
32  19+13
32  19+8+5
35  19+13+3
35  19+8+5+3
37  19+13+5
40  19+13+8
40  19+13+5+3
43  19+13+8+3
45  19+13+8+5
48  19+13+8+5+3

Например, случаем для этого может быть набор полос сопротивления для тренировки. Допустим, вы получаете 5 полос, каждая из которых имеет различные сопротивления, представленные в фунтах, и вы можете комбинировать полосы, чтобы суммировать общее сопротивление. Сопротивление полос составляет 3, 5, 8, 13 и 19 фунтов. Этот набор дает вам 32 (2 ^ 5) возможных конфигураций, минус ноль. В этом примере алгоритм возвращает данные, отсортированные по возрастанию общего сопротивления, в первую очередь, в пользу эффективных конфигураций полос, а для каждой конфигурации полосы сортируются по убыванию сопротивлений.

Answer 10

public static void main(String[] args) {
        // this is an example number
        long number = 245L;
        int sum = 0;

        if (number > 0) {
            do {
                int last = (int) (number % 10);
                sum = (sum + last) % 9;
            } while ((number /= 10) > 0);
            System.err.println("s = " + (sum==0 ? 9:sum);
        } else {
            System.err.println("0");
        }
    }