Ziehen mit Zurücklegen aber ohne Reihenfolge

[Meflin]

Moin moin!

Ich stehe gerade etwas auf dem Schlauch.

Gegeben ist eine Menge, z.B. ABCD und eine Länge n (z.B. 3). Ermittelt werden sollen dann:

AAA
AAB
AAC
AAD
ABB
ABC
ABD
ACC
ACD
ADD
BBB
BBC
BBD
CCC

Meine Versuche führen entweder nur zu Permutationen (also zu wenigen) oder gleich zu den Kombinationen (also zu vielen). Knackpunkt ist, dass es nicht auf die Reihenfolge ankommt.

Irgendwie mag mir nix einfallen. Vielleicht hat ja jemand ne Idee :stupid: (Pseudocode reicht mir hier völlig, deswegen auch keine Delphi-Sparte ;) )

[jfheins]

Vielleicht hilft dir Wikipedia weiter :stupid:

http://de.wikipedia.org/wiki/Kombina...8Repetition.29

[Meflin]

Zitat:

Zitat von jfheins

Vielleicht hilft dir Wikipedia weiter :stupid:

Nciht wirklich. Da wird nur die Anzahl betrachtet (die mir persönlich ber völlig schnurz ist), aber nicht, wie man auf die Kombinationen selbst kommt.

[jfheins]

Aso ... wie wärs damit: (ungetestet, basiert auf deiner Aufzählung ausm ersten Post)

Code:

for (char eins = A; eins <= 'D'; eins++)
{
  for (char zwei = eins; zwei <= 'D'; zwei++)
  {
    for (char drei = zwei; drei <= 'D'; drei++)
    {
      print(eins + zwei + drei);
    }
  }
}

Du hast ja nach Pseudocode gefragt :P

Falls es nicht immer drei sein sollen: Rekusion benutzen ;)

[jaenicke]

Wie wäre es so? (Geht ab Delphi 2005)

Delphi-Quellcode:

procedure TForm164.Button1Click(Sender: TObject);
type
  TMyCharSet = set of Char;

  procedure GetCombinations(const Data: TMyCharSet; Count: Integer;
    Results: TStrings; CurChar: Char; CurPrefix: String = ''; CurPos: Integer = 1);
  var
    Cur: Char;
  begin
    for Cur in Data do
      if Cur >= CurChar then
        if CurPos < Count then
          GetCombinations(Data, Count, Results, Cur, CurPrefix + Cur, CurPos + 1)
        else
          Results.Add(CurPrefix + Cur);
  end;

var
  ResultList: TStringList;
begin
  ResultList := TStringList.Create;
  GetCombinations(['A', 'B', 'C', 'D'], 3, ResultList, 'A');
  ShowMessage(ResultList.Text);
  ResultList.Free;
end;

[jfheins]

Oh, dir war auch gerade langweilig ? :stupid:

Ich habs so:

Code:

public partial class Form1 : Form
    {
        private List<char> Buchstaben;

        public Form1()
        {
            InitializeComponent();

            Buchstaben = new List<char>();

            Buchstaben.AddRange(new char[] {'A', 'B', 'C', 'D'});
        }

        private void Kombinationen<Type>(IList<Type> Menge, int count)
        {
            Kombinationen<Type>(Menge, count, 0, new Stack<Type>());
        }

        private void Kombinationen<Type>(IList<Type> Menge, int count, int start, Stack<Type> Elemente)
        {
            if (count == 0)
            {
                String kombi = "";
                // evtl. Stringbuilder benutzen
                foreach (var elem in Elemente)
                {
                    kombi = elem.ToString() + ' ' + kombi;
                }
                listBox1.Items.Add(kombi);
            }
            else
            {
                for (int i = start; i < Menge.Count(); i++)
                {
                    Elemente.Push(Menge[i]);
                    Kombinationen<Type>(Menge, count - 1, i, Elemente);
                    Elemente.Pop();
                }
            }
        }

        private void button1_Click(object sender, EventArgs e)
        {
            Kombinationen<char>(Buchstaben, 3);
        }
    }

Hier übrigens mein Ergebnis:

Code:

A A A 
A A B 
A A C 
A A D 
A B B 
A B C 
A B D 
A C C 
A C D 
A D D 
B B B 
B B C 
B B D 
B C C 
B C D 
B D D 
C C C 
C C D 
C D D 
D D D

[Meflin]

Tjö Jungs, so hatt ich das eigentlich auch. Wieso ging das nicht :stupid:

Danke jedenfalls ;)