Entwickler-Ecke

Algorithmen, Optimierung und Assembler - Wie kriege ich alle Kombinationen ?!?


fafnir - Mo 31.01.05 17:32
Titel: Wie kriege ich alle Kombinationen ?!?
Hi,

ich habe eine bestimmte Anzahl von Zahlen(werten) (so etwa 80 Stück), und mit denen möchte ich alle Kombinationen ermitteln, bei denen die Summe einer beliebigen Anzahl von Summanden aus dieser Zahlenwerte-Menge eine gewisse Grenze nicht überschreitet. Es sollen ALLE Kombinationen dabeisein, die eine Summe unter der Grenze ergeben; es ist also egal, wie nah die Summe an der Grenze liegt, Hauptsache nicht darüber. Wie realisier ich das am besten ?
Danke im Voraus !

lg Matthias


Beispiel (für Dummies :wink: )

5 Zahlenwerte: 1,3,5,7,9
Grenze: 12
Möglichkeiten sind also: 1,3,5,7,9,1+3,1+5,1+7,1+9,3+5,3+7,3+9,5+7,1+3+5,1+3+7


Moderiert von user profile iconChristian S.: Topic aus Sonstiges verschoben am Mo 31.01.2005 um 17:33


IngoD7 - Mo 31.01.05 18:43
Titel: Re: Wie kriege ich alle Kombinationen ?!?
fafnir hat folgendes geschrieben:
Wie realisier ich das am besten ?

Indem du dir dein Posting nochmal durchliest, dabei feststellst, dass es so keiner verstehen kann, und deshalb dein Problem nochmal schilderst. 8)

//Nachtrag: Eingansposting wurde mittlerweile geändert. So finde ich es schick. :D


jasocul - Mo 31.01.05 18:48

Ich habe das Verstanden. Was ist daran nicht zu verstehen? :gruebel:
So langsam solltest du Übung haben Ingo :wink:

@fafnir:
Sollen nur zweier-Kombinationen zulässig sein oder alle ( z.B.: auch sowas: 20=10+5+4+1 ?)


ScorpionKing - Mo 31.01.05 18:48
Titel: Re: Wie kriege ich alle Kombinationen ?!?
IngoD7 hat folgendes geschrieben:
fafnir hat folgendes geschrieben:
Wie realisier ich das am besten ?

Indem du dir dein Posting nochmal durchliest, dabei feststellst, dass es so keiner verstehen kann, und deshalb dein Problem nochmal schilderst. 8)


die frage war eigentlich ganz ok erklärt, wenn doch meine antwort falsch ist, dann ist sie schlecht formuliert! :lol:

na ja, hier die antwort: du nimmst eine schleife und schreibst die daten in einen array.
also so:


Delphi-Quelltext
1:
2:
3:
for i := 0 to 100 do begin
  arrayxyz[i] := i;
end;


das ist zwar vollkommen sinnlos, da arrayxyz[1] das gleiche wie 1 ist, aber egal.

MfG, ScorpionKing!


Gausi - Mo 31.01.05 18:50

Ein ganz ähnliches Problem hatte ich auch mal. Was ich hier schreibe ist ungetestet, und möglicherweise nicht ganz korrekt. Von möglichen Syntax-Fehlern ganz abgesehen.


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:
// 1. Globales Zahlen-Array: Zahlen[i]
// 2. Globales Boolsches Array, genausolang wie Zahlen, initial alles false: gewählt[i]
// 3. Summe: integer, initial 0
// 4. Maximalwert: MaxWert
// Benötigt wird außerdem noch eine Ausgabe-Prozedur, die ein Ergbnis z.B. in eine Memo reinpackt

procedure SucheRekursiv(start:Integer; ende:Integer);
begin
  gewählt[i]:=TRUE;
  inc(summe,zahlen[start]); // Den Wert des aktuellen Elements draufaddieren
*************
//  Ausgabe-Prozedur muss hierhin. Alle Werte, wo gewählt auf True ist, geben eine 
// mögliche Kombination
// Abfrage (*) stellt sicher, dass der maximal-Wert hier nicht überschritten ist.
*************
  for i:=start+1 to ende do
    // Wenn man den nächsten Wert noch draufpacken kann, dann machen wir das auch
    // und suchen dort rekursiv weiter
    if (summe + zahlen[i]) < MaxWert then (*)
      SucheRekursiv(start+i);
  // Element wieder aus der Auswahl rausnehmen und Summe erniedrigen.
  dec(summe, zahlen[start]);
  gewählt[i] := FALSE;
