Interessante (?) Frage Kombinatorik

[Möbius]

Liebe Alle

Ich bin da auf ein Problem gestossen an dem ich mir die Zähne ausbeisse.
Angenommen ein Zahlenraum n.
n ist dann auch das grösste vorkommende Zeichen.
Die grösse der resultierenden Datei(en) sei n.

Also ist n=4 dann ist das Zielarray (x,x,x,x) gross.

Gesucht sind nun alle Zieldateien deren Quersumme n entspricht.
Also etwas
(4,0,0,0)
(0,4,0,0)
...
(3,1,0,0)
(3,0,1,0)
etc.

Also mit anderen Worten auch die Lösung für alle möglichen Dateien eine Summe n zu bilden mit Anzahl Summanden = n (einschliesslich der 0).

Kennt jemand hierfür einen Algorhitmus oder eine Lösung?
Wie liesse sich das effizient machen.

Vielen Dank und Grüsse
Reto

[blawen]

Etwa so etwas in dieser Art?
Sicher nicht perfekt, aber von der "Grundidee" her, sollte es passen.

Delphi-Quellcode:

procedure TForm7.Button1Click(Sender: TObject);
var
  n: Integer;
  current: array[0..3] of Integer;
begin
  n := 4; // Beispielwert

  Memo1.Clear;
  Memo1.Lines.Add('Alle Lösungen mit einer Quersumme von ' + IntToStr(n) + ':');
  FindeKombinationen(n, Length(current), 0, current);
end;

procedure TForm7.FindeKombinationen(n, k: Integer; idx: Integer; var current: array of Integer);
var
  i: Integer;
  Ausgabe: string;
begin
  if (idx = k) then
  begin
    // Wenn das Array vollständig ausgefüllt ist, prüfe die Summe
    if (current[0] + current[1] + current[2] + current[3] = n) then
    begin
      // Ausgabe in Memo
      Ausgabe := '(';
      for i := 0 to k - 1 do
      begin
        Ausgabe := Ausgabe + IntToStr(current[i]);
        if i < k - 1 then
          Ausgabe := Ausgabe + ', ';
      end;
      Ausgabe := Ausgabe + ')';
      Memo1.Lines.Add(Ausgabe);
    end;
    Exit;
  end;

  for i := 0 to n do
  begin
    current[idx] := i;
    FindeKombinationen(n, k, idx + 1, current);
  end;

[Möbius]

Lieber Roland

Ja genausowas in der Art.
So schlau war ich auch schon. Aber der Algorhitmus bildet alle Permutationen und prüft auf Quersumme 4.
Das ist leider sehr ineffizient.
Mich interessiert das ganze konkret für N = 256.
Und eben effizient...

Danke und GrRuss
Reto (Möbius)

[Olli73]

Hier ist eine Antwort, die ich mit Microsoft Copilot erhalten habe, der weltweit ersten KI-gestützten Antwort-Engine. Wählen Sie diese Option aus, um die vollständige Antwort anzuzeigen, oder probieren Sie sie selbst aus. https://sl.bing.net/AyhcbH3X52

[Olli73]

Oder allgemein:

Hier ist eine Antwort, die ich mit Microsoft Copilot erhalten habe, der weltweit ersten KI-gestützten Antwort-Engine. Wählen Sie diese Option aus, um die vollständige Antwort anzuzeigen, oder probieren Sie sie selbst aus. https://sl.bing.net/b9T8uMC15Ge

[blawen]

Verstehe ich es richtig, dass der Zahlenraum im gewünschten Fall 256^256 gross sein soll (n=256)?
Bei einem so grossen Bereich fehlt mir im Moment der Ansatz.

[Michael II]

Das ist ein typischer "Ziehen ohne Zurücklegen" Fall. n Kugeln, d Kugeln ziehen. n tief d Fälle.

Nimm zum Beispiel n=5 nummerierte Kugeln und ziehe aus diesen 2 Kugeln.

Alle Möglichkeiten aus 5 Kugeln 2 auszuwählen (insgesamt 5 tief 2 = 10 Fälle). Die gezogenen Kugeln markieren wir in der Liste mit X:

XX345
X2X45
X23X5
X234X
1XX45
1X3X5
1X34X
12XX5
12X4X
123XX

Die zwei X unterteilen jede gefundene Lösung in 3 Teile.
Wir können die Anzahl der Kugeln pro Teil zählen und in einen Vektor schreiben:

