Interessante (?) Frage Kombinatorik

[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 von 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)

Hmmmmm..... ...... hmmmmmmmmmm again
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 von Möbius:

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

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.