end;

// Aufruf der in z.B. ButtonKlick:
for i:=0 to length(zahlen)-1 do
  if zahlen[i]<Maxwert then
     SucheRekursiv(i,length(zahlen)-1)

Im groben sollte das klappen.


F34r0fTh3D4rk - Mo 31.01.05 19:03

oder handelt es hierbei vielleicht um fakultät ?

es gibt viele kombinationsmöglichkeiten um die frage zu deuten


IngoD7 - Mo 31.01.05 19:08
Titel: Re: Wie kriege ich alle Kombinationen ?!?
An alle, die meinen, das verstanden zu haben, meine Bitte: Übersetzt es mir!

fafnir hat folgendes geschrieben:
ich habe eine bestimmte Anzahl von Zahlenwerten (so etwa 80),
Die Anzahl ist bekannt. Welche Werte sind das? 1-80? 0-79? 1-50 und 134-163? Na???

fafnir hat folgendes geschrieben:
und mit denen möchte ich alle Kombinationen bis zu einer bestimmten Grenze haben, bsw. bis die Summe 100 ist.
Summe 100 ist klar. Aber was ist sonst denn so mit "einer bestimmten Grenze" gemeint?

fafnir hat folgendes geschrieben:
Es sollen auch die Kombinationen dabeisein, die etwa nur 50 oder 20 oder 5, also alles von 1-100 dabeisein.
Bei allem Respekt: Das ist kein Satz! Den kann (oder muss) ich frei nach Schnauze ergänzen, um da irgendeinen Sinn rauszukitzeln.

Jede Lösung, die ihr hier jetzt hinbastelt, beruht auf stillschweigende Ergänzungen eurerseits. Mit anderen Worten Spekulationen und Vermutungen darüber, was gemeint sein könnte.

Und wer dann zufällig die richtige Antwort gibt, ist der Held. Bei den anderen passte die Frage nicht ... :lol:

Ich kann und will natürlich niemanden daran hindern, auf solche Problembeschreibungen zu antworten ....


Gausi - Mo 31.01.05 19:10

Mit Fakultät hat das nix zu tun. Aber sicherheitshalber sag ich mal, was mein Prog ermitteln sollte (und es hoffentlich auch macht):

Quelltext
1:
2:
3:
4:
5:
6:
z.B. Zahlenwerte 1,2,3,4,5,6, MaxWert=8
Ausgabe (allerdings nicht in dieser Reihenfolge)

1,2,3,4,5,6, (EinerKombos)
1+2, 1+3, 1+4, 1+5, 1+6, 2+3, 2+4, 2+5, 2+6, (ZweierKombos)
1+2+3,1+2+4,1+2+5 (DreierKombos)

Alle anderen Kombinationen ergeben in der Summe mehr als 8.


Edit: Übersetzung, extra für IngoD7, so wie ich es verstanden habe:

Gegeben: Eine Folge von Zahlen $a[1]$ bis $a[N]$
Gesucht: Alle Teilmengen $T \subset \{1,\ldots,N\}$, so dass $\sum_{i\in T} a[i] \le MaxWert$
Für die Kryptischen Zeichen: Siehe ein beliebiges LaTeX-Buch.


jasocul - Mo 31.01.05 19:25

Gleich bekomme ich wieder Ärger, weil es wieder zu viel OT ist.

@Ingo:
Drachen haben es nicht leicht beim Formulieren :wink:
Ich erklär Dir das jetzt mal:
Zitat:
ich habe eine bestimmte Anzahl von Zahlenwerten (so etwa 80)

Das ist doch eindeutig: 80 Zahlenwerte. Dort steht keine Einschränkung. Also beliebig.
Zitat:
alle Kombinationen bis zu einer bestimmten Grenze haben, bsw. bis die Summe 100 ist

bsw heißt beispielsweise. fafnir hat hier ein Beispiel für eine Grenze aufgeschrieben. Was gibt es hinein zu deuten?
Zitat:
Es sollen auch die Kombinationen dabeisein, die etwa nur 50 oder 20 oder 5, also alles von 1-100 dabeisein.

Da hat fafnir im Eifer doch tatsächlich zwei Worte vergessen:
Es sollen auch die Kombinationen dabeisein, die etwa nur 50 oder 20 oder 5 ergeben, also alles von 1-100 soll dabeisein.

