Laden...

[Snippet] Alle Kombinationen von n Elementen (rekursiv)

Erstellt von Joetempes vor 15 Jahren Letzter Beitrag vor 14 Jahren 19.823 Views
Joetempes Themenstarter:in
888 Beiträge seit 2007
vor 15 Jahren
[Snippet] Alle Kombinationen von n Elementen (rekursiv)

Beschreibung:

**
Ermittelt alle möglichen Kombinationen einer n-elementigen Menge.
Generischer Ansatz, Listen verschiedener Typen können verwendet werden.**



//Eure Menge
List<string> sourceList = new List<string> { "A", "B", "C" };
//List<int> sourceList = new List<int> { 1, 2, 3 };

//Aufruf
for (int i = 1; i <= sourceList.Count; i++)
{
      //bzw. new int[i]
       this.buildAllCombinationsRecursive(new string[i], sourceList, 0); 
}

/// <summary>
/// Bildet die Kombinationen
/// </summary>
/// <param name="i_targetList">Ziel Liste</param>
/// <param name="i_sourceList">Liste der Elemente</param>
/// <param name="i_currentPos">Aktuelle Position</param>
private void buildAllCombinationsRecursive<TSource>(IList<TSource> i_targetList, IList<TSource> i_sourceList, int i_currentPos)
        {
            if (i_currentPos == i_targetList.Count)
            {
                string combination = "";
			    for(int i = 0; i < i_targetList.Count; i++)
			    {
				    combination += i_targetList[i] + " ";
			    }

			    Console.WriteLine(combination);
			    return;
            }
            for (int i = 0; i < i_sourceList.Count; i++)
            {
                i_targetList[i_currentPos] = i_sourceList[i];
                this.buildAllCombinationsRecursive(i_targetList, i_sourceList, i_currentPos + 1);
            }
        }

Der Output in dem Beispiel sieht dann so aus:

A
B
C
A A
A B
A C
B A
B B
B C
C A
C B
C C
A A A
A A B
A A C
A B A
A B B
A B C
A C A
A C B
A C C
B A A
B A B
B A C
B B A
B B B
B B C
B C A
B C B
B C C
C A A
C A B
C A C
C B A
C B B
C B C
C C A
C C B
C C C

Schlagwörter: <Kombinatorik>

49.485 Beiträge seit 2005
vor 15 Jahren

Hallo Joetempes,

schreib doch besser eine generische Methode, also statt für String [] besser mit IList<T>. Dann kann man beliebige Listen übergeben.

herbivore

PS: Hier noch eine Variante von mir: Anzahl und Berechnung möglicher Kombinationen und Permutationen. Etwas weiter unten in dem verlinkten Thread findet sich dann noch mein Code für die Berechnung der Permutationen statt aller Kombinationen.

Joetempes Themenstarter:in
888 Beiträge seit 2007
vor 15 Jahren

Hallo herbivore,

ok mach ich.

Gelöschter Account
vor 15 Jahren

ich finde dazu passt auch die thematik vom rucksackproblem. besprochen in:
Mathematik-Problem: Platz in einem Materiallager optimal ausnutzen

Joetempes Themenstarter:in
888 Beiträge seit 2007
vor 15 Jahren

... Snippet geändert in eine generische Version.

Grüße

2.891 Beiträge seit 2004
vor 15 Jahren

Hallo Joetempes,

sehe ich das richtig, dass das eigentliche Resultat nur auf der Console ausgegeben wird?
Denn eigentlich hätte ich erwartet, dass es dann in der Targetlist steht. In deinem Beispiel (ABC) erhalte ich aber in den 3 Schleifendurchläufen nur jeweils eine Liste mit nur einem Element drin (C, CC und CCC)...

Gruß
dN!3L

Joetempes Themenstarter:in
888 Beiträge seit 2007
vor 15 Jahren

Die Target-Liste wird für die Rekursion benötigt, momentan wird das Ergebniss nur auf der Console ausgegeben. Es sollte für jederman ein leichtes sein die Ergebnisse in eine neue Liste zu schreiben an Stelle der Consolen-Ausgabe.

A
8 Beiträge seit 2008
vor 15 Jahren

Wenn die Listenlänge die Zahlenbasis B darstellt und die Listenelemente die einzelnen 'Ziffern' des Nummernsystems, dann zählst Du einfache alle Zahlen bis zur Länge B zur Basis B auf.
Wenn Du eine Liste der Ziffern 0..9 übergibst bekommst Du also alle Zahlen von 0 bis 99999999.

Versuche Dich mal an Permutationen, Variationen, Kombinationen usw. Es sollte durch klitzekleine Änderung des Originalcodes möglich sein, diese Grundfunktionen der Kombinatorik herzuleiten.

Alles geht.

H
17 Beiträge seit 2010
vor 14 Jahren

Das klappt ganz wunderbar.

Kann man das auch insofern abändern, als dass immer nur höchstens drei und mindestens zwei Elemente kombiniert werden und wenn ein Element verwendet wurde, in derselben Kombination nicht nochmal verwendet werden kann? Blicke da nicht so ganz durch!

49.485 Beiträge seit 2005
vor 14 Jahren

Hallo HaraldM,

klar kann man das leicht so ändern.

Eine Lösung für Kombinationen ohne Wiederholung findest du über den Link im zweiten Beitrag.

Um die Anzahl der Elemente, die in einer Kombination verwendet werden, zu begrenzen, muss du die Rekursion nach entsprechend vielen Schritten abbrechen, z.B. indem du einen zusätzlichen Parameter für den (Rest-)Level einführst.

Das muss an Hinweisen für die von dir gewünschte Variante bitte genügen, da das ein Snippets-Thread ist.

herbivore