Zahlen-Kombinationen

[bioser]

Hallo, hat jemand eine Idee, wie man dies realisieren kann ?
Ich habe beispielsweise n Zahlen, mit denen ich n Kombinationen
erzeugen will.

Beispiel: 1 2 3 4

1 2 3 4
2 1 3 4
3 2 1 4
4 1 2 3

Im Prinzip wird immer das nächste Element nach vorne gepackt und dann die
restlichen Elemente angehängt. Dieser Algorithmus müßte auch irgendeinen
Namen haben. Komme aber nicht drauf.

[Sharky]

Hai bioser,

was Du machen möchtest ist eine Permutation. Dazu gibt es von Hagen einen Beitrag in der Code-Library.

[alzaimar]

Oder hier, ist kürzer:

Delphi-Quellcode:

Function NthPermutation (aString : String; aCount : Integer) : String;
Var
  d : Array Of Integer;
  g, i, n : Integer;

Begin
  n := Length (aString);
  setlength (d, n);
  d[1] := 1;
  For i := 2 to n - 1 do d[i] := i * d[i-1];
  Result := '';
  if aCount>=d[n-1]*n Then Exit;
  for i := n-1 downto 1 do begin
    g := (aCount div d[i]) + 1;
    Result  := Result  + aString[g];
    delete (aString, g, 1);
    aCount := aCount mod d[i];
    End;
  Result := Result  + aString;
End;

So erzeugst Du alle Permutationen eines Strings ('12345'):

Delphi-Quellcode:

Var
  i : Integer;
  s : String;

Begin
  i:=0;
  Repeat
    s := NthPermuation ('12345',i);
    inc (i);
    if s<>'' Then Memo1.lines.add (s);
  Until s= '';
End;

[bioser]

Zitat:

Zitat von alzaimar

So erzeugst Du alle Permutationen eines Strings ('12345'):

Delphi-Quellcode:

Var
  i : Integer;
  s : String;

Begin
  i:=0;
  Repeat
    s := NthPermuation ('12345',i);
    inc (i);
    if s<>'' Then Memo1.lines.add (s);
  Until s= '';
End;

Danke für Deine Antwort. Aber, ich weiß nicht, ob dies eine echte Permutation ist,
was ich haben möchte. Deine function spuckt mir folgende Permutationen aus:

54132
54213
54231
54312
54321

Ich brauche aber diese Kombinationen:

12345
21345
31245
41235
51234

Bei 1234 zum Beispiel so:

1234
2134
3124
4123

[alzaimar]

Hä? Willst du alle Permutationen? Davon gibt es N! (bei einem String der Länge N), oder nur ganz bestimmte? Mein Algo sollte 120 Permutationen von '12345' aufzählen.

Beschreib doch nochmal genau, welche Du brauchst...

Aha... im Eingangsposting sah das Anders aus:
Das hier?

Delphi-Quellcode:

Function BioserPermutation (aString : String; aCount : Integer) : String;
Var
  s :String;

Begin
  Assert (aCount < Length (aString), 'Unzulässige Sequenznummer');
  s := Copy (aString, aCount+1, 1); // Dieses Zeichen soll nach vorne;
  Delete (aString, aCount+1,1); // Das Zeichen löschen
  Result := s + aString;
End;

[bioser]

Ja, nochmal an einem Beispiel. Ich habe eine Liste von Zahlen:

1 2 3 4 //Das ist meine erste Kombination

Dann soll die zweite Zahl, also die "2", an die erste Stelle rücken
und die anderen in derselben Reihenfolge angehängt werden, nur daß die
"2" nicht berücksichtigt wird.

2 1 3 4 //Das ist meine zweite Kombination

Jetzt ist die nächste, die "3" an der Reihe, immer ausgehend von der
Originalreihenfolge in meiner Liste.

3 1 2 4 //Das ist meine dritte Kombination

und zuletzt diese Kombination

4 1 2 3