XX345 (0,0,3)
X2X45 (0,1,2)
X23X5 (0,2,1)
X234X (0,3,0)
1XX45 (1,0,2)
1X3X5 (1,1,1)
1X34X (1,2,0)
12XX5 (2,0,1)
12X4X (2,1,0)
123XX (3,0,0)

Die Ziehung 1X34X erzeugt den Vektor (1,2,0): Wir haben in dieser Ziehung die zwei Kugeln 2 und 5 gezogen (durch X markiert). Links von Kugel 2 liegt 1 Kugel (nämlich Kugel 1) [d.h. für unseren Vektor (1,.,.)], links von Kugel 5 liegen die 2 Kugeln 34 [d.h. (.,2,.)] und rechts von Kugel 5 liegt keine Kugel [(.,.,0)].


Wir haben mit diesem Beispiel den Fall "Wir wollen Vektoren mit 3 Elementen, die Summe der Vektorelemente soll 3 ergeben" gelöst.

Allgemein:

Du benötigst einen Vektor (x1,x2,x3,x4....xv) bestehend aus v Elementen.
Die Summe der v Vektorelemente xi soll s ergeben.

Wir wissen anhand des Beispiels oben: Wenn wir v-1 Kugeln ziehen, dann können wir wie oben beschrieben aus jeder Ziehung v Vektorelemente erzeugen.
Insgesamt sollten nach dem Ziehen der v-1 Kugeln noch s Kugeln im Topf liegen.

Wir müssen also den Fall "Aus n=v-1+s Kugeln ohne Zurücklegen d=v-1 Kugeln ziehen" berechnen.

Dies kannst du
- rekursiv lösen oder
- iterativ indem du alle möglichen Fälle durchnummerierst und aus jeder Nummer einen Vektor erzeugst.

[Olli73]

Aus welcher Aussage entnimmst du, dass es ohne zurücklegen ist?

[Michael II]

Lösung via Rekursion.
In s gibst du die gewünschte Summe an, in v die Anzahl der gewünschten Vektorelemente.

Wie erwähnt: Es geht auch iterativ, indem du von 1..n tief d zählst und aus jeder Nummer einen Vektor erzeugst.

Delphi-Quellcode:

procedure ZoZ(n, d: Integer; var A: array of Integer; i, m: Integer; var res : TStringList );
var
  j: Integer;
  hs, s : string;
begin
  A[i] := m;
  if i = d then
  begin
    s := '';
    for j := 1 to n-d do
      s := s + IntToStr(A[j]-A[j-1]-1) + ' ';
    res.Add(s);
  end
  else
  for j := m + 1 to n do ZoZ(n, d, A, i + 1, j,res);
end;

procedure TForm131.Button1Click(Sender: TObject);
var A : array of integer;
    s, v, n, d : integer;
    res : TStringList;
begin
   s := 4;  // Die Summe der Vektorelemente soll s ergeben.
   v := 4;  // Der Vektor soll v Elemente enthalten.

   d := v-1;
   n := s+d;

   setlength(A,d+2);
   A[0] := 0;
   A[d+1] := n+1;
   res := TStringList.Create;
   ZoZ( n, d, A, 0, 0, res );
   ShowMessage( res.Text );
   res.Free;
end;

[Michael II]

Zitat:

Zitat von Olli73 (Beitrag 1540196)

Aus welcher Aussage entnimmst du, dass es ohne zurücklegen ist?

Er will Vektoren von einer gewissen Länge v generieren und die Vektorelemente sollten aufsummiert s ergeben. Das löst man durch "Ziehen ohne Zurücklegen" - siehe mein Beispiel weiter oben.

[Olli73]

Er hätte schreiben sollen, ob z.B. (2, 2, 0, 0) zulässig ist oder nicht.

[Uwe Raabe]

Ich hätte da einen iterativen Ansatz ohne Rekursion zu bieten:

Delphi-Quellcode:

procedure Kombinatorik(N: Integer; HandleArray: TProc<TArray<Integer>>);
var
  arr: TArray<Integer>;
