Weil's so schön war -- noch eine mathematische Spielerei, die sich mit einem Perl-Skript knacken läßt.
Mein Biermann um die Ecke ist ein ehemaliger Software-Ingenieur, der seinen Job hingeschmissen und einen Liquor-Store eröffnet hat ([1]). Als ich neulich Bier kaufte und, wie es in Amerika so Sitte ist, mit ihm ein Schwätzchen hielt, erzählte ich ihm die Aufgabe mit den Ziegen ([2]). Daraufhin revanchierte er sich mit einer Aufgabe aus seinem Repertoire:
In einem Laden steht eine Balkenwaage mit vier Gewichten, mit denen sich tatsächlich Waren von 1, 2, 3, ... 40 Gramm aufs Gramm genau abwiegen lassen. Wie sind die Gewichte beschaffen? Hätte man zum Beispiel zwei Gewichte von je einem Gramm und zwei weitere von je drei Gramm, könnte man damit Waren von 1, 2, 3, 4, 5, 6, 7 und 8 Gramm abwiegen, denn man kann die Gewichte auf beiden Seiten der Waage zusammen mit der Ware plazieren. Eine zwei Gramm schwere Ware kann man dann zum Beispiel abwiegen, indem man auf der einen Seite der Balkenwage ein 3-er Gewicht legt und auf die andere Seite die Ware mitsamt dem 1-er Gewicht. Wiegt die Ware genau 2 Gramm, pendelt sich die Balkenwaage in der Mitte ein. Nun die Frage -- welche vier Gewichte braucht's, damit man nicht nur von 1 bis 8 Gramm, sondern von 1 bis 40 Gramm alles abwiegen kann?
Schwierige Sache. Wie wär's mit einem Perlskript, das alle Möglichkeiten durchprobiert? Wir fangen einfach mit vier Einer-Gewichten an, sehen, wie die sich kombinieren lassen, dann geht's weiter mit drei Einern und einem Zweier, und so weiter, bis wir vier Vierziger-Gewichte haben und damit garantiert weit übers Ziel hinausgeschossen und am Ende aller Möglichkeiten sind:
1, 1, 1, 1
1, 1, 1, 2
...
1, 1,40, 1
...
1,40, 1, 1
...
40,40,40,40
Auf der Suche nach einem Algorithmus, um diese Folge zu erzeugen, hilft folgende Darstellung:
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
Das sind die Zahlen von 0 bis 7 im Binärsystem, deren Ziffern alle Kombinationen von Nullen und Einsen durchprobieren. Die Kombination für die Gewichte oben läßt sich also ganz einfach erzeugen, indem man im 40er-Zahlen-System von 0 bis 404-1 zählt -- 2.560.000 verschiedene Kombinationen.
Listing weights.pl zeigt ab Zeile 40 die Implementierung der
Combine-Klasse, deren Konstruktor zwei Werte erwartet: $n,
die Zahl der unterschiedlichen Zeichen im gewählten Zahlensystem
(z.B. 2 im Binärsystem) und $k, die Anzahl der Stellen, also die
Länge der Ergebnistupel. Kombinatorisch gesehen ist $n die Anzahl
verschiedener Kugeln in einer Urne, und $k die Anzahl der Kugeln,
die man pro Durchgang mit (!) Zurücklegen zieht. Die Ergebnistupel
zeigen alle verschiedenen Möglichkeiten an, wie das Experiment
ausgehen kann. Die next-Methode eines Objekts der Klasse Combine
liefert mit jedem neuen Aufruf einen anderen Ergebnistupel -- bis
sie alle durchgetrieben wurden.
Alle dreistelligen Zahlen im 2-er-System, wie oben angegeben, gibt also
folgender Perl-Code aus:
my $comb = Combine->new(2, 3);
while(@tuple = $comb->next()) {
print "@tuple\n";
}
weights.pl definiert in den Zeilen 3-5 die Konstanten für die
Anzahl der erlaubten Gewichte ($NOF_WEIGHTS), die Anzahl der
Gewichtsunterschiede ($NOF_DIFFS), die durch Kombinieren der
Gewichte erzeugt werden sollen und schließlich mit $MAX_WEIGHT
die größte erlaubte Masse eines einzelnen Gewichtes.
Zeile 7 erzeugt das Kombinations-Objekt und die while-Schleife
ab Zeile 10 iteriert über alle Kombinationen.
Der Kombinationsalgorithmus liefert Tupel von 0,0,0,0 bis 39,39,39,39,
aber da 1,1,1,1 bis 40,40,40,40 für Gewichte realistischer ist,
zählt Zeile 11 zu jedem Tupel-Element flugs Eins dazu.
Die in Zeile 12 aufgerufene Funktion calc_diffs errechnet die
Anzahl der mit einem gegebenen Tupel erreichbaren Gewichtsverteilungen.
Wenn die Zahl 40 zurückkommt, ist das Ziel erreicht, alle Gewichte
von 1 bis 40 können simuliert werden und Zeile 17 bricht die
Schleife und damit das Skript ab. In der Variablen $best
steht immer der bis dato beste erreichte Wert. Jedesmal, wenn sich
etwas verbessert, gibt Zeile 14 den untersuchten Tupel und die Anzahl der
möglichen Kombinationen aus.
Wie errechnet man nun die verschiedenen Wäge-Kombinationen
aus einem Gewichte-Tupel? Für jedes Element eines Tupels, also für
jedes Gewicht, gibt es drei Möglichkeiten: Es bleibt entweder außen
vor oder steht entweder links oder rechts auf der Waage. Wenn
man diese drei Zustände als 0 , 1 und 2 markiert, gibt es
die folgenden Möglichkeiten, die Gewichte über die Waage zu
verteilen und so Gewichtsdifferenzen zu erzeugen, die man zum abwiegen
der Waren nutzen kann:
0 0 0 0
0 0 0 1
0 0 0 2
0 0 1 0
...
2 2 2 2
Die Folge beginnt mit dem Null-Tupel (kein Gewicht auf der Waage), beim zweiten Tupel liegt das vierte Gewicht auf der linken Seite der Waage, beim dritten auf der rechten. Beim vierten liegt das dritte Gewicht auf der linken Seite, und so weiter, bis schließlich im letzten Tupel alle Gewichte auf der rechten Seite der Waage liegen.
Die mit jeder Kombination erreichte Gewichtsdifferenz zwischen linker
und rechter Seite der Waage errechnet sich einfach aus der mit
0 , -1 oder 1 gewichteten Summe der Einzelgewichte, je nachdem
ob das jeweilige Gewicht der Waage fernblieb, oder auf der linken
oder der rechten Seite der Waage zu liegen kam.
Die ab Zeile 20 definierte Funktion calc_diff nimmt einen
Gewichtstupel als Array mit vier Elementen entgegen und erzeugt das oben
erläuterte Wägeraster -- natürlich wieder mit einem
Objekt vom Typ Combine, diesmal mit einem Wert von 3 für $n
(drei Zustände: nicht auf der Waage, links oder rechts) und
4 für $k (weil's 4er-Tupel sind).
Die while-Schleife ab Zeile 26 iteriert dann über die Wägeverteilungen
und die foreach-Schleife ab Zeile 29 errechnet für jede
Gewichtekombination die Wägedifferenz in $diff.
Der Hash %diffs in Zeile 34 erhält für jede geschaffene
Gewichtsdifferenz einen neuen Eintrag, die abs-Funktion sorgt dafür,
daß positive und negative Differenzen nur je einmal zählen, schließlich
spielt es keine Rolle, ob die Balkenwaage nach links oder rechts
ausschlägt, allein das Differenzgewicht zählt, das man zum Abwiegen
von Waren nutzen kann.
Zeile 36 gibt die Anzahl der Einträge im Hash zurück -- die Anzahl der mit der aktuellen Gewichteauswahl und -verteilung erreichbaren Wiegedifferenzen.
Die Klasse Combine, deren next-Methode alle möglichen
Verteilungen der Reihe nach hervorzaubert, ist ab Zeile 40 definiert.
So wie bei einer Dezimalzahl die rechteste Ziffer mit 1, die
zweitrechteste mit 10, die drittrechteste mit 100 usw. gewichtet
ist, sodaß
123 = 1*102 + 2*101 + 3*100,
also
1*100 + 2*10 + 3*1 ist, läßt sich eine dreistellige
Zahl abc im n-System als
a*n2 + b*n1 + c*n0
darstellen.
Für die acht Zahlen 0 bis 7 im Zweiersystem mit
dreiziffrigen Zahlen gilt beispielsweise:
Gewicht: 4 2 1
0 = 0*4 + 0*2 + 0*1 0 0 0
1 = 0*4 + 0*2 + 1*1 0 0 1
2 = 0*4 + 1*2 + 0*1 0 1 0
... ...
7 = 1*4 + 1*2 + 1*1 1 1 1
Nach diesem System ermittelt der Konstruktor der Combine-Klasse
einen Array mit Faktoren, um die einzelnen Stellen der
Zahlen im n-System
zu multiplizieren:
Der map-Befehl in Zeile 49 transformiert den
Array mit den Zahlen von 0 bis $k-1 in
(1, ..., $n$k-2, $n$k-1),
was für $n=2 und $k=3 als
(1,2,4) herauskommt. Die reverse-Funktion dreht den Array um,
macht also (4,2,1) daraus. Zeile 48 legt eine Referenz auf diesen Array
in der Instanzvariable weights des Combine-Objekts ab.
Zwei weitere Instanzvariablen führt ein Combine-Objekt:
total, die Anzahl der insgesamt möglichen Kombinationen,
und count, einen Zähler, der bei 0 startet und bei jedem
Aufruf der next-Methode um eins erhöht wird.
Jeder Stand von count wird in eine Zahl im n-System verwandelt.
Falls die next-Methode in Zeile 60 feststellt, daß der Zählerstand
bereits gleich der maximal möglichen Anzahl von Kombinationen ist, liefert
sie statt einem neuen n-Tupel einfach einen leeren Array zurück und
signalisiert so dem Aufrufer, daß keine weiteren Kombinationen
mehr nachkommen.
Die foreach-Schleife ab Zeile 62 iteriert über den Array der
Gewichtungen und findet den Wert jeder einzelnen Ziffer von
count im n-System heraus, indem es $count jeweils durch
das Gewicht an der entsprechenden Stelle ($weight) teilt und
das Ergebnis mit der int-Funktion auf ganze Zahlen abrundet.
Zeile 64 hängt die ermittelte Ziffer an den @result-Array an
und Zeile 65 präpariert den verbleibenden Wert der darzustellenden
Zahl.
Zeile 68 zählt den internen Zähler count für den nächsten
Aufruf der next-Methode um eins hoch, bevor Zeile 70 die
Ergebniszahl im n-System als Array an den
Aufrufer der next-Methode zurückgibt.
Nachdem ich mich schon darauf eingestellt hatte, den Rechner
über Nacht laufen zu lassen, war ich nicht schlecht erstaunt,
als das Skript schon nach 38 Sekunden mit
dem Ergebnis abbrach -- der Spannung halber wird's hier nicht
abgedruckt, wer will, kann es auf
http://perlmeister.com/weights.html
nachlesen. Nur soviel: Man kommt sich ganz schön doof vor,
weil man nicht gleich draufgekommen ist. Der Biermann
staunte jedenfalls nicht schlecht.
01 #!/usr/bin/perl -w
02
03 my $NOF_WEIGHTS = 4;
04 my $NOF_DIFFS = 40;
05 my $MAX_WEIGHT = 40;
06
07 my $comb = Combine->new($MAX_WEIGHT, $NOF_WEIGHTS);
08 my $best = 0;
09
10 while(my @onecomb = $comb->next()) {
11 @onecomb = map { $_ + 1 } @onecomb;
12 my $diffs = calc_diffs(@onecomb);
13 if($diffs > $best) {
14 print join(',', @onecomb), " ($diffs)\n";
15 $best = $diffs;
16 }
17 last if $diffs == $NOF_DIFFS;
18 }
19
20 sub calc_diffs {
21 my @weights = @_;
22 my %diffs = ();
23
24 my $scalecomb = Combine->new(3, $NOF_WEIGHTS);
25
26 while(my @scale = $scalecomb->next()) {
27 my $diff = 0;
28 my $i = 0;
29 foreach my $scaleloc (@scale) {
30 $diff += $weights[$i] if $scaleloc == 1;
31 $diff -= $weights[$i] if $scaleloc == 2;
32 $i++;
33 }
34 $diffs{abs($diff)}++ if $diff;
35 }
36 return scalar keys %diffs;
37 }
38
39
40 package Combine;
41
42 sub new {
43 my ($class, $n, $k) = @_;
44
45 my $self = { count => 0,
46 total => $n ** $k };
47
48 $self->{weights} =
49 [reverse map { $n**$_ } (0..$k-1)];
50
51 bless $self, shift;
52 }
53
54 sub next {
55 my $self = shift;
56
57 my $count = $self->{count};
58 my @result = ();
59
60 return () if $count == $self->{total};
61
62 foreach my $weight (@{$self->{weights}}) {
63 my $val = int $count/$weight;
64 push @result, $val;
65 $count -= $val * $weight;
66 }
67
68 $self->{count}++;
69
70 @result;
71 }
|
|
Michael Schilliarbeitet als Software-Engineer bei Yahoo! in Sunnyvale, Kalifornien. Er hat "Goto Perl 5" (deutsch) und "Perl Power" (englisch) für Addison-Wesley geschrieben und ist unter mschilli@perlmeister.com zu erreichen. Seine Homepage: http://perlmeister.com. |