Autor Beitrag
juleins
Hält's aus hier
Beiträge: 10



BeitragVerfasst: Di 10.07.07 01:02 
hey.
ich möchte alle möglichen Kombinationen von 9-Stelligen Zahlen erzeugen, in denen jede Ziffer (1 bis 9) aber nur einmal vorkommt.

eine erste idee wäre sicher:

ausblenden Delphi-Quelltext
1:
2:
3:
for i := 123456789 to 987654321 do
   if (keine ziffer doppelt) then
       speichern



dies erscheint mir aber nicht sehr elegant und schnell, da sehr viele zahlen "umsonst" erzeugt werden. Ich bin mir sicher es gibt eine bessere Lösung, ich komme nur nicht drauf.

kann mir jmd helfen?
grüßle juleins

Moderiert von user profile iconTino: Code- durch Delphi-Tags ersetzt.
Calculon
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 676

Win XP Professional
Delphi 7 PE, Delphi 3 PRO
BeitragVerfasst: Di 10.07.07 01:18 
Aufgabe: Wieviel 9-stellige Zahlen gibt es?

Lösung: n = 9 * 10 * 10 * 10 * 10 * 10 * 10 * 10 * 10 = 9 * 10^8 = 900.000.000

Gruß

Calculon
--
Blawen
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 614
Erhaltene Danke: 33

Win XP, Vista, 7
Delphi 5 Prof., BDS 2006 Prof. RAD Studio XE
BeitragVerfasst: Di 10.07.07 01:29 
user profile iconCalculon hat folgendes geschrieben:
Aufgabe: Wieviel 9-stellige Zahlen gibt es?

Lösung: n = 9 * 10 * 10 * 10 * 10 * 10 * 10 * 10 * 10 = 9 * 10^8 = 900.000.000
Da jede Ziffer aber nur einmal vorkommen darf, werden es aber schon ein paar weniger sein ;-)

_________________
Es kompilert, wir können ausliefern.
Und es kompiliert wieder - das Update ist fertig - bitte 100 Euro ;-)
juleins Threadstarter
Hält's aus hier
Beiträge: 10



BeitragVerfasst: Di 10.07.07 01:56 
mh ja klar..
ich will aber nicht wissen wieviele es gibt.
Ich brauche die Kombinationen. ;)
Calculon
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 676

Win XP Professional
Delphi 7 PE, Delphi 3 PRO
BeitragVerfasst: Di 10.07.07 02:11 
juleins hat folgendes geschrieben:
[..] in denen jede Ziffer (1 bis 9) aber nur einmal vorkommt.

:oops: hab ich übersehen... user defined image

Gruß

Calculon
--
ene
ontopic starontopic starontopic starontopic starontopic starofftopic starofftopic starofftopic star
Beiträge: 779
Erhaltene Danke: 1

Vista, XP, W2K
Delphi, .Net, Deutsch und Englisch
BeitragVerfasst: Di 10.07.07 07:27 
Also so etwas wie Soduko? Nicht hübsch, aber man könnte mit einer Schleife 1 bis 9 immer einen Array erzeugen und nur Zahlen verwenden, die nicht in [x..y] sind.

_________________
Wir, die guten Willens sind, geführt von Ahnungslosen, Versuchen für die Undankbaren das Unmögliche zu vollbringen.
Wir haben soviel mit so wenig so lange versucht, daß wir jetzt qualifiziert sind, fast alles mit Nichts zu bewerkstelligen.
alzaimar
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 2889
Erhaltene Danke: 13

W2000, XP
D6E, BDS2006A, DevExpress
BeitragVerfasst: Di 10.07.07 07:39 
Such mal nach 'Permutation'. Das Thema hatten wir schon öfter. Zur Anzahl:
Für die 1.Stelle gibt es 9 Möglichkeiten, für die 2. nur noch 8, für die 3. nur noch 7 (denn zwei Ziffern sind ja schon vergeben)....

Macht also 9*8*7*6*5*4*3*2 = 9! Kombinationen.

Hier ist meine Version:
ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
Type
  TCharSet = Set Of Char;

Procedure TForm1.Permutation(Const aString, aResult : String; anIndex : Integer; aUsedChars : TCharSet);
Var
  i : Integer;

