quarta-feira, 30 de maio de 2012

Combinações de dígitos II

Eu queria enumerar todos os inteiros de n bits com k dígitos 1. Uma olhadela nos números revelou que uma solução recursiva seria a melhor maneira de atacar o problema. Depois de gastar um pouco de fósforo, encontrei esta singela solução em Perl

sub choose {
  my $n=shift;
  my $k=shift;
  my $callback=shift;
  my @rest=@_;
  
  if($k>0) {
    for my $m ($k..$n) {
      choose($m-1, $k-1, $callback, $m, @rest); 
      &$callback($m, @rest) if $k==1;
    }
  } 
}
A função choose() recebe 4 parâmetros: n é o total de bits; k é o número de dígitos 1; callback é a função que será executada para cada combinação; e rest é um array que contém os dígitos das recursões anteriores (e que assim possibilita termos toda a informação na ponta da recursão sem recorrer a variáveis globais).

A função callback() recebe uma lista com os índices dos bits 1 na iteração atual. Então, se ela recebe (1, 4), isso significa que o primeiro e o quarto bits são 1. Os outros são 0.

Pois bem, com o seguinte teste enumerei todos os números de 8 bits com 7 dígitos ligados:

sub to_number {
  my $total=0;
  map { $total+=2**($_-1) } @_;
  print "$total\n";
}

choose(8, 7, \&to_number);
Esse código imprime a seguinte seqüência: 127, 191, 223, 239, 247, 251, 253, 254. Alternativamente, se eu quisesse enumerar combinações de letras (não deveria haver um verbo eletrar?), eu poderia fazer o seguinte:

choose(4, 2, sub { 
  print map { ('A'..'D')[$_-1] } @_;
  print "\n";
});
Esse código apresenta todos os pares com as letras de A a D: AB, AC, BC, AD, BD, e CD.

Um comentário:

Marcus Aurelius disse...

Verbo eletrar? Acho que não, porque é boa prática de software reutilizar a mesma função e passar o elemento em questão como parâmetro em vez de deixar hard-coded :-)