PHP 完全置換アルゴリズム実装プログラムコード_PHP チュートリアル-PHPチュートリアル-php.cn

PHP 完全置換アルゴリズム実装プログラムコード_PHP チュートリアル

WBOY

リリース： 2016-07-13 10:09:52

オリジナル

1130 人が閲覧しました

PHP 完全置換アルゴリズム実装プログラムコード

n 個の異なる要素から m (m≤n) 個の要素を選択し、それらを特定の順序で配置します。これを、n 個の異なる要素からの m 要素の配置と呼びます。 m=n の場合、すべての順列は完全順列と呼ばれます。

はじめに

例えば、3つの要素1、2、3の合計配置は次のようになります。

1、2、3

1,3,2

2,1,3

2,3,1

3,1,2

3,2,1

合計3*2*1=6種類3!

2式

完全な順列数 f(n)=n!(定義 0!=1)

再帰的アルゴリズム

1、2、3

1,3,2

2,1,3

2,3,1

3,2,1

3,1,2

これは、アルゴリズムが完全な順列を出力する方法のみを考慮し、転置に問題があるかどうかを考慮していないためです。そこで、転置関数を変更するという解決策を思いつきました

例えば、1 2 3を転置する場合、直接3 2 1にするのではなく、3と1を直接転置するのではなく、3を前後に配置し、1 2を順番に後ろに配置する必要があります。

基本的なアルゴリズム

以下に 4 種類の全置換アルゴリズムを紹介します。

(A)辞書順

(B)キャリー数増加法

(C)キャリー数減少法

(D)オルソスワップ法

完全な置換アルゴリズムの実装

コードは次のとおりです

header("content-type:text/html;charset=utf-8");/**
* @param array $a 動的に変化する配置する要素のコレクション
* @param array $b には現在の配置が保存されます
* @param array $M 配置される要素のセット、定数と同等、常に配置される要素の初期セット
*/
関数整範囲($a,$b,$M){
$range=array();
if(count($a) > 1){
$d=$b;
foreach($a として $value){
$b[]=$value;
$c=array_diff($M,$b);
if(カウント($c) > 0){
$range[]=wholerange($c,$b,$M);
}
$b=$d;
}
}elseif(count($a) == 1){
foreach($a として $value){
$b[]=$value;
}
$onerange="";
foreach($b として $value){
$onerange.=$value;
}
$range[]=$onerange;
}
$range を返します;
}
/**
* 再帰的な出力配列
*
* @param array $arr 出力する配列
* @return int 配列要素の数を返します。*/
関数再帰配列($arr){
$i=0;
foreach($arr as $value){
if(is_array($value)){
$i+=recursionarray($value);
}その他{
echo $value."
";
$i++;
}
}
$i を返します;
}
$a=array('A','B','C','D');
$b=配列();
$range=wholerange($a,$b,$a);
$count=recursionarray($range);
echo "合計 ".$count." の配置";
?>