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>
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.
ich finde dazu passt auch die thematik vom rucksackproblem. besprochen in:
Mathematik-Problem: Platz in einem Materiallager optimal ausnutzen
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
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.
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.
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!
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