Was war daran jetzt so schwer :gruebel:


Gausi - Mo 31.01.05 19:32

...sag ich doch. Und jetzt zurück zum Thema. Am besten warten, bis sich fafnir dazu äußert. Alles weitere hat jetzt erstmal keinen Sinn und führt zu Ärger. :mahn:


F34r0fTh3D4rk - Mo 31.01.05 19:41

hat das was mit deinem schaltplan topic zu tun ?


fafnir - Di 01.02.05 23:27

Habe meine Problemschilderung etwas optimiert, allerdings fand' ich es nicht sooo schwer zu verstehen (gut, der eine Satz gab wirklich nicht so viel Sinn; bemühe mich aber stets um Rechtschreibung, Grammatik und Syntax ! :? )

Sind schon gute Lösungsansätze dabei, muss mich mal morgen näher damit beschäftigen, ob das gesuchte dabei ist...

@F34r0fTh3D4rk: Ja, hat es.


IngoD7 - Mi 02.02.05 02:26

fafnir hat folgendes geschrieben:
Habe meine Problemschilderung etwas optimiert,
Etwas?!? So ist sie super!

fafnir hat folgendes geschrieben:
allerdings fand' ich es nicht sooo schwer zu verstehen (gut, der eine Satz gab wirklich nicht so viel Sinn; bemühe mich aber stets um Rechtschreibung, Grammatik und Syntax ! :? )
*grumpf* Einigen wir uns darauf, dass sie nicht für jedermann zu verstehen war ...

fafnir hat folgendes geschrieben:
Beispiel (für Dummies :wink: )
Sei froh, dass der Smiley dahinter steht.

fafnir hat folgendes geschrieben:
Sind schon gute Lösungsansätze dabei, muss mich mal morgen näher damit beschäftigen, ob das gesuchte dabei ist...
Gausi's Routine dürfte es sein, wenn sie das macht, was er in seinem zweiten Posting erklärt.

Gruß
Ingo
(Kämpfer gegen sinnfreie Problembeschreibungen) :wink:


fafnir - Di 08.02.05 16:15

Hi !

Also so sieht mein aktueller Sourcecode aus:


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:
...
 
procedure TForm1.BerechnenClick(Sender: TObject);  
var i:integer;  
begin  
for i:=1 to 78 do  
  Kombinationen(i,78); // Es gibt keine Zahl grösser als die Grenze, deshalb fällt hier der Check weg
