RDW2: Golf-Auswertung

Einleitung

Das Rätsel der Woche Nummer 2 der deutschen Perl-Community hatte folgende Aufgabenstellung: Schreibe ein Perl-Programm, das eine Potenzmenge berechnet. Auf Vorschlag von pq entstand eine etwas erweiterte Aufgabenstellung: Schreibe ein möglichst kurzes Perl-Programm, das eine Potenzmenge berechnet. Dabei war die Eingabe und das Ausgabeformat vorgegeben; es sollte folgendermaßen aussehen:

$ ./potenzmenge.pl 1 2
()
(1)
(2)
(1 2)

Lösungen wurden (in zeitlicher Reihenfolge) von pq (59 Zeichen), Taulmarill (70 Zeichen, ohne Ausgabe), DS (58 Zeichen) und mir (57 Zeichen) gepostet. Durch Zusammenarbeit von DS, Taulmarill und mir entstand danach eine 53-zeichige „gemeinsame Lösung”. Ich werde alle diese Lösungen hier erklären, nur lasse ich meine ursprüngliche weg, da in ihr keine Gedanken enthalten sind, die nicht auch in den anderen enthalten wären.

Inhalt

• Allgemeine Bemerkungen
• Lösung von pq
• Lösung von Taulmarill
• Lösung von DS
• gemeinsame Lösung
• Autor

Es werden zwei verschiedene Algorithmen angewandt: Der „Verdopplungs-Algorithmus” (ähnlich A2) von pq und Taulmarill; der „Binär-Algorithmus” von DS und mir sowie in der gemeinsamen Lösung.

Ich habe die Programme nicht gebenchmarkt, aber sie laufen alle in annehmlicher Zeit durch. Theoretisch braucht der Binär-Algorithmus weniger Speicher (wie unten beschrieben), jedoch habe ich noch keine experimentellen Erweise dafür. Es dürfte bei vielen Elementen ins Gewicht fallen. Wenn jemand Benchmarks durchführt, kann ich sie gerne in dieses Dokument einfügen.

Laut der ursprünglichen Aufgabenstellung (die nicht für das Golf geschrieben wurde) sollte eine Funktion P() geschrieben werden, die eine Potenzmenge berechnet. Bis auf Taulmarill (dessen Lösung keine Ausgabe beinhaltet) entschieden sich alle Golfer dagegen, diese Funktion tatsächlich zu implementieren, da sie zu viele Zeichen bräuchte. Stattdessen berechnen die Skripte direkt die Potenzmenge der Parameterliste @ARGV und geben sie auf das Terminal aus.

Alle Golf-Lösungen kommen mit beliebigen alphanumerischen Eingabewerten klar und sind sogar 8-Bit-clean.

Die Ausgabereihenfolge ist bei keiner Lösung besonders übersichtlich. Man muss jedoch erwähnen, dass sie bei dem Binär-Algorithmus am schlimmsten ist.

Lösung von pq

#!/usr/bin/perl
@_=[];for$e(@ARGV){@_=map{[@$_,$e],$_}@_}print"(@$_)
"for@_

Um dies zu verstehen, wird es zunächst etwas ausführlicher geschrieben:

#!/usr/bin/perl
use strict;

my @array=([]);
for my $element (@ARGV) {
  @array = map {[@$_, $element], $_} @array
}
for (@array) {
  print "(@$_)\n";
}

Der Algorithmus ähnelt Algorithmus A2.

@array ist ein Array of Arrays. Zunächst enthält es nur das leere Array (entspricht der leeren Menge). Dann wird für jedes Element der Eingabemenge jedes $element von @array dupliziert, wobei an das Duplikat das $element angehängt wird. Mit Worten lässt sich dies schwer beschreiben, aber die folgende Tabelle wird Klarheit vermitteln:

Hier wird der Aufbau des @arrays für die Eingabemenge {1,2,3} dargestellt. In der linken Spalte steht jeweils das aktuelle $element, während in der rechten Spalte das @array steht.

Betrachten wir beispielsweise den Übergang von der zweiten zur dritten Zeile. Aus [1] werden die beiden Elemente [1,2], [1]. Das zweite davon ist das ursprüngliche; das erste entsteht durch Hinzufügen der 2. Ebenso wird aus [] in der zweiten Zeile [2], [] in der dritten Zeile. Das zweite Element ist wieder das ursprüngliche; das erste entsteht durch Hinzufügen der 2.

Rechts unten schließlich steht die Potenzmenge von {1,2,3}.

sub P{sub _{@_?map{my$f=pop@_;[$f],map{[$f,@$_]}_(@_)}@_:()};[],_(@_)}

Dieses Programm enthält keine Ausgabefunktion. Um es zu testen, speichere man es als taulmarill.pl und führe perl -le 'do "taulmarill.pl"; print "@$_" for P(1,2,3)' aus.

Hiervon gibt es auch eine Nicht-Golf-Version, die ich hier eingefügt habe:

#!/usr/local/bin/perl

use strict;
use warnings;
use Data::Dumper;

my @mengeA = qw/1 2 3/;

print Dumper funcP(@mengeA);

