baumalgorithmus-implementierung c#

Question

Ich habe einige Probleme bei der Lösung eines Algorithmus, der dazu dient, alle möglichen Kombinationen von Elementen aus N verschiedenen Listen zu finden (wobei N>=2 && N<=7 -> diese Zahl ist fest und ich kann für jedes N eine andere Methode erstellen). Das Problem sieht folgendermaßen aus: Ich habe fünf Wörterbücher:

IDictionary<int, MyEnum> listOne; 
IDictionary<int, MyEnum> listTwo;
IDictionary<int, MyEnum> listThree;
IDictionary<int, MyEnum> listFour;
IDictionary<int, MyEnum> listN;

enum MyEnum
    {
    MyEnumOne,
    MyEnumTwo,
    MyEnumThree,
    MyEnumFour,
    MyEnumFive,
    MyEnumOther
   }

die eine beliebige Anzahl von Elementen haben können (nicht mehr als 100, und in den meisten Fällen werden sie zwischen 32 und 64 Elemente haben) und wobei MyEnum eine einfache Aufzählung von Namen mit einigen Werten ist.

Für jede mögliche Kombination habe ich eine Methode, die die Kombination untersucht und prüft, ob sie einige Bedingungen erfüllt, und wenn sie erfüllt sind, speichert einige Daten auf der Grundlage der Kombination.

Ich habe versucht, einfache verschachtelte Iterationen mit foreachs für jede Liste, die wie erwartet, nehmen Ewigkeiten zu laufen!

Jede Hilfe, wo ich anfangen sollte, was ich tun sollte, oder was ich nicht tun sollte, ist mehr als willkommen, und wenn Sie weitere Informationen benötigen, fragen Sie einfach!

* *EDIT: Eine Kombination auf der Grundlage von fünf Listen, wie oben gezeigt, wäre zum Beispiel:

(MyEnumOne, MyEnumOne, MyEnumFour, MyEnumFive, MyEnumTwo)

und, wie diese Kombination, kann mehrere Male erscheinen (wie MyEnumOne Wert kann viele Male auf listOne, etc.), ich habe auch, Aufzeichnung zu halten, wie oft diese Kombination geschieht.

Answer 1

Diese Art von Problemen können Sie mit LINQ leicht lösen.

var solutions = from pair1 in listOne
                where IsCandidate(pair1)
                from pair2 in listTwo
                where IsCandidate(pair1, pair2)
                from pair3 in listThree
                where IsCandidate(pair1, pair2, pair3)
                from pair4 in listFour
                where IsCandidate(pair1, pair2, pair3, pair4)
                from pair5 in listFive
                where IsCandidate(pair1, pair2, pair3, pair4, pair5)
                from pair6 in listSix
                where IsCandidate(pair1, pair2, pair3, pair4, pair5, pair6)
                from pair7 in listSeven
                where IsSolution(pair1, pair2, pair3, pair4, pair5, pair6, pair7)
                select new { pair1, pair2, pair3, pair4, pair5, pair6, pair7 };

Natürlich ist dieser Ansatz nur gültig, weil die Anzahl der Listen zur Kompilierungszeit bekannt ist. Ein alternativer Ansatz wäre eine generische Methode zur Erstellung der möglichen Kombinationen, wie Eric Lippert zeigt in seinem Beitrag .

All diese Zwischenstufen where über die gesamte Abfrage, um ungültige Kombinationen so schnell wie möglich herauszufiltern.

エディトリアル

Feste Lösung, um effizient zu zählen, wie oft eine gleiche Kombination vorkommt, wobei die Schlüssel der ursprünglichen Quelle ignoriert werden.

Um dies zu erreichen, werde ich auf jedes Wörterbuch eine Transformation anwenden. Ich werde jedes Wörterbuch in ein neues Wörterbuch umwandeln, wobei der Schlüssel der Aufzählungswert und der Wert die Anzahl der Vorkommen dieses Aufzählungswerts im ursprünglichen Wörterbuch ist.

IDictionary<MyEnum, int> CountOccurrences(IEnumerable<MyEnum> values)
{
    return (from e in values group e by e).ToDictionary(grp => grp.Key, grp => grp.Count());
}

var solutions = from p1 in CountOccurrences(listOne.Values)
                where IsCandidate(p1)
                from p2 in CountOccurrences(listTwo.Values)
                where IsCandidate(p1, p2)
                from p3 in CountOccurrences(listThree.Values)
                where IsCandidate(p1, p2, p3)
                from p4 in CountOccurrences(listFour.Values)
                where IsCandidate(p1, p2, p3, p4)
                from p5 in CountOccurrences(listFive.Values)
                where IsCandidate(p1, p2, p3, p4, p5)
                from p6 in CountOccurrences(listSix.Values)
                where IsCandidate(p1, p2, p3, p4, p5, p6)
                from p7 in CountOccurrences(listSeven.Values)
                where IsSolution(p1, p2, p3, p4, p5, p6, p7)
                select new {
                    E1 = p1.Key,
                    E2 = p2.Key,
                    E3 = p3.Key,
                    E4 = p4.Key,
                    E5 = p5.Key,
                    E6 = p6.Key,
                    E7 = p7.Key,
                    Times = p1.Value * p2.Value * p3.Value * p4.Value * p5.Value * p6.Value * p7.Value
                };

Answer 2

Im Allgemeinen sollten Sie bei solchen Problemen versuchen konstruieren die Lösungen zu finden und nicht blindlings den gesamten Suchraum nach ihnen zu durchforsten.

Ich gehe davon aus, dass Sie in Wirklichkeit Folgendes tun müssen: - Sie haben N Listen, wobei jede Liste i aus L(i) Elementen besteht. - Sie wollen alle Kombinationen der Länge N erzeugen, bei denen das erste Element aus der ersten Liste stammt, das zweite Element aus der zweiten Liste und so weiter.

Es scheint keine Möglichkeit zu geben, alle Kombinationen auf die harte Tour zu erstellen. Alle 100 Elemente ^ N ~ 10^14... was Äonen dauern wird.

Ich schließe mich der Forderung nach kleinen Mustern und Bedingungen an, die erfüllt werden müssen.