Autor Beitrag
Horst_H
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1654
Erhaltene Danke: 244

WIN10,PuppyLinux
FreePascal,Lazarus
BeitragVerfasst: Fr 14.10.05 13:35 
Hallo,

Es geht doch um 4..8 Zeichen aus A..Z und 0..9 also 26+10 =36 Zeichen
als Beispiel um alle Lottozahlen aufsteigend sortiert auszugeben.
ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
For Zahl1 :=1 to 49-5 do
  For Zahl2 := Zahl1+1 to 49-4 do
    For Zahl3 :=Zahl2+1 to 49-3 do
      For Zahl4 :=Zahl3+1 to 49-2 do
        For Zahl5 :=Zahl4+1 to 49-1 do
          For Zahl6 :=Zahl5+1 to 49-0 do
            begin
            Ausgabe von Zahl1 bis Zahl6
            end;

Die Abwandlung waere nun, 4 bis 8 aus 36 statt 6 aus 49, indem jede Zahl1..Zahln einem Index in dem Array of BenutzbarZeichen ist.
Anschliessend muessten noch alle Permutatationen jeder Ausgabezeile erstellt werden.
Also bei 6 aus 49 sind es 13.89 Mio ? {49 ueber 6} Kombinationen und jeweils 6! = 720 Permutationen also 13,89*720 = ganz ganz viel.

Also viel Spass mit dieser gigantischen Datei.

Gruss Horst
lesumsi
ontopic starontopic starofftopic starofftopic starofftopic starofftopic starofftopic starofftopic star
Beiträge: 54



BeitragVerfasst: Fr 14.10.05 14:05 
@Martin1966
Mein Ausprobieren erfoltge bis jetzt nur rein gedanklich. Ich find noch nichtmal richtig nen Prinzip zum Vorgehen!
Zudem sind meine Delphi Kenntnisse recht bescheiden, jedoch habe ich Erfahrungen in HTML/PHP und Pascal

@Lannes,
nicht ganz diese Richtung. Ich will ja alle alphanumerischen Kombinationen haben:
ausblenden Quelltext
1:
2:
3:
4:
5:
aaaa
aaab
aaac
...
99999999

Bei der Permutation hätte ich ja nur einige Zeichen vertauscht, so bekomme ich z.B. keine doppelten Zeichen.

Man könnte auch alles manuell machen, aber das wäre ne lange Arbeit 2901712999680 kombinationen Manuell zu machen ;)
ripper8472
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 114

Win2k (und wenn ich nen Zweitrechner haette, auch eine Linux Distri)

BeitragVerfasst: Fr 14.10.05 16:13 
2901712999680 variationen, wirklich?
dann liegst du mit der dateigroesse irgendwo um 26947,096 Gigabytes!
Horst_H
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1654
Erhaltene Danke: 244

WIN10,PuppyLinux
FreePascal,Lazarus
BeitragVerfasst: Fr 14.10.05 17:07 
Hallo,

ist mein Ansatz von Nutzen oder nicht?
Bei mir kommt aber jedes Zeichen nur einmal vor.
Falls jedes Zeichen beliebig vorkommen darf, wie im Beispiel aaaa, dann ist die Anzahl der Elemente der Loesungmenge k^n,
wobei k die Anzahl der moeglichen Zeichen ist , hier 36 und
n die Laenge der eryeugten Zeichenkette also 4 bis 8 hier.

Das geht mit n Schleifen von 1..k oder mit n mod,div Rechnungen, aber Divisionen sind teuer.

Gruss Horst
ripper8472
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 114

Win2k (und wenn ich nen Zweitrechner haette, auch eine Linux Distri)

BeitragVerfasst: Fr 14.10.05 17:10 
mit textdateien wuerd ich garnicht arbeiten. ich wuerde direkt die variationen (also aaaa, aaab, aaac, ...) im programm pruefen.
alzaimar
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 2889
Erhaltene Danke: 13

