C# Zahlenproblematik

[UnKnOwN_86]

Hi.

Ich würde gerne eine Anzahl an Möglichkeiten einer bestimmten Zahlenkonstellation herausfinden, diese Konstellationen sollen alle eins gemeinsam haben dessen Summe soll einer bestimmten Zahl entsprechen.

Als Beispiel:
Ich habe eine Zahlenkonstellation bestehend aus 10 Zahlen, diese liegen zwischen 0 und 9 und deren Summe ergibt 40. Also wäre eine mögliche Konstellation:
1 + 9 + 3 + 5 + 4 + 1 + 2 + 3 + 4 + 8 = 40

Wie kann ich nun mit Hilfe von C# eine Liste sämtlicher Möglichkeit ausgeben?

 

[foxhunter]

Am einfachsten ist es, zehn Variablen zahl1 bis zahl10 zu nehmen und diese in verschachtelte Schleifen hochzuzählen. Jeweils danach ein Vergleich, ob 40 erreicht wird, und diese in eine Gut-Liste übernehmen. Zwar nicht genial..müssste aber funktionieren...

 

[Samurai76]

Am längsten dauernde Methode: Alle Stellen hochzählen lassen (Variablen) und die Kombination als Text z.B. in ein Arry schreiben, sobeld das Ergebnis passt (Stichwort Quersumme). Das in C übersetzen und es sollte (je nach Stellenanzahl) gar nicht solang dauern.

Edit: Zu langsam, und ja, es stellt nicht einen optimierten Algorythmus dar, sondern nur einen Denksansatz, wie man es lösen könnte

 

[1668mib]

Naja im Grunde geht nur "probieren". Und das am besten systematisch...

also man macht alle Kombinationen durch
0 + 0 + 0 + 0 + 0 + 0 + 0 + 0 + 0 + 0 = 0 => kein Treffer
0 + 0 + 0 + 0 + 0 + 0 + 0 + 0 + 0 + 1 = 1 => kein Treffer
...
0 + 0 + 0 + 0 + 0 + 0 + 4 + 9 + 9 + 9 = 40 => Treffer

Die Liste bzw eher so ein Baum kann rekursiv erstellt werden.

Ich würde einfach eine Liste/Baum aller Summen erstellen und daraus dann eine Liste der Summen, die 40 ergeben, erstellen...

@foxhunter: 10 verschachtelte Schleifen? Klingt super...

 

[Fairy Ultra]

lass eine variable hochzählen und bilde die quersumme und lass bei 40 diese entsprechend speichern

 

[R3ddy]

Ich denke das ganze ist am einfachsten rekursiv zu lösen. Da ich aber vermute, dass es sich um eine Hausaufgabe handelt (sehe keine praktische Anwendung für sowas) werde ich nicht konkreter.

Hochzählen und prüfen geht natürlich auch, ist von der Performance aber bedeutend schlechter.

 

[foxhunter]

