PHP 순열 및 조합 알고리즘

저는 예전부터 알고리즘에 관심이 많았어요. 작년 초에 iOS 교육을 할 때 선생님이 수업 시간에 누가 먼저 아이디어를 표현할 수 있는지 순위 질문을 주셨는데, 당장 코딩을 할 필요는 없었어요. 당시 북경과기대 신입생이 재빠르게 가능한 방법을 제시하고 선생님께서 승인해 주셨는데, 말은 간단하지만 생각보다 이해하기 쉽지는 않았습니다. 세부적인 것.

사실 저는 대학시절부터 로또번호를 C로 써보려고 했어요. 그 당시에는 한동안 복지복권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의 알고리즘에 대한 서면 테스트 문제", 두 번째 항목은 모두가 배우고 소통할 수 있는 저의 원본 버전입니다.

위에서는 PHP 순열 및 조합 알고리즘을 소개했으며, PHP 튜토리얼에 관심이 있는 친구들에게 도움이 되기를 바랍니다.