begin
  SetLength(arr, N);
  { Triviale Startkombination }
  arr[0] := N;
  HandleArray(arr);
  var idx := 0;
  repeat
    if idx < High(arr) then begin
      { Schiebe einen Zähler um eine Stelle nach rechts }
      Dec(arr[idx]);
      Inc(idx);
      Inc(arr[idx]);
      HandleArray(arr);
    end
    else begin
      { Letzte Stelle: Merke und lösche den Übertrag }
      var K := arr[idx];
      arr[idx] := 0;
      { Suche den den größten Index mit einem Wert > 0. 
        Gibt es keinen sind wir fertig.}
      repeat
        Dec(idx);
        if idx < 0 then
          Exit;
      until arr[idx] > 0;
      { Setze den Übertrag in die nächste Stelle (muss 0 enthalten) }
      arr[idx + 1] := k;
      { Im weiteren Verlauf wird wieder ein Zähler von idx auf den Übertragswert geschoben }
    end;
  until False;
end;

Das Ergebnis sieht dann so aus:

Code:

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

[Michael II]

Ich bau solche Ziehungen auch fast nur iterativ auf, v.a. um Aufrufe zu verhindern.

Hier noch ein rekursiver direkter Ansatz (also ohne die "Ziehen ohne Zurücklegen" Überlegung).
[Damit man bei solchen Aufgaben das Rad nicht immer neu erfinden muss, lohnt es sich ein paar kombinatorische Aufgaben wie "Ziehen mit/ohne Zurücklegen", Permutationen etc. zu programmieren. Durch geschickte Parameterwahl kann man dank einer solchen Sammlung die meisten Probleme mit einer Zeile Code lösen.]

Delphi-Quellcode:

procedure af( rest : integer; var A: array of Integer; elnr : integer; var res : TStringList );
var i, j : integer;
    s : string;
begin
  if elnr = High(A) then // letzte Position in A erreicht
  begin
      s := '';
      A[elnr] := rest; // wir schreiben den Rest der Summe
      // und speichern A in res ab:
      for j := 0 to High(A) do s := s + A[j].ToString + ' ';
      res.Add(s);
  end else
  for i := 0 to rest do
  begin
    // an Postion elnr sind noch die Werte 0..rest möglich
    A[elnr] := i; 
    // danach können wir noch rest-i auf die Elemente A[elnr+1] .. A[High(A)] verteilen:
    af(rest-i, A, elnr+1, res);
  end;
end;

....
 res := TStringList.Create;
 Setlength(A,v);
 af(s,A,0,res);
 ShowMessage( res.Text );
 res.free;

[Kas Ob.]

Zitat:

Zitat von Möbius (Beitrag 1540187)

Lieber Roland

Ja genausowas in der Art.
So schlau war ich auch schon. Aber der Algorhitmus bildet alle Permutationen und prüft auf Quersumme 4.
Das ist leider sehr ineffizient.
Mich interessiert das ganze konkret für N = 256.
Und eben effizient...

Danke und GrRuss
Reto (Möbius)

Hmmmmm..... :gruebel: ...... hmmmmmmmmmm again :gruebel:
Are you trying to attack AES (or something similar in size) at 256Bit ?!!

You already explained in later post what are you trying to do, but... at 256bit it is near impossible to any consumer PC to do this and, simply put it is too much !

To explain on this, no matter how you do it with integers and their arrays, it will be inefficient because it will grow exponentially, this matrix will be very huge no matter what type of integers you are handling ( byte, word, integer...)
So the cheapest and fastest way is to switch to minimum element, and use bits, where there indexes will represent their value, example , lets represent your example with 5 balls

Code:

balls Vector     as bits
XX345 (0,0,3)    00111
X2X45 (0,1,2)    01011
X23X5 (0,2,1)    01101
X234X (0,3,0)    01110
1XX45 (1,0,2)    10011
1X3X5 (1,1,1)    10101
1X34X (1,2,0)    10110
12XX5 (2,0,1)    11001
12X4X (2,1,0)    11010
123XX (3,0,0)    11100

What do we see here:
1) With bits, we instead of building all the permutations, we simply can use an integer value going from 0 to 2^5 (where 5 bits is needed).
2) simple loop with an integer (5 bits integer , it could be a byte or an integer) will let us skip the permutation building in full.
3) In the above example notice that 3 is the sum of all 1 bits !, and there is specific assembly instruction on modern CPUs that can return this sum POPCNT https://www.felixcloutier.com/x86/popcnt
4) I might be mistaken though about what are you really need, is it the separation of the bits by some count ?, like 3 small vectors, in your example only one is there "1X3X5 (1,1,1) 10101" this will complicate the thing but still way easier than handling integers and matrices.

In any case my suggestion is simply to use increased integer (or Int64) or even some BigInt, this at least will save you speed and space.