W2000, XP
D6E, BDS2006A, DevExpress
BeitragVerfasst: Fr 14.10.05 18:02 
Soweit ich das verstehe, handelt es sich um das klassische 0/1-Knapsack-Problem (Rucksack), und das ist NP-komplett. Will sagen, die optimale Möglichkeit ist die, alle Kombinationen durchzuprobieren (brute force). Am Besten geht das mit Backtracking.

Das Rucksackproblem beschreibt einen Dieb, der in seinem Rucksack Diebesgut wegschaffen will, und zwar mit maximalem Wert. Leider ist der arme Kerl etwas schwach auf der Brust, weswegen er nur ein bestimmtes maximales Gewicht tragen kann. Er hat z.B. 3 Goldbarren (je 10 kg, 20000 Euro), 4 Schmuckschatullen (5 kg, 7000 euro) und 5 Geldsäckel (je 2kg, 2000 Euro). Maximal kann der arme Kerl 21 kg schultern. Das Diebesgut darf nicht zerteilt werden (z.B. einfach ein paar Münzen aus dem Säckel) nehmen. Deshalb heisst es 0/1-Knapsack. Dürfte er das, hieße es n/m-Knapsack und wäre in linearer Zeit lösbar.

_________________
Na denn, dann. Bis dann, denn.
ripper8472
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 114

Win2k (und wenn ich nen Zweitrechner haette, auch eine Linux Distri)

BeitragVerfasst: Fr 14.10.05 18:49 
alzaimar, das urspruengliche problem ja.
allerdings hat auf der ersten zeite jemand ein neues thema angeschnitten, das eigentlich auf "raufzaehlen in stellenwertsystemen mit basis != 10" reduziert werden kann.
Lannes
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 2352
Erhaltene Danke: 4

Win XP, 95, 3.11, IE6
D3 Prof, D4 Standard, D2005 PE, TurboDelphi, Lazarus, D2010
BeitragVerfasst: Fr 14.10.05 20:12 
Hallo,

ein Edit, Memo und einen Button aufs Formular, dann :
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:
procedure TForm1.Button1Click(Sender: TObject);
var s:string;
    i:integer;
//****************************************
{}  procedure abc(step,k:integer);
{}  var s_bak:string;
{}      i:integer;
{}  begin
{}    if (step>k) then
{}      begin
{}      if step = Length(Edit1.Text)+1 then//Zeile 11 <----
{}        Memo1.Lines.Add(s);
{}      exit;
{}      end;
{}
{}    for i:=1 to length(edit1.Text) do
{}      begin
{}      s_bak:=s;
{}      s:=s+Edit1.Text[i];
{}      abc(step+1,k);//rekursiv
{}      s:=s_bak;
{}      end;
{}  end;
//****************************************
begin
  for i:=1 to Length(Edit1.text) do
    begin
    s:='';
    abc(1,i);
    end;
  showmessage(IntToStr(Memo1.Lines.Count));
end;

Der Code ergibt bei Eingabe von 'abc':
ausblenden Quelltext
1:
2:
3:
aaa aab aac aba abb abc aca acb acc
baa bab bac bba bbb bbc bca bcb bcc
caa cab cac cba cbb cbc cca ccb ccc
Es ergeben sich folgende Werte für
ausblenden Quelltext
1:
2:
3:
4:
5:
abc    =    27 Kombinationen
abcd   =   256    "
abcde  =  3125    "
abcdef = 46656    "
....
Kommentiert man die Zeile 11 aus, werden auch folgende Kombinationen hinzugefügt:
ausblenden Quelltext
1:
2:
3:
4:
5:
a b c
aa ab ac ba bb bc ca cb cc
aaa aab aac aba abb abc aca acb acc
baa bab bac bba bbb bbc bca bcb bcc
caa cab cac cba cbb cbc cca ccb ccc

_________________
MfG Lannes
(Nichts ist nicht Nichts) and ('' <> nil ) and (Pointer('') = nil ) and (@('') <> nil )
lesumsi
ontopic starontopic starofftopic starofftopic starofftopic starofftopic starofftopic starofftopic star
Beiträge: 54