Hast Du jetzt verstanden, wie ich es haben möchte ?

[alzaimar]

Das macht die Funktion "BioserPermutation"

[freak4fun]

Hallo :hi:,

sowas?

Delphi-Quellcode:

procedure TForm1.Button1Click(Sender: TObject);
var
  i: Integer;
  lReihe: String;
  lTemp: Char;
begin
  lReihe := '1234';
  for i := 1 to length(lReihe) do
    begin
      lTemp := lReihe[1];
      lReihe[1] := lReihe[i];
      lReihe[i] := lTemp;
    end;
  ShowMessage(lReihe);
end;

Eins, zwei mehr Beispiele wären nicht schlecht. ;)

MfG
freak

[alzaimar]

Schau doch mal:

Code:

BioserPermutation ('12345',0) = > '12345'
BioserPermutation ('12345',1) = > '21345'
BioserPermutation ('12345',2) = > '31245'
BioserPermutation ('12345',3) = > '41235'
BioserPermutation ('12345',4) = > '51234'

[edit]Korrigiert, sodass es auch funktioniert :oops: [/edit]

[freak4fun]

Zitat:

Zitat von alzaimar

Code:

BioserPermutation ('12345',5) = > '51235'

Hier wird das Assert ausgelöst. :stupid: Vielleicht ist ihm das zu kompliziert. :zwinker:

MfG
freak

[alzaimar]

Nee, is ja auch Bullshit (von mir). Richtig muss es so heissen, wo oben verbessert!

[freak4fun]

Zitat:

Zitat von alzaimar

Nee, is ja auch *zensiert* (von mir). Richtig muss es so heissen, wo oben verbessert!

Hier programmieren auch Kinder. :shock: (:mrgreen:)

MfG
freak

[bioser]

Danke an alle. Sowas habe ich gesucht.

[freak4fun]

Zitat:

Zitat von bioser

Danke an alle. Sowas habe ich gesucht.

Ich würde jetzt schon gern wissen, welche Lösung du benutzt und warum. :angel2:

MfG
freak

[bioser]

Ich habe die function BioserPermutation benutzt. Leider habe ich aber gesehen,
daß mir das nicht richtig weiterhilft. Ich will jetzt nochmal genauer
werden. Ich benutze TList. Hier sind Daten abgelegt. Nun ist meine
Idee, daß ich mir eine Kopie von der Liste mache um damit dann
die Elemente nach obigen Beispielen zu permutieren.

XML-Code:

OrList:TList (Original)

0      1      2      3      4      5
Elem0  Elem1  Elem2  Elem3  Elem4  Elem5


CoList:TList (Kopie)

0      1      2      3      4      5
Elem0  Elem1  Elem2  Elem3  Elem4  Elem5

1      0      2      3      4      5
Elem1  Elem0  Elem2  Elem3  Elem4  Elem5

2      0      1      3      4      5
Elem2  Elem0  Elem1  Elem3  Elem4  Elem5

usw.

Delphi-Quellcode:

for i:=0 to CoList.count-1 do
begin
 //Dateninhalt verarbeiten
....
//nächste Permutation erzeugen 
end;

Genau das will ich machen !

[alzaimar]

Und genau das macht BioserPermutation, nur eben als String...

[freak4fun]

Möchtest du denn die Zwischenschritte auch haben, oder nur das endergebnis?

MfG
freak

[bioser]

Wenn ich die mit alzaimars function erzeugt habe, müßte ich
die Reihenfolge der Elemente in der Liste entsprechend
anpassen. Also, wenn ich 2 0 1 3 habe, müßten die Elemente
auf die enstprechende Position gesetzt werden.

XML-Code:

Original-Liste

F0   F1   F2   F3
0    1    2    3

Für die Permutation 2 0 1 3 würde dann gelten:

Feldinhalt von Feld 0 nach Feld 1
Feldinhalt von Feld 1 nach Feld 2
Feldinhalt von Feld 2 nach Feld 0
Feldinhalt von Feld 3 nach Feld 3

