« Tweet Sig: ウェブ上の三文判? | トップページ | Exhaustive Lock Dependency Emulator その3 修正とチェック »

2018年4月11日 (水)

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

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 とかちょっとシンタックスシュガーをまぶしたソースも公開しておく。

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

2018-04-11 21:48:01 (JST) in Perl | | コメント (3) | トラックバック (0)

Perl」カテゴリ内の最近の記事

批評や挨拶のためのネットコミュニティ

  • はてなブックマーク(って何?) このエントリーをはてなブックマークに追加 このエントリーを含むはてなブックマーク このエントリーを含むはてなブックマーク
  • Twitter (って何?)

トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/93568/66600279

トラックバックのポリシー

他サイトなどからこの記事に自薦された関連記事(トラックバック)はまだありません。
» JRF のソフトウェア Tips:組み合わせと順列の数え上げのアルゴリズム (この記事)

コメント

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

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

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

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

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

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

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

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

コメントを書く



(メールアドレス形式)


※匿名投稿を許可しています。ゆるめのコメント管理のポリシーを持っています。この記事にまったく関係のないコメントはこのリンク先で受け付けています。
※暗号化パスワードを設定すれば、後に「削除」、すなわち JavaScript で非表示に設定できます。暗号解読者を気にしないならメールアドレスでもかまいません。この設定は平文のメールで管理者に届きます。
※コメントを書くために<b>ボールド</b>、<pre>詩文やソースコード</pre>、<a href="">リンク</a>、その他のHTMLタグが使えます。また、漢字[かんじ]でルビが、[google: キーワード] で検索指定が使えます。


ランダムことわざ: 温故知新。