PHPで順列を取得する

順列

配列で与えられた異なる n個 の要素の中から，異なる r個 を取り出して1列に並べる順列をすべて取得します。

PHPで実装

permutation.php

/**
 * Permutation 順列 nPr (r ≦ n)
 *
 * @param array $arr 並べる元となる配列
 * @param int $r 並べる1列（1セット）あたりの要素数
 * @return null|array
 */
function permutation(array $arr, int $r): ?array
{
    // 重複した値を削除して，数値添字配列にする
    $arr = array_values(array_unique($arr));

    $n = count($arr);
    $result = []; // 最終的に二次元配列にして返す

    // nPr の条件に一致していなければ null を返す
    if($n < 1 || $n < $r){ return null; }

    if($r === 1){
        foreach($arr as $item){
            $result[] = [$item];
        }
    }

    if($r > 1){
        // $item が先頭になる順列を算出する
        foreach($arr as $key => $item){
            // $item を除いた配列を作成
            $newArr = array_filter($arr, function($k) use($key) {
                return $k !== $key;
            }, ARRAY_FILTER_USE_KEY);
            // 再帰処理 二次元配列が返ってくる
            $recursion = permutation($newArr, $r - 1);
            foreach($recursion as $one_set){
                array_unshift($one_set, $item);
                $result[] = $one_set;
            }
        }
    }

    return $result;
}

使い方

// 4 P 2 = 12
$arr = ['A', 'B', 'C', 'D'];
print_r(permutation($arr, 2));

結果

Array
(
    [0] => Array
        (
            [0] => A
            [1] => B
        )

    [1] => Array
        (
            [0] => A
            [1] => C
        )

    [2] => Array
        (
            [0] => A
            [1] => D
        )

    [3] => Array
        (
            [0] => B
            [1] => A
        )

    [4] => Array
        (
            [0] => B
            [1] => C
        )

    [5] => Array
        (
            [0] => B
            [1] => D
        )

    [6] => Array
        (
            [0] => C
            [1] => A
        )

    [7] => Array
        (
            [0] => C
            [1] => B
        )

    [8] => Array
        (
            [0] => C
            [1] => D
        )

    [9] => Array
        (
            [0] => D
            [1] => A
        )

    [10] => Array
        (
            [0] => D
            [1] => B
        )

    [11] => Array
        (
            [0] => D
            [1] => C
        )

)

解説

PHPで組み合わせ(コンビネーション)を取得するで解説したロジックとほとんど同じです。こちらの記事では順列の意味と総数の計算方法についても解説しています。

配列をループして，その要素が先頭にくるパターンを算出していきます。（組み合わせの場合，先頭でなければいけない理由はないです。）

組み合わせは，ループの要素を「必ず含む要素」として，そのパターンをすべて算出します。ですから既にループした要素を全て除いた配列を再帰処理の対象としました。

順列は，ループの要素を「先頭の要素」として，その要素のみを除いた配列を再帰処理の対象とします。

順列は [A, B] と [B, A] を区別しますが，組み合わせは区別しません。

JavaScriptでも実装してみる

permutation.js

/**
 * 順列
 * 
 * @param {Array} array 
 * @param {Number} r
 */
const permutation = (array, r) => {

    const arr = uniq(array);
    const result = [];
    const n = arr.length;

    if(n < 1 || n < r){ return; }

    if(r === 1){
        arr.forEach(item => result.push([item]));
    }

    if(r > 0){
        arr.forEach(item => {
            const newArr = arr.filter(el => el !== item);
            const recursion = permutation(newArr, r - 1);
            recursion.forEach(one_set => result.push([item].concat(one_set)));      
        });
    }

    return result;

};


/**
 * 配列の重複を削除
 * 
 * @param {Array} array 
 * 
 */
const uniq = (array) => {
  if(! Array.isArray(array)){
      return;
  }
  return [...new Set(array)];
};

const array = ['A', 'B', 'C', 'D'];
console.log(permutation(array, 2));