Dann könnte ich die Elemente in einer for-Schleife verarbeiten.

[alzaimar]

Oh, ist doch aber nicht schwer:

Delphi-Quellcode:

Procedure BiosenPermutator (aList, aOutput : TList; aCount : Integer);
Begin
  aOutput[0] := aList [aCount];
  For i := 0 to High (aList) do
    if i<aCount then 
      aOutput[i+1] := aList[i]
    else if i>aCount Then
      aOutput[i] := aList[i];
End;

Ungestet, aber sollte klappen.

[freak4fun]

Wie kommst du auf ' 2 0 1 3'? :gruebel:

Mit BioserPermutation ('0123', 3); komme ich auf 3012.

MfG
freak

[bioser]

Zitat:

Zitat von freak4fun

Wie kommst du auf ' 2 0 1 3'? :gruebel:

Mit BioserPermutation ('0123', 3); komme ich auf 3012.

MfG
freak

Ja, genau.

[bioser]

Zitat:

Zitat von alzaimar

Oh, ist doch aber nicht schwer:

Delphi-Quellcode:

Procedure BiosenPermutator (aList, aOutput : TList; aCount : Integer);
Begin
  aOutput[0] := aList [aCount];
  For i := 0 to High (aList) do
    if i<aCount then 
      aOutput[i+1] := aList[i]
    else if i>aCount Then
      aOutput[i] := aList[i];
End;

Ungestet, aber sollte klappen.

Ja, das sieht doch sehr gut aus. Danke. Das high brauche ich nicht, dafür setze ich alist.count-1 ein. Vorher sollte man noch die Ausgabeliste mit Create erzeugen. Die Ausgabeliste benötigt aber noch Speicherplatz, oder ? So funktioniert es nämlich nicht.

[alzaimar]

Der Aufrufer von BioserPermutation ist für die Speicherverwaltung zuständig. Weiterhin kannst/solltest Du die Datentypen sowie die High-funktion ggf an deinen Datentyp anpassen.
Wenn Deine Liste z.B. Als Array [0..3] Of Integer deklariert ist, dann wäre es ja schön blod, die zuerst in eine TList zu kopieren, dann zu BioserPermutieren, um sie abschließend wieder von der TList in das Array of Integer zurück zukopieren. Insofern verwendest Du meinen Code natürlich nur als Anhaltspunt.

[Eichhoernchen]

Wir haben damit jetzt gerade in der Schule begonnen,
vielleicht hilft dir das:

Delphi-Quellcode:

const n = 5;

var
  Form1: TForm1;
  zahl_gesetzt : array[1..n] of Boolean;
  zahlen : array[1..n] of Integer;
  count : integer;

implementation

{$R *.dfm}

procedure init;
var i : integer;
Begin
for i := 1 to n do
 zahl_gesetzt[i] := false;
 count := 0;
end;

procedure Ausgabe(zahl : integer);
Begin
 Form1.StringGrid1.Cells[0, count] := IntToStr(zahl);
 inc(count);
 Form1.Stringgrid1.RowCount := count;
 Form1.StringGrid1.Update;
 Form1.StringGrid1.Refresh;
end;

procedure permut(i : integer);
var j, k ,zahl : integer;
Begin
 for j := 1 to n do
  if not zahl_gesetzt[j]
    then Begin
          zahlen[i] := j;
          zahl_gesetzt[j] := true;
          if i < n
            then permut(i+1)
            else Begin
                  zahl := 0;
                  for k := n downto 1 do
                    zahl := zahl + (zahlen[k] * round(power(10, n-k)));
                  Ausgabe(zahl);
                 end;
          zahl_gesetzt[j] := false;
         end;
end;



procedure TForm1.BitBtn1Click(Sender: TObject);
begin
Init;
permut(1);
end;

Hoffe es hilft!