Begin
  For i:=1 to Length (aString) Do
    If Not (aString[i] in aUsedChars) Then
      If anIndex = Length (aString) Then
        Memo1.lines.add(aResult+aString[i])
      Else
        Permutation (aString, aResult + aString[i], anIndex + 1, aUsedChars + [aString[i]]);
End;

Aufruf mit
Delphi-Quellcode:
ausblenden Delphi-Quelltext
1:
Permutation ('1234567''' ,1 , [])					

Hier wird ein Memo als Container verwendet. Das ist natürlich eine riesige Performance-Bremse.

_________________
Na denn, dann. Bis dann, denn.
oldmax
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 380


D3 Prof, D4 Prof
BeitragVerfasst: Di 10.07.07 13:23 
Hi
Ich glaub, die Lösung ist gar nicht so schwer.
Nimm einen String '123456789'( ja, sehr unbeliebt....)
Dann zwei Schleifen

ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
For i:=1 to Length(ZahlenString)-1 do
begin
  For J :=i+1 to Length(ZahlenString) do
  begin
    Merker:=ZahlenString[i];
    ZahlenString[i]:=ZahlenString[J];
    ZahlenString[J]:=Merker;
  end;
end;


und dann lass dich vom Ergebnis überraschen...
Übrigends, Zahlen können nicht doppelt ersscheinen, weil sie ja auch nur 1x im String vorkommen und nur getauscht werden. Es kommt nix hinzu und es geht auch nix weg....

Gruß oldmax

PS: ich vergaß - Entweder die erzeugten Strings in eine Listbox schreiben oder einen Zähler mitlaufen lassen.

_________________
Zier dich nich so, ich krieg dich schon....
Blawen
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 614
Erhaltene Danke: 33

Win XP, Vista, 7
Delphi 5 Prof., BDS 2006 Prof. RAD Studio XE
BeitragVerfasst: Di 10.07.07 13:53 
user profile iconoldmax hat folgendes geschrieben:
ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
For i:=1 to Length(ZahlenString)-1 do
begin
  For J :=i+1 to Length(ZahlenString) do
  begin
    Merker:=ZahlenString[i];
    ZahlenString[i]:=ZahlenString[J];
    ZahlenString[J]:=Merker;
  end;
end;

PS: ich vergaß - Entweder die erzeugten Strings in eine Listbox schreiben oder einen Zähler mitlaufen lassen.

PS:
Den Ausgangsstring nicht vergessen mitzuzählen, bzw. auszugeben!

_________________
Es kompilert, wir können ausliefern.
Und es kompiliert wieder - das Update ist fertig - bitte 100 Euro ;-)
juleins Threadstarter
Hält's aus hier
Beiträge: 10



BeitragVerfasst: Di 10.07.07 17:15 
hey oldmax

deine routine liefert mir nur 36 lösungen.
ich sehe aber auf den ersten blick, dass es noch mehr geben muss.
Irgendwo steckt da noch ein fehler.

grüßle juleins
JayEff
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 2971

Windows Vista Ultimate
D7 Enterprise
BeitragVerfasst: Di 10.07.07 17:36 
user profile iconjuleins hat folgendes geschrieben:
deine routine liefert mir nur 36 lösungen.
ich sehe aber auf den ersten blick, dass es noch mehr geben muss.
Richtig, denn 9! ist 362880.

_________________
>+++[>+++[>++++++++<-]<-]<++++[>++++[>>>+++++++<<<-]<-]<<++
[>++[>++[>>++++<<-]<-]<-]>>>>>++++++++++++++++++.+++++++.>++.-.<<.>>--.<+++++..<+.
alzaimar
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 2889
Erhaltene Danke: 13

W2000, XP
D6E, BDS2006A, DevExpress
BeitragVerfasst: Di 10.07.07 17:51 
Wieso nimmst Du nicht einfach meinen Codeschnipsel
Magst Du ihn etwa nicht? :eyes: Dabei hab ich mir soooo viel Mühe gegeben... :bawling:

:zwinker:

_________________
Na denn, dann. Bis dann, denn.
juleins Threadstarter
Hält's aus hier
Beiträge: 10



