QUIZ: Рассчитать количество комбинаций дней

Question

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

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

Примером может быть:

5, 10, 5, 2, 2, 1, 5

Как вы можете видеть выше, будет равняться 30.

The Идея расчета состоит в том, чтобы дать потенциальному сотруднику представление о том, какие выходные дни они могут предпринять.

Возвращаемые значения также могут быть:

10, 10, 10

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

Задача может быть выполнена в ЛЮБОМ программировании langauge!

Я попытался следующие:

using System; 
using System.Collections.Generic; 
using System.Linq; 
using System.Text; 
using System.Threading.Tasks; 

namespace ConsoleApplication2 
{ 
    class Program 
    { 
     static void Main(string[] args) 
     { 
      // find all possible combinations of this list 
      var input = new[] { "1", "2", "3", "4", "5", "6","7","8","9","10","11","12","13","14" }; 
      var output = FastPowerSet(input); 

      Print(output); 
      Console.ReadLine(); 
     } 

     static T[][] FastPowerSet<T>(T[] seq) 
     { 
      var powerSet = new T[1 << seq.Length][]; 
      powerSet[0] = new T[0]; // starting only with empty set 
      for (var i = 0; i < seq.Length; i++) 
      { 
       var cur = seq[i]; 
       var count = 1 << i; // doubling list each time 
       for (var j = 0; j < count; j++) 
       { 
        var source = powerSet[j]; 
        var destination = powerSet[count + j] = new T[source.Length + 1]; 
        for (var q = 0; q < source.Length; q++) 
         destination[q] = source[q]; 
        destination[source.Length] = cur; 
       } 
      } 
      return powerSet; 
     } 

     static void Print<T>(T[][] seq) 
     { 
      for (var i = 0; i < seq.Length; i++) 
      { 
       var line = new StringBuilder(); 
       for (var j = 0; j < seq[i].Length; j++) 
       { 
        line.AppendFormat("{0}, ", seq[i][j]); 
       } 
       Console.WriteLine(line); 
      } 
     } 
    } 
} 

Answer 1

Спасибо PriceCheaperton!

Несколько шире вопрос был дан ответ here where restrictions of the sizes of the parts of the given sum can be given as well.

В решении Python на верхней ссылке выше вы бы изменить вызов функции, как это решить конкретный пример (я если 15 не знаю ..30 действительно, в противном случае вы должны заполнить список по таким же образом, я начал его):

subset_sum([1,2,3,4,5,6,7,8,9,10,11,12,13,14,15..30],30) 

с наилучшими пожеланиями, Маты

Answer 2

Я попытался рекурсивный способ делать вещи в Python, работает прилично:

def combination(n): 
    if n == 0: 
     return [[]] 

    comb = [] 

    for i in xrange(n): 
     sub_comb = combination(n-(i+1)) 
     for l in sub_comb: 
      l.append(i+1) 
      comb.append(l) 
    return comb 

if __name__ == '__main__': 

    print combination(10)