Autor Beitrag
fafnir
Hält's aus hier
Beiträge: 6



BeitragVerfasst: Mo 31.01.05 18:32 
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


Zuletzt bearbeitet von fafnir am Mi 02.02.05 00:27, insgesamt 2-mal bearbeitet
IngoD7
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 629


D7
BeitragVerfasst: Mo 31.01.05 19:43 
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


Zuletzt bearbeitet von IngoD7 am Mi 02.02.05 03:28, insgesamt 1-mal bearbeitet
jasocul
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 6393
Erhaltene Danke: 147

Windows 7 + Windows 10
Sydney Prof + CE
BeitragVerfasst: Mo 31.01.05 19: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
ontopic starontopic starontopic starontopic starhalf ontopic starofftopic starofftopic starofftopic star
Beiträge: 1150

Win XP

BeitragVerfasst: Mo 31.01.05 19:48 
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:

ausblenden 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!

_________________
Aus dem Urlaub zurück!
Gausi
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 8548
Erhaltene Danke: 477

Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
BeitragVerfasst: Mo 31.01.05 19: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.

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

_________________
We are, we were and will not be.
F34r0fTh3D4rk
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 5284
Erhaltene Danke: 27

Win Vista (32), Win 7 (64)
Eclipse, SciTE, Lazarus
BeitragVerfasst: Mo 31.01.05 20:03 
oder handelt es hierbei vielleicht um fakultät ?

es gibt viele kombinationsmöglichkeiten um die frage zu deuten
IngoD7
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 629


D7
BeitragVerfasst: Mo 31.01.05 20:08 
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 ....


Zuletzt bearbeitet von IngoD7 am Mo 31.01.05 20:11, insgesamt 1-mal bearbeitet
Gausi
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 8548
Erhaltene Danke: 477

Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
BeitragVerfasst: Mo 31.01.05 20:10 
Mit Fakultät hat das nix zu tun. Aber sicherheitshalber sag ich mal, was mein Prog ermitteln sollte (und es hoffentlich auch macht):
ausblenden 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.

_________________
We are, we were and will not be.
jasocul
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 6393
Erhaltene Danke: 147

Windows 7 + Windows 10
Sydney Prof + CE
BeitragVerfasst: Mo 31.01.05 20: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
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 8548
Erhaltene Danke: 477

Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
BeitragVerfasst: Mo 31.01.05 20: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:

_________________
We are, we were and will not be.
F34r0fTh3D4rk
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 5284
Erhaltene Danke: 27

Win Vista (32), Win 7 (64)
Eclipse, SciTE, Lazarus
BeitragVerfasst: Mo 31.01.05 20:41 
hat das was mit deinem schaltplan topic zu tun ?
fafnir Threadstarter
Hält's aus hier
Beiträge: 6



BeitragVerfasst: Mi 02.02.05 00: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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 629


D7
BeitragVerfasst: Mi 02.02.05 03: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 Threadstarter
Hält's aus hier
Beiträge: 6



BeitragVerfasst: Di 08.02.05 17:15 
Hi !

Also so sieht mein aktueller Sourcecode aus:

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


Zuletzt bearbeitet von fafnir am Di 08.02.05 21:13, insgesamt 1-mal bearbeitet
Gausi
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 8548
Erhaltene Danke: 477

Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
BeitragVerfasst: Di 08.02.05 18:21 
Da waren in meinem Code von eben doch n paar Fehlerchen drin. Probiers mal so:
ausblenden 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:

_________________
We are, we were and will not be.
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: Mi 09.02.05 03: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.

www.cppforum.de/foru...andvoll-brennen.html
lesumsi
ontopic starontopic starofftopic starofftopic starofftopic starofftopic starofftopic starofftopic star
Beiträge: 54



BeitragVerfasst: Fr 14.10.05 12: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
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 12:29 
ausblenden 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 1068

Win 2000, Win XP
Delphi 7, Delphi 2005
BeitragVerfasst: Fr 14.10.05 12: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
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 13:14 
Hallo,

geht das in die richtige Richtung :gruebel:
delphi.zsg-rottenbur...i.html#permutationen

_________________
MfG Lannes
(Nichts ist nicht Nichts) and ('' <> nil ) and (Pointer('') = nil ) and (@('') <> nil )