Auxiliary assembly instructions that might help here:
LZCNT https://www.felixcloutier.com/x86/lzcnt
TZCNT https://www.felixcloutier.com/x86/tzcnt
and of course there is SIMD version for only two them, there is no trailing zero counting SIMD instruction
https://www.felixcloutier.com/x86/vpopcnt
https://www.felixcloutier.com/x86/vplzcntd:vplzcntq

Anyway, this still strongly smell like deferential cryptoanalysis, i remember read many of very close proposed statistically approaches/attacks, yet none of these papers had an implemented algorithm in computer compliable language, it is always mathematical theories and formulas, so will not waste time searching for them.

This approach by generating the permutation by simply increase an integer, is .. well ... firstly i like it.. secondly it will be very fast, i don't think there is faster than this, yet increasing an integer to large values above 32bit (we are here about only 32 balls) it is a big deal but doable on our consumer PCs, for 64bit it will be way slower, going up from there is border sanity to run and wait, so you might divide you problem into smaller and repeatable periodic parts, this might help, but too long for me to go on about it here for more than few lines, and yes i need to wrap my head around it first,... if only the bit counts is needed then, each 5 bits result will be repeated, like directly deduce the result of concatenation the result of two 5bits into one 10bit, or slicing the 10bits into two 5bits, of course if you need larger numbers then use numbers makes sense something is equal to 2^k, like 8 bit or 4 bit, now these 8bit or 4bit can also in a higher layer represented as bits, hence 32bit will be come 4bit representing a matrix of 8bit, the usage for the this higher layer, will be used for elimination only, but again i am suggesting elimination here because it is first what comes to my mind at this moment... this might need more than scratching head and beard.

I wrote too much and hope this still clear, if your needed algorithm only needed the count then it is simple assembly instruction (or few for longer), but if you need the smaller vectors, then it will be harder but doable, by divide and conquer.
About count the bits, i can't find my Hackers Delights book, i didn't see it for few years now, so might lost it or lend it to someone and forgot, but may someone here or even you might it, and there is nice algorithms as i remembers you can use without using assembly, slower though, and some of them might be very slow do the stupidity of Delphi compiler.

Hope i didn't mess the subject by more than few kilometers, and hope it help you with ideas.

And of course good luck.

[Kas Ob.]

Another though on this:

Delphi Sets can be used as set can handle up to 256 element ([0..255]), each value will be a bit by its index, but it will be ugly with too much casting for my liking, it is the only way to do with runtime.

[Möbius]

Vielen Dank Michael

Dein Coding funktioniert.
Er rechnet jetzt schon Stunden und gibt lauter richtige Resultate raus.

Im Prinzip interessiert mich vorerst mal eine Abschätzung der Lösung für n=255.
Aber eben da geht probieren über studieren. Mit Fakultät 256 kommt kein Rechner klar.

Jedenfals, Dein Ansatz funktioniert.
Lieder macht er aber sehr viele Iterationen bis es wieder zu einer Ausgabe kommt....

[shebang]

Zitat:

Zitat von Möbius (Beitrag 1540245)

Mit Fakultät 256 kommt kein Rechner klar.

Weil da eine Zahl mit über 500 Stellen herauskommt. Schau dir dazu am besten mal die Stirling Formel an.

[Michael II]

Zitat:

Zitat von Möbius (Beitrag 1540245)

Vielen Dank Michael

Dein Coding funktioniert.
Er rechnet jetzt schon Stunden und gibt lauter richtige Resultate raus.

Im Prinzip interessiert mich vorerst mal eine Abschätzung der Lösung für n=255.
Aber eben da geht probieren über studieren. Mit Fakultät 256 kommt kein Rechner klar.

Jedenfals, Dein Ansatz funktioniert.
Lieder macht er aber sehr viele Iterationen bis es wieder zu einer Ausgabe kommt....

Hallo Möbius,

