Subconjuntos de un Conjunto

Introducción

El siguiente ejemplo muestra un iterador sobre los subconjuntos de un conjunto dado. El conjunto viene definido por los argumentos en línea de comando. Sigue un ejemplo de ejecución:

lhp@nereida:~/Lperl/src$ perl allsubsets.pl A B C D
()
(A)
(B)
(A, B)
(C)
(A, C)
(B, C)
(A, B, C)
(D)
(A, D)
(B, D)
(A, B, D)
(C, D)
(A, C, D)
(B, C, D)
(A, B, C, D)

Número en Binario = Conjunto

La idea en la que se basa el iterador de conjuntos es que la representación binaria de un número puede verse como la definición de un conjunto. Los unos indican pertenencia y los ceros no pertenencia. Observe la misma ejecución anterior pero prefijado con la representación binaria del número de orden:

~/Lperl/src$ perl allsubsets.pl A B C D | perl -ne 'printf "%2d:%4b %s",$k,$k,$_; $k++'
 0:   0 ()
 1:   1 (A)
 2:  10 (B)
 3:  11 (A, B)
 4: 100 (C)
 5: 101 (A, C)
 6: 110 (B, C)
 7: 111 (A, B, C)
 8:1000 (D)
 9:1001 (A, D)
10:1010 (B, D)
11:1011 (A, B, D)
12:1100 (C, D)
13:1101 (A, C, D)
14:1110 (B, C, D)
15:1111 (A, B, C, D)

La opción -n de Perl

La opción -n de Perl inserta el siguiente bucle alrededor de nuestro programa:

        LINE:
          while (<>) {
              ...             # nuestro programa va aqui
          }

Asi pues el comando perl -ne 'printf "%2d:%4b %s",$k,$k,$_; $k++' se convierte en:

        LINE:
          while (<>) {
              printf "%2d:%4b %s",$k,$k,$_; $k++
          }

LLamadas al Iterador

Los conjuntos son representados mediante listas. Dado que el conjunto vacío es un subconjunto de cualquier conjunto y que el conjunto vacío es representado mediante la lista vacía no podemos usar como criterio de finalización el retorno de la lista vacía.

lhp@nereida:~/Lperl/src$ sed -ne '20,$p' allsubsets.pl | cat -n
     1  my @S;
     2  FOREVER: {
     3    @S = $s->();
     4
     5    local $" = ', ';
     6    print "(@S)\n";
     7
     8    last if (@S == @ARGV);
     9
    10    redo FOREVER;
    11  }

Constructor

Sigue el código:

lhp@nereida:~/Lperl/src$ cat -n allsubsets.pl
 1  #!/usr/bin/perl -w
 2  use strict;
 3
 4  sub subsets {
 5    my @set = @_;
 6    my $powern = 1 << @set;
 7    my $n = -1;
 8
 9    my $s = sub {
10      $n++;
11      return map {  $n & (1 << $_)? ($set[$_]) : () } 0..$#set;
12    };
13
14    return $s;
15  }
16
17  die "$0 el1 el2 el3 ...\n" unless @ARGV;
18  my $s = subsets(@ARGV);
19
20  my @S;
21  FOREVER: {
22    @S = $s->();
23
24    local $" = ', ';
25    print "(@S)\n";
26
27    last if (@S == @ARGV);
28
29    redo FOREVER;
30  }