組み合わせと順列の数え上げのアルゴリズム

Perl で組み合わせの数え上げが欲しかったのだが、CPAN からのインストールには C が必要なようなので、できれば避けたい。これぐらいなら、Perl 自体で書けるだろうと、参考となるサイトを探すと…意外にない。

そして見つけたいくつかの日本語のサイトでは、nCr = nCr=(n-1)Cr + (n-1)C(r-1) の式を使って示していた。いや、もっと効率の良い方法があったはず…と海外のサイトを調べると、最近、私が勉強している Python でアルゴリズムを示しているサイトがあったので、それを Perl に書き換えてみた。

なお、「数え上げ」という言葉を使ったが、数を求めるのと区別するために、組み合わせや順列の「生成」と言ったり「列挙」と言ったりもするようだ。

組み合わせ (combinationis) に関しては、ソースを読めばアルゴリズムは理解できるが、順列 (permutations) に関しては私は理解できなかった。本来、タイトルで示していることからは、アルゴリズムの説明を期待されるところだが、それは勘弁していただきたい。

{
  package Combinations;
  
  sub new {
    my $class = shift;
    my $obj = {};
    $obj->{l} = shift;
    $obj->{r} = shift;
    bless $obj, $class;
    return $obj;
  }
  
  sub next {
    my $self = shift;
    my $n = scalar @{$self->{l}};
    my $r = $self->{r};
    if (! exists $self->{tmp}) {
      $self->{tmp} = [0 .. ($r - 1)];
    } else {
      my $i;
      for ($i = $r - 1; $i >= 0; $i--) {
        if ($self->{tmp}->[$i] != $i + $n - $r) {
          last;
        }
      }
      if ($i == -1) {
        return undef;
      }
      $self->{tmp}->[$i]++;
      for (my $j = $i + 1; $j < $r; $j++) {
        $self->{tmp}->[$j] = $self->{tmp}->[$j - 1] + 1;
      }
    }
    my @r;
    foreach my $c (@{$self->{tmp}}) {
      push(@r, $self->{l}->[$c]);
    }
    return \@r;
  }
}

{
  package Permutations;
  
  sub new {
    my $class = shift;
    my $obj = {};
    $obj->{l} = shift;
    $obj->{r} = shift;
    if (! defined $obj->{r}) {
      $obj->{r} = scalar @{$obj->{l}};
    }
    bless $obj, $class;
    return $obj;
  }
  
  sub next {
    my $self = shift;
    my $n = scalar @{$self->{l}};
    my $r = $self->{r};
    
    if (! exists $self->{tmp}) {
      $self->{tmp} = [0 .. ($n - 1)];
      my @l = reverse(($n - $r + 1) .. $n);
      $self->{cycles} = \@l;
    } else {
      my $i;
      for ($i = $r - 1; $i >= 0; $i--) {
        $self->{cycles}->[$i]--;
        if ($self->{cycles}->[$i] == 0) {
          my $c = splice(@{$self->{tmp}}, $i, 1);
          push(@{$self->{tmp}}, $c);
          $self->{cycles}->[$i] = $n - $i;
        } else {
          my $j = $self->{cycles}->[$i];
          my $tmp = $self->{tmp}->[$i];
          $self->{tmp}->[$i] = $self->{tmp}->[-$j];
          $self->{tmp}->[-$j] = $tmp;
          last;
        }
      }
      if ($i == -1) {
        return undef;
      }
    }
    
    my @r;
    for (my $i = 0; $i < $r; $i++) {
      push(@r, $self->{l}->[$self->{tmp}->[$i]]);
    }
    return \@r;
  }
}


MAIN:
{
  print "Combinations:\n";
  my $comb = Combinations->new(["a", "b", "c", "d"], 2);
  while (my $l = $comb->next()) {
    print join(",", @$l) . "\n";
  }
  
  print "\nPermutations:\n";
  my $perm = Permutations->new(["a", "b", "c", "d"], 2);
  while (my $l = $perm->next()) {
    print join(",", @$l) . "\n";
  }
}

下記の参考にしたサイトでは変数名が indices になっているところを、tmp に置き換えている以外は、だいたい同じなので、少なくとも私に著作権はなさそうである。数式や証明に著作権がないように、このプログラムはパブリックドメインのはず。

