Versuch, alle Teilmengen ( Powerset ) der 9-stelligen Zeichenfolge 'ABCDEFGHI' zu berechnen.
Unter Verwendung von standardmäßigen rekursiven Methoden trifft mein Computer vor dem Abschluss einen Fehler von 1 GB. Ich habe kein physisches Gedächtnis mehr.
Wie kann das besser gemacht werden? Die Sprache ist kein Problem, und die Ergebnisse, die an die Standardausgabe gesendet werden, sind ebenfalls gut - sie müssen nicht alle vor der Ausgabe im Speicher gehalten werden.
Es gibt ein triviales bijektives Mapping von der Potenzmenge von X = {A, B, C, D, E, F, G, H, I} auf die Menge von Zahlen zwischen 0 und 2 ^ | X | = 2 ^ 9:
Ø entspricht 000000000 (Basis 2)
{A} entspricht 100000000 (Basis 2)
{B} entspricht 010000000 (Basis 2)
{C} entspricht 001000000 (Basis 2)
...
{I} entspricht 000000001 (Basis 2)
{A, B} entspricht 110000000 (Basis 2)
{A, C} entspricht 101000000 (Basis 2)
...
{A, B, C, D, E, F, G, H, I} entspricht 111111111 (Basis 2)
Sie können diese Beobachtung verwenden, um die Potenzmenge wie folgt zu erzeugen (Pseudocode):
%Vor%Auf diese Weise vermeiden Sie eine Rekursion (und je nachdem, für was Sie das Powerset brauchen, können Sie das Powerset sogar "generieren", ohne viele Datenstrukturen zu vergeben - zum Beispiel, wenn Sie nur die Kraft eingestellt).
Ich würde dafür Divide and Conquer benutzen:
%Vor%Auf diese Weise sehen Sie sofort, dass die Anzahl der Lösungen 2 ^ | originalSet | ist - deshalb wird es "Kraftset" genannt. In Ihrem Fall wäre dies 2 ^ 9, daher sollte auf einem 1-GB-Gerät kein Speicherfehler auftreten. Ich nehme an, Sie haben einen Fehler in Ihrem Algorithmus.
Wie wäre es mit dieser eleganten Lösung? Erweitern Sie den Code, der nCr erzeugt, um für r = 1 bis n zu iterieren!
%Vor%Die Ausgabe:
%Vor%Tags und Links algorithm language-agnostic recursion powerset