Danke für dein Feedback. Punkto Anzahl Lösungen: Wie erwähnt, kann dein Problem auf "Ziehen ohne Zurücklegen (d Kugeln (oder was auch immer) aus insgesamt n ziehen ohne gezogene zurückzulegen)" zurückgeführt werden. Und da kennen wir die Anzahl Möglichkeiten (n tief d) = n!/(d!*(n-d)!), wobei für dein Problem d = v-1, und n = s+d, v = Länge des Vektors, s = gewünschte Summe. Wenn du die genaue Anzahl berechnen lassen willst, kannst du Mathematica, Maple o.ä. bemühen (Python kann's glaub auch - bin aber dort nicht zu Hause ;-)). Oder Delphi mit BigInts...

Wenn du nur Näherungswerte benötigst, dann reicht sogar ein Taschenrechner der 1970er Jahre (oder natürlich Delphi). Du kannst ausnutzen, dass log(a*b)=log(a)+log(b) und damit g := Log(n!) = Log(1)+Log(2)+...+Log(n) ist. Am besten nimmst du den 10er Log. Wenn dein Resultat m,f lautet (m vor dem Komma, f nach dem Komma), dann lautet das Resultat für n! = 10^g ≈ (0,f)^10*10^m.

Punkto "Warten auf Ausgabe". Im Code, wo jeweils ein weiterer Vektor bekannt ist, könntest du direkt in ein File schreiben. Dann stopfst du bei "grossem n tief d" keine Riesen-TStringlist (bei grosser Lösungsmenge besser integer Array) in den Arbeitsspeicher.

Wie erwähnt "Rekursive Lösungen" sind oft besser zu lesen als iterative. Bei vielen verschachtelten rekursiven Aufrufen hast du bei einer iterativen Lösung (wie zum Beispiel Uwes) u.U. mehr Performance.

[Uwe Raabe]

Bei N = 4 erzeugt mein Algorithmus 35 Ausgaben, bei N = 10 sind es schon 92378, bei N = 16 sind es 300540195. Die Zahl entspricht dem Binomialkoeffizient (n über k) mit n = 2*N-1 und k = N-1. Jedes N + 1 erzeugt knapp 4x so viele Ausgaben wie N. Damit kannst du in etwa abschätzen, wie lange es bei N = 256 wohl dauern wird. (Hinweis: Die Zahl ist ca. 4,7e+152. Dauert eine Iteration lediglich eine Nanosekunde, dann sind das ca. 4,7e+143 Sekunden oder ca. 1,5e+136 Jahre. Zum Vergleich: Das Universum ist heute ca. 1,4e+10 Jahre alt.)

Auch eine Parallelisierung würde nur wenig bringen, denn wenn ich das ohne Overhead auf 4 Kerne verteilen könnte, würde das immer noch solange dauern, als würde ich statt N = 256 nur N = 255 vorgeben. Bei 16 Cores wäre es dann so schnell wie N = 254.

[Sinspin]

Das waren noch Zeiten als solche Probleme hier oder in der EE im Zwei-Wochen-Takt besprochen wurden. Leider sind die meißten Experten von damals bereits in ihrer nächsten Inkarnation und aktuell zu jung um helfen zu können.
Keine Ahnung ob Fiete (Wolfgang) aus der EE Lust hätte etwas dazu zu sagen.
Ich hätte Lust, leider nur wenig Zeit.
Das wäre auf jeden Fall etwas was man mit Multithreading leicht beschleunigen könnte. Bin gerade am überlegen was eine GraKa von der Arbeit halten würde.

[Michael II]

Zitat:

Zitat von Sinspin (Beitrag 1540278)

Bin gerade am überlegen was eine GraKa von der Arbeit halten würde.

Eine Grafikkarte hat an (wie vorliegend) O(4^n) Problemen keine Freude. Spannend für GPU Berechnungen sind Algorithmen mit linearer, linear logarithmischer, allenfalls polynomialer Komplexität.

Im 1000Euro Bereich hat eine NVIDIA RTX3080 10'240 CUDA Kerne; Wenn du alle rechnen lässt, dann kannst du von Uwes weiter oben berechneten 10^136 Jahren 5 vom Exponenten nehmen ;-).

Nebenbei: In #18 sollte stehen: n! = 10^g ≈ 10^(0,f)*10^m, Beispiel 4! = 10^log(4!) = 10^log(1*2*3*4) = 10^(log(1)+log(2)+log(3)+log(4)). Die Summe s der logs kannst du auch für sehr grosse n noch mit einem Taschenrechner berechnen. Hier s=1.38021... - 10^1.38021... = 10^0.38021*10^1 = 2.4*10^1.
Ohne log rechnen: Bei n tief d = n!/(d!*(n-d)!) rechnest du die drei Fakultäten nicht einzeln, du kannst den Bruch kürzen und vermeidest so u.U. Overflows, wenn du mit grossen Werten rechnest. Beispiel 1024 tief 2 = 1024!/(2!*1022!) = 1024*1023/2