BeitragVerfasst: Di 10.07.07 18:28 
hey tut mir leid alzaimar^^
ich hab gerade vorher erst wieder reingeschaut
und hab nur den von oldmax ausprobiert.

Der sah so schön einfach aus :)

jetzt versuch ichs mal mit deinem, keine sorge

danke & grüßle juleins
alzaimar
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 2889
Erhaltene Danke: 13

W2000, XP
D6E, BDS2006A, DevExpress
BeitragVerfasst: Mi 11.07.07 09:50 
:dance2:

_________________
Na denn, dann. Bis dann, denn.
Horst_H
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1643
Erhaltene Danke: 236

WIN10,PuppyLinux
FreePascal,Lazarus
BeitragVerfasst: Mi 11.07.07 15:47 
Hallo,

wie wäre es mit diesen alten Klamotten ;-)
ausblenden volle Höhe Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:
108:
109:
110:
111:
112:
113:
114:
115:
116:
117:
118:
119:
120:
121:
122:
123:
124:
125:
126:
127:
128:
129:
130:
131:
132:
133:
134:
135:
136:
137:
138:
139:
140:
141:
142:
143:
144:
145:
146:
147:
148:
149:
150:
151:
152:
153:
154:
155:
156:
program PermuteString;
{$Apptype console}
uses
  sysutils,classes;
const
  nmax = 9;
Type
  TCharSet = Set Of Char;

var
  sl : TStringlist;
  PermString : string;
  T0,T1 : TdateTime;
  j  : INt64;
  i,
  n : integer;
  Zeichen : char;


function Next(var a:string): Boolean;
var
   k,j,r,s : integer;
   temp    : char;
   procedure swap(i,j :integer);
   begin
     temp := a[i];
     a[i] := a[j];
     a[j] := temp;
   end;

