SOFTELメモ Developer's blog

会社概要 ブログ 調査依頼 社員募集 ...

【php】n個の文字からどれを何回使ってもよいので長さrの文字列を作る(重複順列)

問題

a,b,c,d,e,fの文字を使って作れる6文字の文字列をすべて書き出せ。

(重複順列: 異なるn個のものから重複を許してr個とる順列の数は?)

解答例

/**
 * 組み合わせ作成関数
 *
 * @param $a 使用する文字の配列
 * @param $l 作成する文字の長さ
 * @return 文字の組み合わせ結果の配列
 */
function pat($a, $l)
{
  $x = array('');
  for ($i = 0; $i < $l; ++$i) {
    $_x = array();
    foreach ($a as $ak => $av) {
      foreach ($x as $xk => $xv) {
        $xv .= $av;
        $_x[] = $xv;
      }
    }
    $x = $_x;
  }
  return $x;
}

$a = array('a','b','c','d','e','f');
$l = 6;
var_export(pat($a, $l));

$aが空の配列だったり、$lが長さ0だったりしたときはどうするのがいいでしょうね。

実行結果

array (
  0 => 'aaaaaa',
  1 => 'baaaaa',
  2 => 'caaaaa',
  3 => 'daaaaa',
  4 => 'eaaaaa',
  5 => 'faaaaa',
  6 => 'abaaaa',
  7 => 'bbaaaa',
  8 => 'cbaaaa',
  9 => 'dbaaaa',
  10 => 'ebaaaa',
  11 => 'fbaaaa',
  12 => 'acaaaa',
  13 => 'bcaaaa',
  14 => 'ccaaaa',
  15 => 'dcaaaa',
  16 => 'ecaaaa',
  17 => 'fcaaaa',
  18 => 'adaaaa',
  19 => 'bdaaaa',
  20 => 'cdaaaa',
  21 => 'ddaaaa',
  22 => 'edaaaa',
  23 => 'fdaaaa',
  24 => 'aeaaaa',
  25 => 'beaaaa',
  26 => 'ceaaaa',
  27 => 'deaaaa',
  28 => 'eeaaaa',
  29 => 'feaaaa',
  30 => 'afaaaa',
  31 => 'bfaaaa',
  32 => 'cfaaaa',
  33 => 'dfaaaa',
  34 => 'efaaaa',
  35 => 'ffaaaa',
  36 => 'aabaaa',
  37 => 'babaaa',
  38 => 'cabaaa',
  39 => 'dabaaa',
  40 => 'eabaaa',
  41 => 'fabaaa',
  42 => 'abbaaa',
  43 => 'bbbaaa',
  44 => 'cbbaaa',
  45 => 'dbbaaa',
  46 => 'ebbaaa',
  47 => 'fbbaaa',
  48 => 'acbaaa',
  49 => 'bcbaaa',
  50 => 'ccbaaa',
  51 => 'dcbaaa',
  52 => 'ecbaaa',
  53 => 'fcbaaa',
  54 => 'adbaaa',
  55 => 'bdbaaa',
  56 => 'cdbaaa',
  57 => 'ddbaaa',
  58 => 'edbaaa',
  59 => 'fdbaaa',
  60 => 'aebaaa',
  61 => 'bebaaa',
  62 => 'cebaaa',
  63 => 'debaaa',
  64 => 'eebaaa',
  65 => 'febaaa',
  66 => 'afbaaa',
  67 => 'bfbaaa',
  68 => 'cfbaaa',
  69 => 'dfbaaa',
  70 => 'efbaaa',
  71 => 'ffbaaa',
  72 => 'aacaaa',
  73 => 'bacaaa',
  74 => 'cacaaa',
  75 => 'dacaaa',
  76 => 'eacaaa',
  77 => 'facaaa',
  78 => 'abcaaa',
  79 => 'bbcaaa',
  80 => 'cbcaaa',
  81 => 'dbcaaa',
  82 => 'ebcaaa',
  83 => 'fbcaaa',
  84 => 'accaaa',
  85 => 'bccaaa',
  86 => 'cccaaa',
  87 => 'dccaaa',
  88 => 'eccaaa',
  89 => 'fccaaa',
  90 => 'adcaaa',
  91 => 'bdcaaa',
  92 => 'cdcaaa',
  93 => 'ddcaaa',
  94 => 'edcaaa',
  95 => 'fdcaaa',
  96 => 'aecaaa',

~ (重いので)中略 ~

  46643 => 'fdffff',
  46644 => 'aeffff',
  46645 => 'beffff',
  46646 => 'ceffff',
  46647 => 'deffff',
  46648 => 'eeffff',
  46649 => 'feffff',
  46650 => 'afffff',
  46651 => 'bfffff',
  46652 => 'cfffff',
  46653 => 'dfffff',
  46654 => 'efffff',
  46655 => 'ffffff',
)

添字が46655番 = 全部で46656個 = 6の6乗個。

関連するメモ

コメント