so als ungetestes Beispiel, allerdings in C (C# ist nicht so mein Ding..)

int a,b,c,d,e,f,g,h,i,j

for (a=0;a<10;a++)
 for (b=0;b<10;b++)
  for (c=0;c<10;c++)
   for (d=0;d<10;d++)
    for (e=0;e<10;e++)
     for (f=0;f<10;f++)
      for (g=0;g<10;g++)
       for (h=0;h<10;h++)
        for (i=0;i<10;i++)
         for (j=0;j<10;j++)
          if (a+b+c+d+e+f+g+h+i+j == 40)
           printf("%d+%d+%d+%d+%d+%d+%d+%d+%d+%d = 40\n",a,b,c,d,e,f,g,h,i,j)

 

[1668mib]

Wobei das bei 10 Ziffern schon speicherhungrig werden kann mit meinem Baum... hmm... evtl sind die Schleifen doch nicht so verkehrt, aber die sind halt unflexibel... der Ansatz hier funktioniert bei wengier Zahlen:

namespace sum40
{
    class Program
    {
        static void Main(string[] args)
        {
            List<List<int>> list = SumSearcher.getSums(10, 3);
            foreach (List<int> summands in list) {
                foreach (int value in summands) {
                    Console.Write(value + " ");
                }
                Console.WriteLine();
            }
            Console.ReadKey();
        }
    }

    class SumSearcher
    {

        public static List<List<int>> getSums(int sum, int summands)
        {
            List<List<int>> result = new List<List<int>>();
            for (int i = 0; i < 10; i++)
            {
                new NumberNode(null, i, summands - 1, sum, result);
            }
            return result;
        }


        class NumberNode
        {
            private int value;
            private NumberNode parent;

            public NumberNode(NumberNode parent, int value, int depth, int sum, List<List<int>> results)
            {
                this.parent = parent;
                this.value = value;
                if (getSum() > sum)
                {
                    return;
                }
                if (depth == 0)
                {
                    if (getSum() == sum)
                    {
                        List<int> list = new List<int>();
                        NumberNode currentItem = this;
                        while (currentItem != null)
                        {
                            list.Insert(0, currentItem.value);
                            currentItem = currentItem.parent;
                        }
                        results.Add(list);
                    }
                }
                else
                {
                    for (int i = 0; i < 10; i++)
                    {
                        new NumberNode(this, i, depth - 1, sum, results);
                    }
                }
            }

            public int getSum()
            {
                int result = value;
                NumberNode currentParent = parent;
                while (currentParent != null)
                {
                    result += currentParent.value;
                    currentParent = currentParent.parent;
                }
                return result;
            }
        }
    }
}

 

[maxwell-cs]

hier mal ein rekursiver ansatz, der schneller als die vollständige enumeration mit anschließender summenprüfung ist, da belegungen, die nicht mehr zu der gewünschten summe führen können, nicht weiter verfolgt werden.
zwar in c++, aber die paar zeilen auf c# zu kopieren sollte ja kein aufwand sein.

#include <iostream>

using namespace std;

int max (int a, int b){
   if (a > b) {
      return a;
   }
   return b;
}

void printSummands(int sum,
                   int num_digits,
                   int min_val,
                   int max_val,
                   int* data,
                   int prefix_len)
{
   if (num_digits > 0){
      for (int i = max(min_val, sum - (num_digits - 1) * max_val); i <= max_val && i <= sum; ++i){
         data[prefix_len] = i;
         printSummands(sum - i,
                       num_digits - 1,
                       min_val,
                       max_val,
                       data,
                       prefix_len + 1);
      }
   }
   else {
      for (int i = 0; i < prefix_len; ++i) {
         cout << data[i];
         if (i + 1 < prefix_len) {
            cout << " + ";
         }
         else {
            cout << endl;
         }
      }
   }
}

int main() {
   const int num_digits = 3;
   const int min_val = 0;
   const int max_val = 9;
   const int sum = 20;
   int data[num_digits];
   printSummands(sum,
                 num_digits,
                 min_val,
                 max_val,
                 data,
                 0);
   return 0;
}

edit: für den fall 40 / 10 summanden / ziffern von 0-9 werden 374894389 verschiedene summen bestimmt (hab dafür mal die konsolenausgabe durch nen zähler ersetzt).

edit: nochmal ein wenig die performance verbessert

 

[1668mib]

Ganz anderer Ansatz:
man erstellt eine Liste von Ziffern, die überhaupt zur Summe 40 kommen mit der Bedingung, dass es höchstens 10 Ziffern sein dürfen.... also z.B.
1, 2, 3, 4, 4, 6, 7, 8
4, 9, 9, 9

Die Einträge füllt man mit Nullen auf und permutiert sie durch.

 

[holy]

Strengt euch mal ein bischen mehr an.
Der jenige, der das Problem löst, am besten für eine beliebige Zahl, also nicht nur 40, wird vermutlich sehr viel Geld damit verdienen und zumindest den Turing-Preis bekommen

edit.
Effizienz vorausgesetzt

 

[1668mib]

@maxwell-cs: Die Zahl der Summen ist auch schon mit ein Grund, warum es sehr speicherhungrig wird, wenn man eine Ergebnisliste erstellen will... da kommt man schon auf min 3,5 GB, wenn man pro Ziffer von einem Byte Speicher ausgeht...

 

[maxwell-cs]

Ganz anderer Ansatz:
man erstellt eine Liste von Ziffern, die überhaupt zur Summe 40 kommen mit der Bedingung, dass es höchstens 10 Ziffern sein dürfen.... also z.B.
1, 2, 3, 4, 4, 6, 7, 8
4, 9, 9, 9

Die Einträge füllt man mit Nullen auf und permutiert sie durch.

warum nullen erst weglassen und dann wieder hinzufügen? einfach die ziffern in einer beliebigen reihenfolge, z.b. von vorne nach hinten, auf alle möglichen werte setzen und eine stelle zurückspringen, wenn die summe nicht mehr erreicht werden kann.

 

[1668mib]

In dem Gedankenspiel hab ich die Nullen weggelassen, weil sie nichts zur Summe beitragen... aber ich glaube, du hast gar nicht wirklich gelesen, was ich in dem Ansatz geschrieben hab...

 

[maxwell-cs]

klar hab ich das
ich bin mir nur recht sicher, dass der offensichtliche rekursive ansatz, der teilbäume in der enumeration abschneidet, bis vielleicht auf nen konstanten faktor optimal ist.

 

[1668mib]

@maxwell-cs: Naja konstante Faktoren interessieren ah nicht unbedingt. Wenn er optimal ist, dann lässt sich das auch sicher beweisen :-) [nicht dass der Beweis hier kommen muss]

 

[maxwell-cs]