BeitragVerfasst: Fr 14.10.05 21:21 
Das is gut, damit lässt sich sicher was anfangen!!!

Aber ich muss mal anmerken, dass ich es echt klasse finde, wie schnell, nett und gut hier geantwortet wird.
Kenn ich leider aus anderen Foren ganz anders...
ripper8472
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 114

Win2k (und wenn ich nen Zweitrechner haette, auch eine Linux Distri)

BeitragVerfasst: Sa 15.10.05 01:03 
das entscheidet sich an den ersten antworten. naturgesetz.
wird deine frage von jemandem fuer wuerdig befunden, dann tun das auch alle anderen.
Horst_H
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1654
Erhaltene Danke: 244

WIN10,PuppyLinux
FreePascal,Lazarus
BeitragVerfasst: Sa 15.10.05 11:40 
Hallo,

also sind es k^n Lösungen, die gefragt waren, bzw falls auch alle Losungen bis Zeichenanzahl von a..n (a grösser 0) gefragt sind.
Anzahl=Summe[i=a..n] k^i

Damit es nur n Zeichen werden habe ich N aus Edit2.text eingeführt.
Edit1.text = ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789
Edit2.text = 2
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:
implementation

{$R *.dfm}
var
  count : integer;

procedure TForm1.Button1Click(Sender: TObject);
var s:string;
    i,a,n,Faktor:integer;
//****************************************
{}  procedure abc(step,k:integer);
{}  var
{}    i:integer;
{}  begin
{}    if (step>k) then
{}      begin
{      If Count mod Faktor = 0 then}
{        Memo1.Lines[0]:=s;}
{}      Memo1.Lines.Add(s);
{}      inc(Count);
{}      exit;
{}      end;
{}    for i:=1 to length(edit1.Text) do
{}      begin
{}      s[step]:=Edit1.Text[i];
{}      abc(step+1,k);//rekursiv
{}      end;
{}  end;
//****************************************
begin
  memo1.Clear;
  n := StrToInt(Edit2.text);
  Faktor := 1;
  For i := 1 to n-1 do
    Faktor := Faktor*length(Edit1.Text);
 Count := 0;
 a := 1//aus 1 bis n
 //Jetzt die unterschiedlichen Lösungen der Länge i erzeugen
 For i := 1 to n do
   begin
   setlength(s,i);
   abc(1,i);
   end;
 showmessage(IntToStr(Count));
end;
end.

Dies hat 1332 Lösungen

Gruss Horst
alzaimar
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 2889
Erhaltene Danke: 13

W2000, XP
D6E, BDS2006A, DevExpress
BeitragVerfasst: Sa 15.10.05 14:18 
Hier eine Routine, die zu einer beliebigen 'Zahl' aNumber, bestehend aus Ziffern 'aDigits' eins dazuzählt.
AddOne ('a','abc',3) = 'b'
AddOne ('c','abc',3) = 'aa',
AddOne ('ccc','abc',3) = Overflow Exception

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:
Var
  s : String;

  Function AddOne (Const aNumber, aDigits : String; aMaxLen : Integer) : String;
  Var
    i,p : Integer;

  Begin
    i := Length (aNumber);       // Von hinten anfangen
    Result := aNumber;
    While i>0 do begin        
      p := Pos (Result[i], aDigits);    // Welches Zeichen?
      if p = Length (aDigits) Then Begin   // Überlauf ?
        Result [i] := aDigits[1];    // Ja, Ziffer i wieder auf '0'
        dec (i);        // und eine Stelle nach vorne
        End
      Else Begin
        Result [i] := aDigits[p+1];    // Kein überlauf, einfach nächtes Zeichen
        Exit;          // nehmen, das entspricht '+1'
        End;
      End;
    If Length (Result) = aMaxLen Then    // Max. Stellen erreicht?
      Raise EOverflow.Create('Overflow Error'); // Exception auslösen
    result := aDigits[1]+Result;    // Ansonsten einfach eine '1' vorne anstellen.
  End;