ちなみに実行すると次のようになる。

$ perl combinations.pl
Combinations:
a,b
a,c
a,d
b,c
b,d
c,d

Permutations:
a,b
a,c
a,d
b,a
b,c
b,d
c,a
c,b
c,d
d,a
d,b
d,c

他の値でも試したが、ちゃんと数え上げられているようである。

■参考
  ●《組み合わせ（Combination）の数え上げのコードを書いてみた - くそにそてくにっく》。さらに元となるサイトがあったようだが、見つからなかった。ここが日本語で「組み合わせ 数え上げ アルゴリズム -爆発」でググると最初に来る。
  ●《組み合わせの数え上げ | tamaのblog》。ビットで表現することで効率化しているということらしい。ただ、下の海外のサイトのほうが効率的だと思う。
  ●《python - Where can I find source code for itertools.combinations（）function - Stack Overflow》。組み合わせのアルゴリズム。C で書かれているコードを Python コードで説明していてわかりやすい。
  ●《algorithm for python itertools.permutations - Stack Overflow》。順列のアルゴリズム。C で書かれているコードを Python コードで説明している。アルゴリズムの理屈についても少し書かれているようだが、他に教科書がないと理解できないと思う。(私が理解できなかっただけ？)
  ●《Algorithm::Combinatorics - search.cpan.org》。上の私のコードを使う必要はまったくなく、ちゃんと Perl モジュールが存在している。あくまでアルゴリズムの参考と、自分の確認のためにこの記事を書いた。
    
■配布物
  
上のソースに use strict とかちょっとシンタックスシュガーをまぶしたソースも公開しておく。

  ●combinations.pl
    
更新：2018-04-11,2018-04-20,2018-04-25
初公開：2018年04月11日 21:47:56
最新版：2018年04月25日 21:03:45


Comments:

[E:aquarius] 初公開：combinations-20180411.pl。バージョン 0.01。

[cocolog:89185782] に今回の感想をひとことしておいた。

投稿: JRF | 2018-04-11 22:20:54 (JST)

[E:baseball] 更新：combinations-20180420.pl。バージョン 0.02。

Perl を知らない人も読めるようにするため迷ったのだが、splice ぐらいはかまわないか…と、Permutations の途中を splice を使って書き換えておいた。splice の意味がわからない人は、ググるなり、海外の Python バージョンを読むなり、前のバージョンを読むなりして欲しい。

投稿: JRF | 2018-04-20 20:23:48 (JST)

[E:music] アルゴリズムの本を立ち読みしてきた。ここと同じアルゴリズムの紹介はなかったように思う。が、組み合わせや順列の「数え上げ」ではなく「生成」という言葉を使うべきことを知った。その旨を、上の最初のところで「なお」以下に書き足しておいた。ちなみに「生成」の言葉でググると「数え上げ」でググるより多くのサイトがマッチする。

投稿: JRF | 2018-04-25 21:09:57 (JST)

Links:

組み合わせ（Combination）の数え上げのコードを書いてみた - くそにそてくにっく: http://d.hatena.ne.jp/niso1985/20090823/1251020418 (hbm)
組み合わせの数え上げ | tamaのblog: http://muscle199x.blog.fc2.com/blog-entry-65.html (hbm)
python - Where can I find source code for itertools.combinations（）function - Stack Overflow: https://stackoverflow.com/questions/5731505/where-can-i-find-source-code-for-itertools-combinations-function (hbm)
algorithm for python itertools.permutations - Stack Overflow: https://stackoverflow.com/questions/2565619/algorithm-for-python-itertools-permutations (hbm)
Algorithm::Combinatorics - search.cpan.org: http://search.cpan.org/~fxn/Algorithm-Combinatorics-0.27/Combinatorics.pm (hbm)
combinations.pl: http://jrf.cocolog-nifty.com/archive/perl/combinations.pl
combinations-20180411.pl: http://jrf.cocolog-nifty.com/archive/perl/combinations-20180411.pl
combinations-20180420.pl: http://jrf.cocolog-nifty.com/archive/perl/combinations-20180420.pl