Algorithmus zur Kombinatorik

Mein erster Gedanke wäre dabei Rekursion, besser gesagt, Backtracking.

Hierzu mal kurz eine (der tausenden) Definition:

Die Gesamtlösung wird schrittweise aus Teillösungen zusammengesetzt. Falls man dabei in eine Sackgasse gerät, werden der letze Schritt oder mehrere der letzen Schritte rückgängig gemacht. Aus einer so reduzierten Teillösung versucht man, auf einen anderen Weg eine Gesamtlösung aufzubauen.

Wäre also an Deinem Beispiel und mit der Zahl 7:

1
1 + 1 = 2
1 + 1 + 1 = 3
1 + 1 + 1 + 0 = 3
1 + 1 + 1 + 0 + 0 = 3
1 + 1 + 1 + 0 + 0 + 0 = 3
1 + 1 + 1 + 0 + 0 + 0 + 1 = 4 -> Sackgasse, zurück und nächste Möglichkeit
1 + 1 + 1 + 0 + 0 + 0 + 2 = 5 -> Sackgasse, zurück und nächste Möglichkeit
1 + 1 + 1 + 0 + 0 + 0 + 3 = 6 -> Sackgasse, Möglichkeiten erschöpft also noch weiter zurück
1 + 1 + 1 + 0 + 0 + 1 + 1 = 5 -> Sackgasse, zurück und nächste Möglichkeit
1 + 1 + 1 + 0 + 0 + 1 + 2 = 6 -> Sackgasse, zurück und nächste Möglichkeit
1 + 1 + 1 + 0 + 0 + 1 + 3 = 7 -> Erfolg!!

Klar soweit?

Gruß Spawn

Edit: Merk grad, dass die Erklärung mitunter etwas wirr ist. Aufgrund momentaner Langeweile schreib ich ein Programm, wenns Dir nix ausmacht

Danke dir Spawn!

Hab mir schon gedacht, dass das in diese Richtung gehen wird. Inzwischen hab ich auch mal ein wenig gebastelt. Da Rekursion bei mir nicht nicht besonders viele Sympathiepunkte hat (ich denke lieber vorwärts als rückwärts ), bau ich grad an einer iterativen Lösung. Bei 7 Ebenen geht das grad noch

Wenn's nicht funktionieren sollte, werde ich mich doch mal an die rekursive Variante ranschmeißen.

Vielen Dank!

greez
JoSsiF

Das hält mich allerdings nicht davon ab, es auch zu versuchen

Das hält mich allerdings nicht davon ab, es auch zu versuchen

Aber gern!

So, also meine iterative Geschichte hier funktioniert. Bin dennoch nicht ganz glücklich damit, da die Performance doch arg zu wünschen übrig lässt. Ist aber nicht so schlimm, da es um einen wahrscheinlich einmalig angewendeten Importfilter geht.

Falls deine Lösung funzt, Spawn, würde mich der Code brennend interessieren

greez
JoSsiF

Da hat sich grad ein fieser Fehler eingeschlichen, das Ergebnis stimmt zwar, aber er nimmt nicht Deine vorgegebenen Zahlen, sondern nur 1,2 oder 3 als Summand ???

Habs gleich

Edit: Aju, Fehler is klar. Gleich fertig!

So, fertig. Ist vielleicht noch nicht 100%ig elegant, aber geht. Das ganze ist ne C#-Konsolenanwendung geworden.

using System;
using System.Collections.Generic;
using System.Text;
using System.Collections;

namespace ConsoleApplication1
{
    class Program
    {
        private ArrayList summandenArray;
        private int summe = 0; //gewünschte Summe
        private int wert; //aktueller Wert
        private int rekursionstiefe;
        private ArrayList weg; //der momentane Weg
        private ArrayList loesungen; //alle Lösungen

        public Program(int summe)
        {
            weg = new ArrayList();
            loesungen = new ArrayList();
            this.summe = summe;
            initSummanden();
            Console.WriteLine("Gewünschte Zahl: " + summe.ToString());
            wert = 0;
            rekursionstiefe = 0;
            rekursion();
            Console.Read();
           
        }

        private void rekursion()
        {
            //ist Endknoten erreicht?
            if (rekursionstiefe == 7)
            {
                //ist das Problem vollständig gelöst?
                if (wert == summe)
                {
                    loesungen.Add(weg);
                    Console.Write("\nLösung: ");
                    for (int i = 0; i < weg.Count; i++)
                        Console.Out.Write((int)weg[i]);
                }
                return;
            }
            else
            {
                for (int i = 0; i < ((ArrayList)summandenArray[rekursionstiefe]).Count; i++)
                {
                    int summand = (int)((ArrayList)summandenArray[rekursionstiefe])[i];
                    weg.Add(summand);
                    wert += summand;
                    rekursionstiefe++;
                    rekursion();
                    rekursionstiefe--;
                    wert -= summand;
                    weg.RemoveAt(weg.Count - 1);
                }
            }
        }

