QUIZ: Berechne Anzahl der Tage Kombinationen

Question

Ich möchte die Anzahl der verschiedenen Arten von Tagen berechnen, die ich haben kann, dass gleich meinem Sollwert.

Zum Beispiel, wenn jemand 30 Tage Jahresurlaub als Teil der Beschäftigung hat, möchte ich berechnen, welche verschiedenen Arten von Urlaub sie nehmen könnten.

wäre ein Beispiel:

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

Wie Sie die oben wird gleich 30 sehen

Die Die Idee der Berechnung besteht darin, einem potenziellen Mitarbeiter eine Vorstellung davon zu geben, welche Art von freien Tagen er nehmen kann.

Die zurückgegebenen Werte könnte auch sein:

10, 10, 10

Dies bedeutet, dass i Zahlenkombinationen Zahl, die gleich der gesamten Jahresurlaub berechnen müssen.

Die Herausforderung kann in jeder Programmiersprache abgeschlossen werden!

Ich habe versucht, die folgenden:

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

Danke PriceCheaperton!

Eine etwas breitere Frage haben here where restrictions of the sizes of the parts of the given sum can be given as well.

In der Python-Lösung oben auf den Link beantwortet oben Sie den Aufruf der Funktion wie folgt ändern würde Ihr besonderes Beispiel (ich weiß nicht, ob 15 zu lösen ..30 gültig ist, sonst müssen Sie die Liste, um die gleiche Art und Weise, ergänze ich es begonnen haben):

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

Mit besten Grüßen, Mats

Answer 2

ich eine rekursive Art und Weise, Dinge zu tun in Python versucht habe, funktioniert anständig:

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)