Post by Ralf GoertzPost by Ralf GoertzDie dritte Menge ist dann schon das Komplement der Vereinigung der
ersten beiden. Die erste Runde next_permutation wird fünfmal
durchlaufen, die zweite, darin geschachtelt, dreimal. Damit hätte man
die 15 Partitionen. Der Vorteil ist nicht nur die Vermeidung von
Dubletten sondern auch die Speichererparnis. Mein Rechner hätte
nämlich von der Zeit her locker auch größere m und n zugelassen,
allerdings kostet das Speichern im set<set<vector<int>>> dann sehr
schnell sehr viel Platz und zwingt den Computer in die Knie. Und der
Algorithmus lässt sich leicht nichtrekursiv programmieren, denke ich.
Vielleicht probiere ich es nachher mal.
Ich habe das jetzt gemacht. Alllerdings doch rekursiv. Bin aber um
Ich habs nicht bleiben lassen können, meinen Algorithmus auch mal zu
programmieren, allerdings ohne *jede* Rücksicht auf Effizienz, sondern
erst mal, ob so geht (heißt heute wohl proof of concept), noch dazu in
Perl, was bei solchen Anwendungen (bloß rechnen, nichts denken)
Größenordnungen an Rechenzeit kostet. Dazu unten mehr.
Allerdings Speicherprobleme habe ich keine: man braucht nur den Platz
für den Stack bei der Rekursion, das sind 2 Integers pro Niveau Tiefe.
Die Rekursivität kann übrigens durchaus Zeit sparen. Ich halte
momentan die Nichtrekursivität bei mir für eines der möglichen
Effizienzprobleme.
Post by Ralf GoertzThere are 126126 partitions
real 0m0.044s
user 0m0.043s
sys 0m0.001s
Das sind bei mir 9,3 sec, also Faktor 217.
Post by Ralf Goertz(Natürlich ohne output). Für 4*5 erhalte ich
There are 488864376 partitions
real 1m25.758s
user 1m25.373s
sys 0m0.033s
Das sind bei mir 10 h, also Faktor 416.
Die Faktoren sehen wild aus, sind aber Interpretation vs. Compilation
sowie ausgiebigen Laufzeitchecks geschuldet. Ich möchte das Ding mal
nach C übersetzen, was nicht so viel Arbeit ist, weil die Sachen, die
Perl besser kann, gar nicht vorkommen. Nur habe ich leider sehr wenig
Ahnung von C, auch wenn ich das eine oder andere Progrämmelchen
geschrieben habe. Aber was man machen muss, um aus einem in C
geschriebenen Algorithmus ein komplettes lauffähiges Programm zu
machen und welche Compileroptionen es gibt, da bin ich blank.
Post by Ralf GoertzKeine Ahnung, ob das jetzt äquivalent zu Helmuts Vorgehen ist. Das
ist zwar auch elegant, aber für mich nicht so intuitiv.
Ich habe es nur sehr knapp beschrieben – so schrecklich unintuitiv ist
es meiner Ansicht nach nicht. Ich hänge eine kommentierte Version an.
Mein Anliegen war:
a) Der Algorithmus soll die Lösungen produzieren, die gesucht werden,
und nicht eine Obermenge und dann die überflüssigen wegschmeißen.
Dass immer von Permutationen (also viel mehr als Kombinationen) und
Dubletten (die solls gar nicht geben) die Rede war, hat mich
alarmiert. Ob zu Recht, weiß ich nicht, so genau habe ich in die
hier veröffentlichten Algorithmen nicht hineingesehen.
b) Wenn man eine Kombination als ganze Zahl darstellt – jedes mögliche
Element 1 Bit –, dann ist es eine billige Operation, mit ein paar
Booleschen und arithmetischen Operationen die nächste Kombination
zu finden. Neu seit dem letzten Mal ist, dass es nicht teurer wird,
auch noch eine Maske von Bits dazu anzugeben, die auf jeden Fall
vorkommen müssen. Geht billig nur bis zur Wortlänge von Integers,
aber da sind wir bis jetzt ja erst bei 20.
Jetzt, wo ich schon angefangen habe, mache ich auch noch ein wenig
weiter. Mein Plan:
1. Schauen, ob die Einführung von Rekursion was bringt oder was
kostet. Es gibt dann gar keine Arrays mehr, nur noch einfache
Variable, die allerdings im Aufrufstack gestapelt werden. Keine
Ahnung, wie viel ich da ändern muss – vermutlich nicht allzu viel,
aber doch mit der Chance auf viele neue Fehler.
2. Die bessere (klarere?, schnellere?) der beiden Versionen von Hand in
C übersetzen und dann einen realistischeren Laufzeitvergleich
machen. Da könnte ich Hilfe brauchen, weil ich, wie oben erwähnt,
für C-Programme keinen Blick habe.
Die jetzige Form des Programms steht in
http://hhr-m.userweb.mwn.de/tmp/combipart.txt
Ohne die Unterprogramme zur Ausgabe von Ergebnissen sieht das so aus:
#! /usr/bin/perl
use strict;
# ========================================================================
# Unterprogramme zur Manipulation einer einzelnen Menge
# Die Menge {a1, ..., an} wird dabei als Zahl 2^a1+...+2^an dargestelt
# ========================================================================
my $nsol = multi_comb (20, 5, 0);
print "$nsol\n";
sub lastbit {
my ($x) = @_;
# die Menge, die nur das kleinste Element von x enthält
return $x & ($x ^ ($x-1));
};
sub popcount {
my ($x) = @_;
# Mächtigkeit von x (für alte CDC-Freaks: "population count")
my $res = 0;
while ($x) {
$res++;
$x = $x ^ lastbit($x);
};
return $res;
};
sub fill {
my ($x, $n, $k) = @_;
# die um die k kleinsten bisher nicht enthaltenen (Noch-nicht-)Elemente erweiterte Menge x
# n ist dabei die maximale Größe von Mengen
# Ergebnis < 0 falls nicht möglich
my $full = (1 << $n) - 1; # alle überhaupt je vorkommenden Elemente
return -1 if $x > $full; # x enthält unmögliche Elemente
return $x unless $k; # nichts hinzufügen
my $cand = $full ^ $x; # Menge der möglicherweise hinzukommenden Elemente
for (my $i=1; $i<=$k; $i++) {
return -2 unless $cand; # nicht genug Kandidaten
my $c = lastbit($cand); # zu verschiebendes Bit
$cand ^= $c; # aus cand entfernen
$x ^= $c; # zu x hinzufügen
};
return $x;
};
sub advance {
my ($x, $n, $mask) = @_;
# x ist eine Menge, die mask als Untermenge enthält
# Das Ergebnis ist die lexikografisch nächste Menge, die gleichmächtig mit x ist
# und ebenfalls mask als Untermenge enthält
# n ist dabei die maximale Größe von Mengen
# Ergebnis < 0 falls nicht möglich
my $full = (1 << $n) - 1; # alle überhaupt je vorkommenden Elemente
return -1 if $x > $full; # x enthält unmögliche Elemente
return -3 if ($x | $mask) != $x; # Bedingung für x nicht erfüllt
my $rest = $x ^ $mask; # Bits ohne mask
my $nrest = popcount($rest); # Anzahl Bits ohne mask
$x += lastbit($rest); # so viel müssen wir mindestens addieren
$x |= $mask; # die Bits von mask wieder hinzufügen
$nrest -= popcount($x ^ $mask); # soviele Bits fehlen noch
return $x unless $nrest; # nichts fehlt mehr
return fill($x, $n, $nrest); # Rest auffüllen
};
# ========================================================================
# Algorithmus zur Lösung der Aufgabe
# ========================================================================
sub multi_comb {
my ($n, $k, $output) = @_;
# Es werden alle Möglichkeiten gesucht, aus n Elementen soviele
# disjunkte Kombinationen von je k Elementen wie möglich auszuwählen.
# Vorläufig ist die Lösung nur komplett, wenn k Teiler von n ist.
# Ergebnis ist die Anzahl der Lösungen
# Falls $output gesetzt ist, werden die Lösungen ausgegeben
my ($new_comb, $mask, $success, $nsol);
my @stack = (0); # bis jetzt die leere Menge
my @mask = (1); # obligatorisch in der nächsten Kombination
while (1) {
$new_comb = fill($stack[$#stack], $n, $k); # Angefangene Lösung um neue Kombination ergänzen
if ($new_comb > 0) { # falls gelungen
$mask[$#stack] = $stack[$#stack] | lastbit($new_comb ^ $stack[$#stack]); # kleinstes neues Element obligatorisch
push(@stack, $new_comb); # eintragen
} else {
if ($output) {
printf ("%12d ", $nsol);
print_sets (@stack);
};
$nsol++;
$success = 0;
while ($#stack) { # jüngste Kombination suchen, die sich ersetzen lässt
$mask = $mask[$#stack-1];
$new_comb = advance(pop(@stack), $n, $mask); # Kombination zu ersetzen versuchen
if ($new_comb > 0) { # falls gelungen
$mask[$#stack] = $stack[$#stack] | lastbit($new_comb ^ $stack[$#stack]); # kleinstes neues Element obligatorisch
push(@stack, $new_comb); # eintragen
$success = 1;
last; # keine weitere suchen
};
};
return $nsol unless $success; # die allererste Kombination ließ sich auch nicht ersetzen
};
};
};