        private void initSummanden()
        {
            summandenArray = new ArrayList();
            ArrayList summanden = new ArrayList();
            //die ersten 3 Summandenarrays
            summanden.Add(1);
            summanden.Add(2);
            summanden.Add(3);
            summanden.Add(4);
            summanden.Add(5);
            summandenArray.Add(summanden);
            summandenArray.Add(summanden);
            summandenArray.Add(summanden);
            //das 4te
            summanden = new ArrayList();
            summanden.Add(0);
            summanden.Add(1);
            summanden.Add(2);
            summanden.Add(3);
            summanden.Add(4);
            summanden.Add(5);
            summandenArray.Add(summanden);
            //das 5te
            summanden = new ArrayList();
            summanden.Add(0);
            summanden.Add(1);
            summanden.Add(2);
            summanden.Add(3);
            summandenArray.Add(summanden);
            //das 6te
            summanden = new ArrayList();
            summanden.Add(0);
            summanden.Add(1);
            summanden.Add(2);
            summanden.Add(3);
            summanden.Add(4);
            summandenArray.Add(summanden);
            //und das 7te
            summanden = new ArrayList();
            summanden.Add(1);
            summanden.Add(2);
            summanden.Add(3);
            summandenArray.Add(summanden);
            Console.WriteLine("SummandenArrays:");
            for (int i = 0; i < summandenArray.Count; i++)
            {
                ArrayList tempList = (ArrayList)summandenArray[i];
                for (int j = 0; j < tempList.Count; j++)
                    Console.Write((int)tempList[j]);
                Console.WriteLine();
            }
        }

        static void Main(string[] args)
        {
            int summe;
            try
            {
                summe = int.Parse(args[0]);
            }
            catch (Exception) { summe = 0; }
            Program program = new Program(summe);
        }
    }
}


Vielen Dank für deine große Mühe!

Denke mal, dass ich gegen Ende der Woche den Filter fertig habe. Wenn dann noch Zeit ist, übersetze ich mir das mal nach PHP. Mit der rekursiven Funktion sieht's auf jeden Fall eleganter aus. Und wenn's auch noch schneller ist, dann werd ich wohl mal ernsthaft drüber nachdenken, das einzusetzen

Danke dir!

greez
JoSsiF

Hmm, naja, Problem dabei ist, dass Rekursion zwar oft eleganter, aber prinzipiell immer langsamer ist

Ich teste ja mit dem Programm auch alle Möglichkeiten und filtere dann alle richtigen raus, also Zeitgewinn hast Du wahrscheinlich nicht.

Spaß gemacht hat's trotzdem

Ach ja, gibt da auch noch paar performancesteigernde Verbesserungsmöglichkeiten. Z.B. dass die Rekursion gleich "zurückspringt" wenn der aktuelle Wert größer oder gleich der gewünschten Summe ist, aber noch nicht alle 7 Summanden "verbraten" sind. Aber wie gesagt: An ne Iteration wird's wohl nicht rankommen.

Ach ja, gibt da auch noch paar performancesteigernde Verbesserungsmöglichkeiten. Z.B. dass die Rekursion gleich "zurückspringt" wenn der aktuelle Wert größer oder gleich der gewünschten Summe ist, aber noch nicht alle 7 Summanden "verbraten" sind.

Hängt sicher auch davon ab, wie umfangreich die Summenbildung ist. Wenn ich das Programm auf meinen Fall umsetze, könnte das u.U. so aufwändig sein, dass der Performance-Gewinn gleich wieder verloren geht.

Aber sei's drum: man lernt nie aus

Noch was zum Thema Performance Tuning.

Wenn du deinen Zahlenpool nicht von vorne sondern von hinten angehst wirst du schneller sein.

Bsp.:
Zahl 7
Pool (9, 6, 3, 1)

9 kompletter schmarn --> nächste Zahl
6 Ja okay, ist kleiner also nächste Zahl
6 + 6 zu groß
6 + 3 noch immer
6 + 1 ok

Damit wirst du die Performance, wenn ich das richtig verstanden habe, erhöhen können.

MFG
BWA

Das kommt wahrscheinlich drauf an. Wenn Du große Zahlen suchst, ist von hinten schneller, bei kleinen von vorn.
Müsste man mal testen. Aber interessante Idee.

@BWA: Die Idee ist interessant. Das fällt dann bei mir mal - genau wie Spawns rekursiver Algorithmus - in die Kategorie "wenn ich hinterher noch Zeit hab"

Aber danke, dass du dir Gedanken gemacht hast!

greez
JoSsiF

Darf man eigentlich fragen, welchen Gedanken Du damit verfolgst, Zahlen in 7 Summanden zu zerlegen?

Kryptografie? Obwohl, meintest ja was von nem Importfilter... ???