PHP の置換および組み合わせアルゴリズム

私はずっとアルゴリズムに興味がありました。昨年の初めに iOS でトレーニングしていたとき、先生はクラスで誰が自分のアイデアを最初に表現できるかを順位付けする質問をしましたが、それを実装するためにすぐにコーディングする必要はありませんでした。その時、北京理工大学の1年生が、私が実現可能な方法を見つけたとすぐに言い、先生はそれは簡単そうに思えましたが、私が想像していたほど理解するのは簡単ではありませんでした。いろいろなことを詳しく考えてみましょう。

実際、私は学生時代に、福祉宝くじ 3D とスポーツ宝くじナンバー 3 をしばらくプレイして、コンピューターで当選番号を選別しようと試みていました。幸いなことに、私は経済的余裕がなく、生活費も限られていたため、時間内にこの引き返せない道から抜け出すことができました。

最近のモバイルゲームのプロジェクトでは、順列と組み合わせのアルゴリズムが必要であると記載されていましたが、私は今クライアントに取り組んでいますが、まだPHPに比較的慣れているので、自分で練習して書いてみると、予想外にうまくいきました。 PHP の配列関数は非常に便利で、数行で実行できます。その欠点についてアドバイスをいただければ幸いです。

<?php

// 阶乘
function factorial($n) {
	return array_product(range(1, $n));
}

// 排列数
function A($n, $m) {
	return factorial($n)/factorial($n-$m);
}

// 组合数
function C($n, $m) {
	return A($n, $m)/factorial($m);
}

// 排列
function arrangement($a, $m) {
	$r = array();

	$n = count($a);
	if ($m <= 0 || $m > $n) {
		return $r;
	}

	for ($i=0; $i<$n; $i++) {
		$b = $a;
		$t = array_splice($b, $i, 1);
		if ($m == 1) {
			$r[] = $t;
		} else {
			$c = arrangement($b, $m-1);
			foreach ($c as $v) {
				$r[] = array_merge($t, $v);
			}
		}
	}

	return $r;
}

// 组合
function combination($a, $m) {
	$r = array();

	$n = count($a);
	if ($m <= 0 || $m > $n) {
		return $r;
	}

	for ($i=0; $i<$n; $i++) {
		$t = array($a[$i]);
		if ($m == 1) {
			$r[] = $t;
		} else {
			$b = array_slice($a, $i+1);
			$c = combination($b, $m-1);
			foreach ($c as $v) {
				$r[] = array_merge($t, $v);
			}
		}
	}

	return $r;
}


// ====== 测试 ======
$a = array("A", "B", "C", "D");

$r = arrangement($a, 2);
var_dump($r);

$r = A(4, 2);
echo $r."\n";

$r = combination($a, 2);
var_dump($r);

$r = C(4, 2);
echo $r."\n";

さらに、私が数年前に PHP をトレーニングしていたときに、ループ行列アルゴリズムも作成しました。ここでは外部リンクを使用することはできません。興味のある学生は、Sina からのアルゴリズムに関する筆記試験の質問を参照してください。 2番目の記事は、皆さんが学び、交流できるようにするための私のオリジナルバージョンです。

上記では、PHP の順列と組み合わせのアルゴリズムをその側面も含めて紹介しましたが、PHP チュートリアルに興味のある友人に役立つことを願っています。