begin
  try
    s:=''
    repeat
      s := AddOne (s, edit1.text, StrToInt (edit2.text));
      me.lines.add (s);
    until false;
  Except
    End;
end;

Allerdings ist das nicht exakt eine 'Addition', aber die hier gestellte Aufgabe wird gelöst. Um korrekt in einem t-ären System zu addieren, ist folgende Modifikation nötig:
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:
Var
  s: String;

  Function AddOne(Const aNumber, aDigits: String; aMaxLen: Integer): String;
  Var
    i, p: Integer;

  Begin
    i := Length(aNumber);
    Result := aNumber;
    While i > 0 Do Begin
      p := Pos(Result[i], aDigits);
      If p = Length(aDigits) Then Begin // Overflow
        Result[i] := aDigits[1];
        dec(i);
      End
      Else Begin
        Result[i] := aDigits[p + 1];
        Exit;
      End;
    End;
    If Length(Result) = aMaxLen Then
      Raise EOverflow.Create('Overflow Error');
    result := aDigits[2] + Result;
  End;

Begin
  Try
    s := Copy(edit1.text, 11);
    While True Do Begin
      me.lines.add(s);
      s := AddOne(s, edit1.text, StrToInt(edit2.text));
    End;
  Except
  End;
End;

Dann ist AddOne ('0','01',2) = '1' und AddOne ('1','01',2) = '10' also mathematisch korrekt.

_________________
Na denn, dann. Bis dann, denn.
Harry M.
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 754

Win 2000, XP
D2005
BeitragVerfasst: Sa 15.10.05 14:37 
Wer suchet der findet: www.delphipraxis.net...ighlight=brute+force

www.delphipraxis.net...ighlight=brute+force

In gleicher / ähnlicher Sache stellt sich mir die Frage wie ich es korreckt berechnen kann wieviele Möglichkeiten sich ergeben können. Die Berechnung mit Power oder Exp geht fehl.
Hier der Code dafür
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:
function BruteForce(cNb: Cardinal; Const sCh: String): String;
begin
  Result := '';
  while cNb > Length(sCh) do begin
    dec(cNb);
    Result := sCh[cNb mod Length(sCh) + 1] + Result;
    cNb := cNb div Length(sCh);
    end;

  if cNb > 0 then
    Result := sCh[cNb] + Result;
end;

procedure TForm1.FormCreate(Sender: TObject);
const
  MinChars = $1// von 'a'
  MaxChars = $3// bis 'zzz'
  CharSet = 'abcdefghijklmnopqrstuvwxyz';
var
  AllKeys: Real;
  sGenPass: String;
  cLastNb: Cardinal;
begin
  Memo1.Clear;
  cLastNb := 1;
  sGenPass := CharSet[1]; // erstes zeichen definieren
  AllKeys := Exp(MaxChars*ln(Length(CharSet))); // berechnen aller permutationen

  while Length(sGenPass) < MinChars do begin   // jetzt bis zum ersten wort vorrücken
    Inc(cLastNb, 1);
    sGenPass := BruteForce(cLastNb, CharSet);
    end;

  // alle möglichkeiten erzeugen
  while (Length(sGenPass) >= MinChars) and (Length(sGenPass) <= MaxChars) do begin
    Memo1.Lines.Add(sGenPass);
    Inc(cLastNb, 1);
    sGenPass := BruteForce(cLastNb, CharSet);
    end;


  showmessage('Berechnete Keys: '+FloatToStr(AllKeys)+' / Tatsächliche Keys: '+IntToStr(Memo1.Lines.Count-1));
end;

_________________
Gruß Harry
Et spes me per dies sine te ducat et amor me ferat, si dolor spem tollit.
alzaimar
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 2889
Erhaltene Danke: 13