end;  

 
procedure TForm1.Kombinationen(start:integer; ende:integer);  
var i:integer;  
begin  
  swahrheit[start]:=true;  
  inc(geslaenge,slaenge[start]);  
  Ausgabe; // Aufruf der Ausgabe-Prozedur  
  for i:=start+i to ende do // aktuelles Problem  
    if (geslaenge+slaenge[i])<grenze then  
      Kombinationen(start+i,78
    else  
    begin  
      dec(geslaenge,slaenge[start]);  
      swahrheit[i]:=false;  
    end;  
end;  

 
procedure TForm1.Ausgabe; // schreibt alle Ergebnisse in ein StringGrid  
var i,x:integer;  
begin  
x:=0;  
y:=y+1;  
StringGrid1.RowCount:=y;  
StringGrid1.Cells[0,y-1]:=inttostr(y);  
  for i:=1 to 78 do  
    if swahrheit[i]=true then  
    begin  
      x:=x+1;  
      StringGrid1.Cells[x,y-1]:=inttostr(i);  
    end;  
end;  

...


Mein aktuelles Problem: i scheint nicht definiert zu sein (habs markiert). i soll im ersten Durchlauf doch start+1 sein, oder ? Nur wo setze ich i das erste Mal gleich 1 ?

In der Prozedur kann ich das ja nicht, da die eigentlich eine Schleife ist (i würde bei jedem Durchlauf wieder auf 1 gesetzt werden).

Hoffe, es ist verständlich, was ich meine... Im Moment funzt das Programm noch nicht so recht, es gibt nur 78 Kombinationen... *G*

lg Matthias


Gausi - Di 08.02.05 17:21

Da waren in meinem Code von eben doch n paar Fehlerchen drin. Probiers mal so:

Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
procedure TForm1.Kombinationen(start:integer; ende:integer);     
var i:integer;     
begin     
  swahrheit[start]:=true;     
  inc(geslaenge,slaenge[start]);     
  Ausgabe; // Aufruf der Ausgabe-Prozedur     
  for i:=start+1 to ende do 
    if (geslaenge+slaenge[i])<grenze then     
      Kombinationen(i,78)    
//    else     
//    begin     
// das machen, wenn die Schleife beendet ist
      dec(geslaenge,slaenge[start]);     
      swahrheit[start]:=false;     
//    end;     
end;

Edit: Zu schnell auf Absenden geklickt... :wink:


ripper8472 - Mi 09.02.05 02:11

als ich den Eingangspost gelesen habe, kam mir sofort mein Programm in den Sinn.
Ist zwar C++ Code und so geschrieben, wie es mir in den Sinn kam, sollte aber doch etwas bringen. Und bitte nicht hauen wegen der Speicher- und Pointerexzesse. Ich bin ein sehr gewissenhafter Mensch und kann das.
Es findet die Kombinationen, die eine möglichst große Summe bilden, den Grenzwert aber nicht überschreiten.

http://www.cppforum.de/forum/topic,48,-cds-randvoll-brennen.html


lesumsi - Fr 14.10.05 11:11

Guten Tag,

ich möchte gerne mal an die Anfangsfrage anknüpfen und wissen, wie ich Folgendes realisieren kann:
Ich brauch ein Programm, welches mir alle Kombinationsmöglichkeiten aus allen Buchstaben und Zahlen
mit 4-8 Zeichen in einer Textdatei ausgibt.
Ich bin schon die ganze Zeit am ausprobieren komme aber zu keinem wirklichen Ergebnis.
Ich bedanke mich schonmal im Vorraus, sollten noch Fragen bezüglich meiner Frage sein, stellt sie ruhig.


MfG,
Marc


ripper8472 - Fr 14.10.05 11:29


Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
#include <stdio.h>

int main()
{
  char mynum[10] = {0};
  int i = 0, j, base = 26;
  while (i < 100) // erste 100 variationen
  {
    for(j=0; j<10; ++j)
      printf("%c", 'A'+mynum[j]);
    puts("\n");
    for(j=9;j;)
    {
      mynum[j] = (mynum[j]+1)%base;
      if (mynum[j--]) break;
    }
    ++i;
  }
  return 0;
}

viel spass beim portieren auf delphi


Martin1966 - Fr 14.10.05 11:29

user profile iconlesumsi hat folgendes geschrieben:
Ich bin schon die ganze Zeit am ausprobieren komme aber zu keinem wirklichen Ergebnis.

Zeig doch mal was du schon hast. Dann können wir darauf aufbauen.

Lg Martin


Lannes - Fr 14.10.05 12:14

Hallo,

geht das in die richtige Richtung :gruebel:
http://delphi.zsg-rottenburg.de/delphi.html#permutationen


Horst_H - Fr 14.10.05 12: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.

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 - Fr 14.10.05 13: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:

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 - Fr 14.10.05 15:13

2901712999680 variationen, wirklich?
dann liegst du mit der dateigroesse irgendwo um 26947,096 Gigabytes!


Horst_H - Fr 14.10.05 16: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 - Fr 14.10.05 16:10

mit textdateien wuerd ich garnicht arbeiten. ich wuerde direkt die variationen (also aaaa, aaab, aaac, ...) im programm pruefen.


alzaimar - Fr 14.10.05 17: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.


ripper8472 - Fr 14.10.05 17: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 - Fr 14.10.05 19:12

Hallo,

ein Edit, Memo und einen Button aufs Formular, dann :

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':

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

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:

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


lesumsi - Fr 14.10.05 20: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 - Sa 15.10.05 00: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 - Sa 15.10.05 10: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

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 - Sa 15.10.05 13: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


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:

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.


Harry M. - Sa 15.10.05 13:37

Wer suchet der findet: http://www.delphipraxis.net/topic62161_tbruteforce+version+013+rc+2.html&highlight=brute+force

http://www.delphipraxis.net/topic16760_brute+force+algorithmus.html&highlight=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

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;


alzaimar - Sa 15.10.05 21: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.


Harry M. - So 16.10.05 01:27

Wahnsinns-Formel: Und wie siehst das in Delphi aus?


alzaimar - So 16.10.05 09:02


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;


Horst_H - So 16.10.05 11: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.

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. - So 16.10.05 15: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.)


Harry M. - Mo 17.10.05 03: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

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ß.