Willkommen auf myCSharp.de! Anmelden | kostenlos registrieren
 | Suche | FAQ

Hauptmenü
myCSharp.de
» Startseite
» Forum
» Suche
» Regeln
» Wie poste ich richtig?

Mitglieder
» Liste / Suche
» Wer ist online?

Ressourcen
» FAQ
» Artikel
» C#-Snippets
» Jobbörse
» Microsoft Docs

Team
» Kontakt
» Cookies
» Spenden
» Datenschutz
» Impressum

  • »
  • Community
  • |
  • Diskussionsforum
[Snippet] Alle Kombinationen von n Elementen (rekursiv)
Joetempes
myCSharp.de - Member

Avatar #avatar-3309.jpg


Dabei seit:
Beiträge: 914
Herkunft: Germany

Themenstarter:

[Snippet] Alle Kombinationen von n Elementen (rekursiv)

beantworten | zitieren | melden

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>
Dieser Beitrag wurde 7 mal editiert, zum letzten Mal von Joetempes am .
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 52329
Herkunft: Berlin

beantworten | zitieren | melden

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.
private Nachricht | Beiträge des Benutzers
Joetempes
myCSharp.de - Member

Avatar #avatar-3309.jpg


Dabei seit:
Beiträge: 914
Herkunft: Germany

Themenstarter:

beantworten | zitieren | melden

Hallo herbivore,

ok mach ich.
private Nachricht | Beiträge des Benutzers
Gelöschter Benutzer

beantworten | zitieren | melden

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

Avatar #avatar-3309.jpg


Dabei seit:
Beiträge: 914
Herkunft: Germany

Themenstarter:

beantworten | zitieren | melden

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

Grüße
private Nachricht | Beiträge des Benutzers
dN!3L
myCSharp.de - Experte

Avatar #avatar-2985.png


Dabei seit:
Beiträge: 3138

beantworten | zitieren | melden

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
private Nachricht | Beiträge des Benutzers
Joetempes
myCSharp.de - Member

Avatar #avatar-3309.jpg


Dabei seit:
Beiträge: 914
Herkunft: Germany

Themenstarter:

beantworten | zitieren | melden

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.
private Nachricht | Beiträge des Benutzers
alzaimar
myCSharp.de - Member



Dabei seit:
Beiträge: 8
Herkunft: Berlin

beantworten | zitieren | melden

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.
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von alzaimar am .
Alles geht.
private Nachricht | Beiträge des Benutzers
HaraldM
myCSharp.de - Member



Dabei seit:
Beiträge: 16

beantworten | zitieren | melden

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!
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 52329
Herkunft: Berlin

beantworten | zitieren | melden

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
private Nachricht | Beiträge des Benutzers