W2000, XP
D6E, BDS2006A, DevExpress
BeitragVerfasst: Sa 15.10.05 22:15 
Also: Wir stellen Zahlen dar, die Ziffern sind z.B. 'abcdefg', Nun wollen wir alle "Zahlen" mit maximal N Stellen darstellen. Wieviel gibt es denn nun? Sei X die Anzahl von Ziffern (hier: 6)
Es gibt also X 'Zahlen' mit einer Stelle.
Jeder dieser Zahlen kann ich eine Zahl vorne ran stellen. Macht für jede der X Zahlen X Möglichkeiten, also gibt es X*X Zahlen mit 2 Stellen.
...
Es gibt also X^N Zahlen mit genau N Stellen. Ergo gibt es X + X^2 + X^3 + ... X^N Möglichkeiten, um alle Zahlen zwischen 1 und N Stellen darzustellen.

_________________
Na denn, dann. Bis dann, denn.
Harry M.
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 754

Win 2000, XP
D2005
BeitragVerfasst: So 16.10.05 02:27 
Wahnsinns-Formel: Und wie siehst das in Delphi aus?

_________________
Gruß Harry
Et spes me per dies sine te ducat et amor me ferat, si dolor spem tollit.
alzaimar
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 2889
Erhaltene Danke: 13

W2000, XP
D6E, BDS2006A, DevExpress
BeitragVerfasst: So 16.10.05 10:02 
ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
Function AnzahlStellen (N, X : Integer) : Double;
Var
  i : Integer;

Begin
  Result := 1;
  For i:=1 to n do Result := Result + Power (x,i);
End;

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

WIN10,PuppyLinux
FreePascal,Lazarus
BeitragVerfasst: So 16.10.05 12:59 
Hallo,

Zitat:

Verfasst am: Sa 15.10.05 11:40

also sind es k^n Lösungen, die gefragt waren, bzw falls auch alle Losungen bis Zeichenanzahl von a..n (a grösser 0) gefragt sind.
Anzahl=Summe[i=a..n] k^i

Die Anzahl der Möglichkeiten mal ohne Power.
ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
Function AnzahlMoeglichkeiten(Zahllaenge, ZeichenAnzahl : Integer) : Double;   
Var   
  i : Integer;
  Potx : double;
Begin   
  Result := 0.0;   
  Potx := 1.0;
  For i:=1 to ZahlLaenge do 
    begin
    Result := Result + Potx;   
    Potx:= Potx*ZeichenAnzahl;
    end;
End;


Gruss Horst
Harry M.
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 754

Win 2000, XP
D2005
BeitragVerfasst: So 16.10.05 16:16 
Eine ähnliche Formel hatte ich ir heute früh auch zum Frühstück zurecht geleget. Leider bin ich noch nicht dazugekommen sie zuposten (Bin erst jetzt wieder ans Inet (bzw. nach Hause) gekommen. Sie sieht aber genauso so aus wie die von alzaimer. Hat halt etwas gedauert es zuverstehen.)

_________________
Gruß Harry
Et spes me per dies sine te ducat et amor me ferat, si dolor spem tollit.
Harry M.
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 754

Win 2000, XP
D2005
BeitragVerfasst: Mo 17.10.05 04:30 
So da bin ich wieder - will mich ja auch nicht lumpen lassen *g. Die obigen Formeln sind schon richtig. Fehl gehen auch diese wenn nicht bei 1 begonnen wird (etwa bei aaa - zzzzz) Ich habe das ganze mal in Form gebracht
ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
Function GetpermutationCount2(MinChars, MaxChars, CharLen: Integer) : Double;
Var
  i : Integer;
Begin
  Result := Power(CharLen, MinChars);

  while MinChars < MaxChars do begin
    Inc(MinChars, 1);
    Result := Result + Power(CharLen, MinChars);
    end;
End;

Danke nochmal für den logischen Denkanstoß.

_________________
Gruß Harry
Et spes me per dies sine te ducat et amor me ferat, si dolor spem tollit.