ist man nur an der anzahl solcher summen interessiert, geht es natürlich deutlich schneller, hier ein ansatz mittels dynamischer programmierung mit laufzeit O(n * summe * d), wobei n die anzahl der stellen und d die anzahl der zur verfügung stehenden ziffern bezeichnet.
der fall von oben (summe 40, 10 summanden, ziffern 0-9) ist damit bei mir in unter 1ms erledigt.

#include <iostream>

using namespace std;

int num_sums(int sum,
             int num_digits,
             int min_val,
             int max_val)
{
   int data[num_digits][sum + 1];
   for (int i = 0; i < sum + 1; ++i) {
      if (i >= min_val && i <= max_val) {
         data[0][i] = 1;
      }
      else {
         data[0][i] = 0;
      }
   }
   for (int i = 1; i < num_digits; ++i){
      for(int s = 0; s < sum + 1; ++s) {
         data[i][s] = 0;
         for (int j = min_val; j <= max_val && j <= s; ++j){
            data[i][s] += data[i - 1][s - j];
         }
      }
   }
   return data[num_digits - 1][sum];
}

int main() {
   const int num_digits = 10;
   const int min_val = 0;
   const int max_val = 9;
   const int sum = 40;
   cout << num_sums(sum,
                    num_digits,
                    min_val,
                    max_val);
   return 0;
}

 

[efcoyote]

Die Ausgabe sieht ganz passabel aus, aber ohne Gewähr auf 100% Richtigkeit. Ist eher eine "optische" Lösung. Die einzelnen Schleifen in Methoden gepackt reduziert den Code wahrscheinlich enorm. Dafür sieht mal den Sinn vielleicht so besser.

const Int32 number = 40;

for (Int32 a = 1; a <= Math.Min(number, 9); a++)
	if (number - a > 0)
		for (Int32 b = a; b <= Math.Min(number - a, 9); b++)
			if (number - a - b > 0)
				for (Int32 c = b; c <= Math.Min(number - a - b, 9); c++)
					if (number - a - b - c > 0)
						for (Int32 d = c; d <= Math.Min(number - a - b - c, 9); d++)
							if (number - a - b - c - d > 0)
								for (Int32 e = d; e <= Math.Min(number - a - b - c - d, 9); e++)
									if (number - a - b - c - d - e > 0)
										for (Int32 f = e; f <= Math.Min(number - a - b - c - d - e, 9); f++)
											if (number - a - b - c - d - e - f > 0)
												for (Int32 g = f; g <= Math.Min(number - a - b - c - d - e - f, 9); g++)
													if (number - a - b - c - d - e - f - g > 0)
														for (Int32 h = g; h <= Math.Min(number - a - b - c - d - e - f - g, 9); h++)
															if (number - a - b - c - d - e - f - g - h > 0)
																for (Int32 i = h; i <= Math.Min(number - a - b - c - d - e - f - g - h, 9); i++)
																	if (number - a - b - c - d - e - f - g - h - i > 0)
																		for (Int32 j = i; j <= Math.Min(number - a - b - c - d - e - f - g - h - i, 9); j++)
																			if (number - a - b - c - d - e - f - g - h - i - j > 0) { }
																			else
																				System.Console.WriteLine(String.Format("{0} {1} {2} {3} {4} {5} {6} {7} {8} {9}", a, b, c, d, e, f, g, h, i, j));
																	else
																		System.Console.WriteLine(String.Format("{0} {1} {2} {3} {4} {5} {6} {7} {8}", a, b, c, d, e, f, g, h, i));
															else
																System.Console.WriteLine(String.Format("{0} {1} {2} {3} {4} {5} {6} {7}", a, b, c, d, e, f, g, h));
													else
														System.Console.WriteLine(String.Format("{0} {1} {2} {3} {4} {5} {6}", a, b, c, d, e, f, g));
											else
												System.Console.WriteLine(String.Format("{0} {1} {2} {3} {4} {5}", a, b, c, d, e, f));
									else
										System.Console.WriteLine(String.Format("{0} {1} {2} {3} {4}", a, b, c, d, e));
							else
								System.Console.WriteLine(String.Format("{0} {1} {2} {3}", a, b, c, d));
					else
						System.Console.WriteLine(String.Format("{0} {1} {2}", a, b, c));
			else
				System.Console.WriteLine(String.Format("{0} {1}", a, b));
	else
		System.Console.WriteLine(String.Format("{0}", a));

 

[holy]

Die Ausgabe sieht ganz passabel aus, aber ohne Gewähr auf 100% Richtigkeit. Ist eher eine "optische" Lösung. Die einzelnen Schleifen in Methoden gepackt reduziert den Code wahrscheinlich enorm. Dafür sieht mal den Sinn vielleicht so besser.

Ist aber leider falsch bzw. stellt nur einen Bruchteil der möglichen Zahlpartitionen dar.

 

[efcoyote]

Und welche fehlt beispielsweise?