我最近了解了 CNS 和 FNS,因为它们看起来很优雅,所以我决定尝试使用这些技术实现生成组合和排列的方法。我完成了将 n 选 k 组合转换为 CSN 排名和反向转换的方法,但我正在努力实现相同的操作,只是针对 n 选 k(唯一)排列。
感谢 @Joshua,我成功实现了 未排序(FNS 到排列)方法:
这是我目前尝试的一种排名(FNS置换)方法:
问题在于,
我使用上面链接的维基百科文章和this MSDN article自学,但它们都没有涉及到k大小的子集,所以我不知道这样的逻辑是什么样子的... 我也尝试过谷歌搜索和查找现有的问题/答案,但还没有找到相关的内容。
感谢 @Joshua,我成功实现了 未排序(FNS 到排列)方法:
function Pr_Unrank($n, $k, $rank) { // rank starts at 1
if ($n >= $k) {
if (($rank > 0) && ($rank <= Pr($n, $k))) {
$rank--;
$result = array();
$factoriadic = array();
for ($i = 1; $i <= ($n - $k); ++$i) {
$rank *= $i;
}
for ($j = 1; $j <= $n; ++$j) {
$factoriadic[$n - $j] = ($rank % $j) + 1; $rank /= $j;
}
for ($i = $n - 1; $i >= 0; --$i) {
$result[$i] = $factoriadic[$i];
for ($j = $i + 1; $j < $n; ++$j) {
if ($result[$j] >= $result[$i]) {
++$result[$j];
}
}
}
return array_reverse(array_slice($result, 0 - $k));
}
}
return false;
}
这是我目前尝试的一种排名(FNS置换)方法:
function Pr_Rank($n, $k, $permutation) {
if ($n >= $k) {
$result = range(1, $n);
$factoriadic = array();
foreach ($permutation as $key => $value) {
$factoriadic[$k - $key - 1] = array_search($value, $result);
array_splice($result, $factoriadic[$k - $key - 1], 1);
}
$result = 1;
foreach (array_filter($factoriadic) as $key => $value) {
$result += F($key) * $value;
}
return $result;
}
return false;
}
这些是我正在使用的辅助函数:
function F($n) { // Factorial
return array_product(range($n, 1));
}
function Pr($n, $k) { // Permutations (without Repetitions)
return array_product(range($n - $k + 1, $n));
}
问题在于,
Pr_Rank()
方法仅在n=k
时返回正确的排名(演示):var_dump(Pr_Rank(5, 2, Pr_Unrank(5, 2, 10))); // 3, should be 10
var_dump(Pr_Rank(5, 3, Pr_Unrank(5, 3, 10))); // 4, should be 10
var_dump(Pr_Rank(5, 5, Pr_Unrank(5, 5, 10))); // 10, it's correct
我使用上面链接的维基百科文章和this MSDN article自学,但它们都没有涉及到k大小的子集,所以我不知道这样的逻辑是什么样子的... 我也尝试过谷歌搜索和查找现有的问题/答案,但还没有找到相关的内容。