begin
   k := n-1;
   while a[k] > a[k+1do
      k:=k-1;
   if k <> 0 then
   begin
      j := n;
      while a[k] > a[j] do
          j:=j-1;
      swap(j,k);
      r:=n;
      s:=k+1;
      while r>s do
      begin
         swap(r,s);
         r:=r-1;
         s:=s+1;
      end;
      Next:= true;
   end
   else
   {Reverse order reached -> end}
      Next := false
end;

Procedure Permutation(Const aString, aResult : String; anIndex : Integer; aUsedChars : TCharSet);
Var
  i : Integer;

Begin
  For i:=1 to Length (aString) Do
    If Not (aString[i] in aUsedChars) Then
      If anIndex = Length (aString) Then
        SL.add(aResult+aString[i])
      Else
        Permutation (aString, aResult + aString[i], anIndex + 1, aUsedChars + [aString[i]]);
End;

Function NthPermutation (const aString : AnsiString; aCount : Int64) : AnsiString;
Var
  pos, i, n : Cardinal;
  chTemp : char;
Begin
  n := Length(aString);
  result := aString;
  for i := n downto 2 do
    begin
    pos := acount mod i +1;
    //switch
    chTemp := result[i];
    result[i] := result[Pos];
    result[Pos] := chTemp;

    acount :=  acount div i;
    End;
End;


begin
 setlength(PermString,nmax);

 For i := 1 to nmax do
    PermString[i] := chr(i+ord('0'));

 n := nmax;
 j := 1;
 For i := 2 to n do
   j := i*j;
 writeln(PermString,j:10);
 readln;
try
 sl := TStringlist.create;
 sl.capacity:= j;

 t0 := time;
 Permutation (PermString, '' ,1 , []);
 t1:= time;

 WriteLn('ALZ',sl.count:8,FormatDateTime(' hh:mm:ss.zzz',T1-t0));

 sl.clear;
 sl.capacity:= j;

 t0 := time;
 repeat
   sl.add(nthpermutation(permstring,j));
   dec(j);
 until j=0;
 t1:= time;

 WriteLn('HOR',sl.count:8,FormatDateTime(' hh:mm:ss.zzz',T1-t0));

 sl.clear;
 sl.capacity:= j;

 For i := 1 to nmax do
    PermString[i] := chr(i+ord('0'));

 t0 := time;
 repeat
   sl.add(PermString);
 until NOT(Next(PermString));
 t1:= time;

 WriteLn('PermLex',sl.count:8,FormatDateTime(' hh:mm:ss.zzz',T1-t0));

{//Test, ob alles stimmig ist
 sl.sort;
 t1:= time;
 WriteLn(FormatDateTime(' hh:mm:ss.zzz',T1-t0));

 For i := 2 to sl.count do
   IF sl[i-2]= sl[i-1] then
     writeln(i);
 t1:= time;
 WriteLn(FormatDateTime(' hh:mm:ss.zzz',T1-t0));

 writeln(sl.count);

}

finally
 sl.free;
end;

 Readln;
end.


Eigentlich suchte ich eine Version (permlex.pas) , die direkt lexikografisch aufsteigend ist, wie die von alzaimar.
Aha, 2003 war das: www.webplain.de/fore...1,5610,5704#msg-5704 (Programmer: Joe Sawada, 1997. aber der Link ist weg).
Nun denn, ich habe es jetzt eingebaut und siehe da, die Zeiten sind etwa etwa 5(ALZ):3(HOR):1(PermLex), also erheblich schneller

Gruß Horst
EDIT:

Die Anzahl der Vertauschungen (bei alzaimar Anhängen) pro Durchgang ist bei mir immer n-1, bei permlex ca. 1,54 fast unabhänigig von n und das macht die Sache sehr schnell.Ich habe mal DIV und MOD eliminiert, falls man nextpermutation haben will. Aber das ist nur doppelt so schnell, als NthPermutation.
ausblenden volle Höhe Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
type
  TModZaehl = array[1..nmax] of integer;
..
var 
  ModZaehl : TModZaehl;
..
function NextPermutation(const aString: AnsiString; var ModZaehl: TModZaehl): AnsiString;
var
  pos, i, n: Cardinal;
  chTemp: char;

begin
  n := Length(aString);

  result := aString;

  for i := 1 to n-1 do
  begin
    pos := n-ModZaehl[i];

    //switch
//    Form1.memo1.lines.add(Format('~Tausche %2d mit %2d ',[i,pos]));

    chTemp := result[i];
    result[i] := result[Pos];
    result[Pos] := chTemp;
  end;

  i := n;
  pos := 1;
  inc(ModZaehl[pos]);
  while ModZaehl[pos] >= i do
  begin
    ModZaehl[pos] := 0;
    inc(pos);
    dec(i);
    if i < 2 then
      break;
    inc(ModZaehl[pos]);
  end;

end;
...
  t0 := time;
  for i := 1 to j do
    NextPermutation(PermString, ModZaehl);
  t1 := time;
..

Lange Rede, keinen Sinn: Permlex ist zeitlich konstant*O(n!) und nthPermutation ist ~konstant*O((n+1)!) in der Lauftzeit.
(nmax=10 -> permlex 0,221 Sekunden (ohne sl.add(..) sonst 1,61 Sekunden)


Was ich noch nicht gefunden habe ist eine nextpermutation, mit jeweils nur einer Tauschung.

www.codeplanet.eu/mo...storyid=7&page=0 oder
www.c-plusplus.de/fo...var-t-is-178286.html
Dort wundert mich das bei n=10 weniger als 10! permutationen berechnet werden???
Fiete
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Beiträge: 529
Erhaltene Danke: 232

W7
Delphi 6 pro
BeitragVerfasst: Fr 28.09.07 19:02 
user profile iconjuleins hat folgendes geschrieben:
hey.
ich möchte alle möglichen Kombinationen von 9-Stelligen Zahlen erzeugen, in denen jede Ziffer (1 bis 9) aber nur einmal vorkommt.

eine erste idee wäre sicher:

ausblenden Delphi-Quelltext
1:
2:
3:
for i := 123456789 to 987654321 do
   if (keine ziffer doppelt) then
       speichern



dies erscheint mir aber nicht sehr elegant und schnell, da sehr viele zahlen "umsonst" erzeugt werden. Ich bin mir sicher es gibt eine bessere Lösung, ich komme nur nicht drauf.

kann mir jmd helfen?
grüßle juleins

Moderiert von user profile iconTino: Code- durch Delphi-Tags ersetzt.
Einloggen, um Attachments anzusehen!
_________________
Fietes Gesetz: use your brain (THINK)
MantaBerti
Hält's aus hier
Beiträge: 1



BeitragVerfasst: Do 21.02.08 06:04 
user profile iconHorst_H hat folgendes geschrieben:

Was ich noch nicht gefunden habe ist eine nextpermutation, mit jeweils nur einer Tauschung.

www.codeplanet.eu/tu...0-permutationen.html
Dort wundert mich das bei n=10 weniger als 10! permutationen berechnet werden???


Dort werden nicht immer weniger als 10! Permutationen berechnet. Es gibt Permutationen mit und ohne Wiederholungen. Bei Permutation mit Wiederholung berechnet sich die Anzahl nicht nach n! sondern mit n! / k! * k! * kn!

Beispiel: aba

Je nach Algorithmus produziert das:

aab, aba, aba, aab, baa, baa

oder

aab, aba, baa

Dort werden verschiedene schnelle Algorithmen vorgestellt, die jeweils mit und ohne Wiederholungen rechnen, darunter ein sogenannter Countdown Algorithmus, der extrem performant arbeitet. Schneller geht es meines Wissens nicht mehr. Ich habe den C++ Algo dort in Delphi portiert. Funktioniert erste Sahne! :D

Gruß
Berti
Horst_H
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1643
Erhaltene Danke: 236

WIN10,PuppyLinux
FreePascal,Lazarus
BeitragVerfasst: Do 21.02.08 09:21 
Hallo,

dann beglücke uns doch mit deiner Umsetzung nach Delphi.
Dann man ja einen kleinen Test starten.

Gruß Horst
Delphi-Laie
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 1586
Erhaltene Danke: 231


Delphi 2 - RAD-Studio 10.1 Berlin
BeitragVerfasst: Mo 13.07.09 12:16 
Ist zwar schon zwei Jahre her, aber trotzdem:

user profile iconHorst_H hat folgendes geschrieben Zum zitierten Posting springen:
Was ich noch nicht gefunden habe ist eine nextpermutation, mit jeweils nur einer Tauschung.


Doch, gibt es, auch im Internet veröffentlicht (nach langer, hartnäckiger Suche gefunden), und zwar hier: medwelljournals.com/...jit/2007/956-957.pdf

Der dort beschriebene, (programmier-)sprachunabhängige Algorithmus ist zwar fürchterlicher "Spaghetticode", der eine iterative Optimierung durchaus verdient hat, aber er funktioniert und kommt tatsächlich nur mit einem Austausch (also jeweils zwei betroffene Elemente) zur Generierung einer (jeden) neuen Permutation aus. Er ist natürlich auch so optimiert, daß keine doppelten Permutationen erzeugt werden und zudem so "intelligent", daß er nach der Enumeration aller Permutationen von selbst endet (also keine Zählschleife für die Permutationsanzahl erforderlich ist). Hier eine erste (!) Delphi-Umsetzung, die sich noch voll an das Original anlehnt, mit der beispielhaften Elementeanzahl n=5:

ausblenden volle Höhe Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
const n=5;

label 2,4,6,8;

var a:string;
temp:char;
c,r,m:array[1..n] of integer;
i,k:byte;

begin
for i:=1 to n do
  begin
  c[i]:=0;
  r[i]:=1;
  m[i]:=n-i
  end;
a:='ABCDE';

2:i:=1;k:=1;

showmessage(a); //Hier der Abruf (beispielhaft die Ausgabe) der originalen und jeder permutierten Zeichenfolge zu weiteren "Verarbeitung"

4:if c[i]=m[i] then goto 6;
temp:=a[c[i]+k];
a[c[i]+k]:=a[c[i]+k+r[i]];
a[c[i]+k+r[i]]:=temp;
inc(c[i],r[i]);
goto 2;

6:if c[succ(i)]=m[succ(i)] then goto 8;
temp:=a[k];
a[k]:=a[succ(n-k)];
a[succ(n-k)]:=temp;
c[i]:=n-i-m[i];
inc(c[succ(i)],r[succ(i)]);
goto 2;

8:r[i]:=-r[i];
m[i]:=n-i-m[i];
r[succ(i)]:=-r[succ(i)];
m[succ(i)]:=pred(n-i-m[succ(i)]);
inc(i,2);
inc(k);
if i<n then goto 4


Auch werden in jenem Artikel andere, frühere, ebenfalls elementetauschbasierte Ansätze von Ives, Sedgewick und Roy erwähnt. Ob dieser Algorithmus wirklich der erste dieser Art ist, geht aus dem Artikel m.E. nicht eindeutig hervor. Ich verstehe es aber so, daß dieser neue Algorithmus zur Erzeugung jeder neuen Permutation nur eine Vertauschung (logischerweise (nur)) zweier Elemente benötigt und sich damit doch signifikant von den vorigen unterscheidet. Natürlich finden sich noch andere Beiträge im Internet, aber das ist zweifelsohne der schnellste und effektivste Ansatz. Auch in Donald E. Knuths Band 4 "Combinatorical algorithms" wird sich sicher etliches zu dieser Problematik bzw. Thematik finden.

Die bloßen Vertauschungen (anstatt daß jedesmal eine Ausgangsdatenmenge in eine Zieldatenmenge transformiert wird) bewirken auch einen minimalen Ressourcenbedarf hinsichtlich der zu "bewegenden" Daten und des Speicherbedarfes, analog den "in-place"-Sortieralgorithmen.

Weil die Enumeration auch in diesem Algorithmus nicht lexikographisch erfolgt und damit nicht bei der höchsten Permutation (also der mit der lexikographisch höchsten Nummer) endet, ist der als Thema plakativ genannte Wunsch "123456789 to 987654321" allerdings nicht erfüllbar, für die reine Enumeration aller Permutationen jedoch auch nicht nötig.

Edit: Der Verweis existert leider nicht mehr, deshalb hänge ich die entsprechende PDF-Datei hier an.

Edit 2: Die Datei ist nunmehr [url=docsdrive.com/pdfs/m...it/2007/956-957.pdf]hier[/url] verfügbar.
Einloggen, um Attachments anzusehen!


Zuletzt bearbeitet von Delphi-Laie am Sa 11.05.13 13:40, insgesamt 7-mal bearbeitet
BenBE
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 8720
Erhaltene Danke: 191

Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
BeitragVerfasst: Mo 13.07.09 13:27 
Die GOTOs tun ja weh! Wenn es wenigstens COMEFROMs wären!

ausblenden volle Höhe Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
procedure GetPermutations(A: String; Callback: TPermutationCallback);
var
    temp:char;
    c,r,m:array of integer;
    i,k,n:Integer;
    p:Boolean;
begin
    n := Length(A);

    //Succ because I'm too lazy for the index transformation in the rest of the source.
    SetLength(c,succ(n));
    SetLength(r,succ(n));
    SetLength(m,succ(n));

    for i:=1 to n do
    begin
        c[i]:=0;
        r[i]:=1;
        m[i]:=n-i
    end;

    p := True; //False if no interest in original, don't forget to init i and k to 1

    repeat
        if p Then
        begin
            Callback(a); //Hier der Abruf (an dieser Stelle die Ausgabe) der originalen und jeder permutierten Zeichenfolge

            i := 1;
            k := 1;

            p := false;
        end;

        if c[i] <> m[i] then
        Begin
            temp := a[c[i]+k];
            a[c[i]+k] := a[c[i]+k+r[i]];
            a[c[i]+k+r[i]] := temp;
            inc(c[i], r[i]);

            p = true;
            continue;
        end;

        if c[succ(i)] <> m[succ(i)] then
        begin
            temp := a[k];
            a[k] := a[succ(n-k)];
            a[succ(n-k)] := temp;
            c[i] := n-i-m[i];
            inc(c[succ(i)],r[succ(i)]);

            p = true;
            continue;
        end;

        r[i] := -r[i];
        m[i] := n-i-m[i];
        r[succ(i)] := -r[succ(i)];
        m[succ(i)] := pred(n-i-m[succ(i)]);
        inc(i, 2);
        inc(k);
    until not p and (i >= n);

end;


Auf den Rest der Kommentare verzichte ich, wie der Originalautor auch ;-)

_________________
Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

Für diesen Beitrag haben gedankt: Delphi-Laie