Как найти все способы получения целого числа n в виде суммы m целых чисел (без порядка)?

Question

Я ищу алгоритм, который находит все способы выразить целое число n как сумму m (неотрицательных) целых чисел. Меня особенно интересуют m = 6 и n⩽20. Какой бы самый быстрый способ найти все возможности (используя компьютер, а не вручную). Если возможно, я хотел бы посмотреть только на комбинации из шести целых чисел, причем порядок не является релевантным (то есть [1, 2, 0, 0, 0, 0] и [2, 1, 0, 0, 0, 0 ] считаются 1 комбинацией).

Самый простой способ - это просто попробовать все перестановки с 6 целыми числами, меньшими или равными 20, и добавить только те, которые суммируют до 20 к нашему результату (с последующим удалением удвоений, если мы не хотим смотреть на упорядочение). Похоже, что это займет очень много времени, так как 20^6 возможностей потребуют достаточно времени, чтобы проверить.

Что было бы более эффективным способом решения этой проблемы?

Answer 1

Вы можете избежать повторений путем генерации чисел в монотонно возрастающем порядке (каждое число равно или больше предыдущего).

Для данного count (например, 6) вы можете определить проблему рекурсивно, генерируя все возможные значения для первого числа, а затем рекурсивно генерируя все списки номеров count - 1, которые суммируются с исходной суммой минус первое число, причем первое число является минимальным значением для оставшихся номеров в списке.

Поскольку цифры должны увеличиваться, вы не можете «пикать слишком рано» - вы можете вычислить максимальное значение, разделив сумму на счетчик (так как все остальные значения должны быть равны или больше этого).

Вот простая реализация в Java:

public static void outputSums(String start, int sum, int count, int min) 
{ 
    // if there is just one value, it's just the sum: 
    if(count == 1) 
    { 
     System.out.println(start + " " + sum); 
     return; 
    } 

    int max = sum/count; // calculate maximum value 
    for(int i = min; i <= max; i++) 
    { 
     outputSums(start + " " + i, // append each number to the list 
      sum - i, // recursively find numbers that sum to the remainder 
      count - 1, // with a count of one less 
      i); // equal to or greater to this one (i.e. increasing order) 
    } 
} 

start содержит неполный список, что у вас есть выход до сих пор. При первом вызове функции он будет пустым.

Demo

Answer 2

Обратное предыдущего подхода состоит в том, чтобы вычислить его от самых больших до самых маленьких.

Это реализация Python, использующая итераторы, так что она проста в использовании программно.

def partition (count, total, maximum = None) : 
    if maximum is None or total < maximum: 
     maximum = total 
    if 0 == count: 
     yield [] 
    else: 
     while total <= count * maximum: 
      for part in partition(count - 1, total - maximum, maximum): 
       yield part + [maximum] 
      maximum = maximum - 1 

А вот пример того, как использовать его программно распечатать результат:

for part in partition(6, 10): 
    print(part)