sub funcP {
  return ( [], rec(@_) );
}

sub rec {
  return () unless @_;

  map {
      my $first = shift @_;
      [$first], map { [ $first, @$_ ] } rec(@_);
  } @_;
}

Auch wenn dieser Algorithmus rekursiv ist, gleicht er prinzipiell dem von pq. Bei pq wurde ein Array anfänglich mit ([]) initialisiert. Das findet sich hier wieder, indem funcP() die leere Menge vor das Ergebnis der rekursiven Subroutine rec() hängt. rec() führt dann das oben beschriebene sukzessive Verdoppeln durch.

Ich habe mir erlaubt, einen Zeilenumbruch einzufügen, damit die Lösung die Aufgabenstellung erfüllt. Damit erhöhte sich die Länge auf 58 Zeichen.

for$a(1..2**@ARGV){print"{@ARGV[grep$a&2**$_,0..@ARGV]}
"}

Lesbare Version:

use strict;

for my $a (1..2**@ARGV) {
  my @teilmenge = @ARGV[grep {$a & 2**$_} 0..@ARGV];
  print "{@teilmenge}\n";
}

Hier liegt ein komplett neuer Algorithmus vor. Er beruht auf der Beobachtung (der Beweis sei den Mathematikern überlassen), dass in den Zahlen von 0 bis 2ⁿ-1 in Binärdarstellung jede mögliche Kombination aus Einsen und Nullen von der Länge n vorkommt. Die folgende Tabelle zeigt dies für n=2:

Eine Formulierung der Aufgabenstellung wäre: Finde jede mögliche Kombination der Elemente der Eingabemenge. Wer sich noch an den letzten Absatz erinnert, dem wird aufgefallen sein, dass er zwei Sätze mit „jede mögliche Kombination” gelesen hat. Wir müssen also nur noch die Kombinationen aus Nullen und Einsen in die Kombinationen der Elemente der Eingabemenge umrechnen. Dies geschieht folgendermaßen: Steht an der ersten Stelle der Binärzahl eine Eins, so kommt das erste Element der Eingabemenge in die Teilmenge. Steht eine Null, kommt es nicht hinein. In der folgenden Tabelle werden auf diese Weise alle Teilmengen der Eingabemenge {1,2} gebildet:

Im obigen Perl-Skript wird die Überprüfung, ob an der $_ten Stelle (von rechts) in der Binärdarstellung von $a eine Eins steht, mit der logischen Operation $a & 2**$_ realisiert.

Man beachte, dass @ARGV (in skalarem Kontext) die Anzahl n der Elemente der Eingabemenge ist. Das aufmerksame Auge wird sehen, dass 0..@ARGV nicht n sondern n+1 Elemente hat. Damit wird jede Binärzahl auf n+1 statt n Ziffern überprüft. Dies macht keinen Unterschied, da die linksliegenden Stellen stets Null sind. Dies spart ein Zeichen ein, auch wenn es laufzeitmäßig einen kleinen Nachteil bringt. Leider bin ich nicht selbst auf diese Idee gekommen.

Dieser Algorithmus hat einen speichertechnischen Vorteil gegenüber vielen anderen Algorithmen zur Potenzmengenberechnung: Es muss kein Array aufgebaut werden, sondern die Teilmengen können direkt in der Schleife ausgegeben werden.

Ein Nachteil von diesem Algorithmus ist, dass die Ausgabereihenfolge sicherlich unschöner als bei allen Konkurrenzalgorithmen ist.

(Anmerkung: Ich habe oben „Kombination” in zwei verschiedenen Bedeutungen verwendet. Hoffentlich ist es keinem aufgefallen. Es war aus didaktischen Gründen unerlässlich.)

Übrigens machte auch Ronnie Anwendung von einem Algorithmus, der diesem ähnelt.

print"(@x[grep$i&1<<$_,0..@x])
"until$i++>>(@x=@ARGV)

Dies ist algorithmisch kaum ein Unterschied zur DS-Lösung. DS sagt hier, dass es eine Optimierung meiner Lösung sei.

Zunächst fällt auf, dass @ARGV in @x umbenannt wurde, womit insgesamt ein Zeichen gespart werden konnte. Verkürzt wurde auch der Schleifenkopf, der jetzt am Ende steht. Es wird keine for-Schleife verwendet, sondern es wird die Variable $i hochgezählt, bis eine Abbruchbedingung erfüllt ist.

Diese Abbruchbedingung, $i >> @ARGV, soll hier etwas genauer beleuchtet werden: Mit der Schiebe-Operation wird die Laufvariable um genau n Bits (n ist die Anzahl der Eingabeelemente) nach rechts geschoben. Dabei fallen alle Einsen heraus und es bleibt eine Null. Erst wenn das n+1te Bit von rechts Eins ist, bleibt nach >> ein wahrer Wert übrig. In diesem Moment hat die Laufvariable den Wert 2ⁿ überschritten und die Schleife kann abgebrochen werden.

Autor

betterworld alias Christoph Bußenius.

Fragen, Kritik und Anregungen zu diesem Text bitte auf board.perl-community.de in einem geeigneten Thread.