Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
Help us understand the problem. What is going on with this article?

重複順列を全て列挙する

More than 5 years have passed since last update.

例えば、A, B, C, D, Eからなる10文字を並べる。並べる10文字の中には同じ文字が重複してもよい。このとき、全ての重複順列を列挙するプログラムの例。
他にも効率的なやり方はあるけど, まずは実装がしやすい方法を。

考え方

A, B, C, D, Eをそれぞれ文字0, 1, 2, 3, 4に1対1に対応付ける. こうすると, 求めたい重複順列の1つは各桁が0〜4であるような10桁の整数に対応付けることができる(10桁に満たない場合10桁になるように前0で埋める).
各桁が0〜4なのでこれは5進数の10桁の整数のことである. 10桁の5進数の最小値・最大値はそれぞれ10進数で0, 5^10 - 1なので0から5^10 - 1までのループを行うことで全てが漏れなく得られる. あとは各ループのインデックスを5進数に変換し, 0, 1, 2, 3, 4をそれぞれA, B, C, D, Eに置き換えることで元のA, B, C, D, Eからなる10文字が得られる.

進数の変換

言語によっては自分で変換するためのコードを書いたりする必要がある.
しかしPHPでは便利なことにn進数からm進数への変換のための関数がデフォルトで用意されている.
base_convert ($number, $n, $m)を使うことで可能である.
またJavaScriptではNumber.toString(5)などとすれば5進数への変換が行える.

他の言語でも2進数や16進数など比較的よく使われる進数変換に関してはライブラリが存在するものも多い. ライブラリが存在しない場合, 自分で実装する必要があるが, 10進数からの変換で, 整数から整数への変換に限定さえすれば, そんなに難しいことはない.

最後にサンプル

<?php
// 0埋めするための関数
function padZero($str, $length) {
    if (strlen($str) == $length) {
        return $str;
    }
    return padZero("0".$str, $length);
}

// マッピング
$replace_from   = array("0", "1", "2", "3", "4");
$replace_to     = array("A", "B", "C", "D", "E");

for ($i=0, $length=pow(5, 10); $i<$length; $i++) {
    $str = padZero(base_convert($i, 10, 5), 10);
    echo str_replace($replace_from, $replace_to, $str)."\n";
}
?>
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away