计算置换的阶乘秩(N选择K) [英] Computing the Factoradic Rank of a Permutation (N choose K)
问题描述
我最近了解了 CNS 和 @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
我使用上面链接的Wikipedia文章和此MSDN文章,我知道他们都不打算考虑k个大小的子集,但是我完全不知道这种逻辑的样子……
我还尝试了谷歌搜索并搜索现有的问题/答案,但是还没有找到任何相关内容.
睡了一觉,并在Pen&纸,我想通了.如果有人感兴趣:
例如,第42个 5选择3 的排列是 这对于计算阶乘( 仍然, 所以4-2-5
,但是如果您查看Pr_Unrank()
,其中4-2-5[-1-3]
,最后两个元素被丢弃,因此最终只能使用k
元素.>
3-1-2[-0-0]
)的小数表示非常重要:
4-2-5
= (2! * 3) + (1! * 1) + (0! * 2)
= 9
4-2-5-1-3
= (4! * 3) + (3! * 1) + (2! * 2) + (1! * 0) + (0! * 0)
= 82
82
不是正确的答案.要获得它,我们必须将其除以以下结果:
Pr(5, 5) / Pr(5, 3)
(=)(5 - 3)!
= 120 / 60
= 2
82 / 2
是41
,我要做的就是添加1
以使排名从1开始.
Array // 5 choose 3 permutations
(
[1] => 1-2-3
[2] => 1-2-4
[3] => 1-2-5
[4] => 1-3-2
[5] => 1-3-4
[6] => 1-3-5
[7] => 1-4-2
[8] => 1-4-3
[9] => 1-4-5
[10] => 1-5-2
[11] => 1-5-3
[12] => 1-5-4
[13] => 2-1-3
[14] => 2-1-4
[15] => 2-1-5
[16] => 2-3-1
[17] => 2-3-4
[18] => 2-3-5
[19] => 2-4-1
[20] => 2-4-3
[21] => 2-4-5
[22] => 2-5-1
[23] => 2-5-3
[24] => 2-5-4
[25] => 3-1-2
[26] => 3-1-4
[27] => 3-1-5
[28] => 3-2-1
[29] => 3-2-4
[30] => 3-2-5
[31] => 3-4-1
[32] => 3-4-2
[33] => 3-4-5
[34] => 3-5-1
[35] => 3-5-2
[36] => 3-5-4
[37] => 4-1-2
[38] => 4-1-3
[39] => 4-1-5
[40] => 4-2-1
[41] => 4-2-3
[42] => 4-2-5
[43] => 4-3-1
[44] => 4-3-2
[45] => 4-3-5
[46] => 4-5-1
[47] => 4-5-2
[48] => 4-5-3
[49] => 5-1-2
[50] => 5-1-3
[51] => 5-1-4
[52] => 5-2-1
[53] => 5-2-3
[54] => 5-2-4
[55] => 5-3-1
[56] => 5-3-2
[57] => 5-3-4
[58] => 5-4-1
[59] => 5-4-2
[60] => 5-4-3
)
I've recently learnt about CNS and FNS, and since they look so elegant to me, I decided to try and implement methods to generate combinations and permutations using those techniques. I finished my method to convert from n choose k combinations to a CSN rank and vice-versa but I'm banging my head against the wall trying to do the same with n choose k (unique) permutations.
Thanks to @Joshua I got the unranking (FNS to permutation) method working:
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;
}
This is my current attempt at a ranking (permutation to FNS) method:
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;
}
And these are the helper functions I'm using:
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));
}
The problem is, the Pr_Rank()
method only returns the correct rank when n = k
(demo):
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
I guided myself using the Wikipedia article I linked above and this MSDN article, I know neither of them contemplate k-sized subsets, but I'm completely in the dark what such logic would look like...
I also tried Googling and searching existing questions / answers but nothing relevant has come up yet.
After a good night sleep and a little help from pen & paper, I figured it out. In case anyone is interested:
For instance, the 42nd 5 choose 3 permutation is 4-2-5
, but if you look at Pr_Unrank()
, where array_slice()
is called, you'll notice that the actual permutation (in lexicographic order) is actually 4-2-5[-1-3]
, the last two elements are discarded so that you only end up with k
elements.
This is very important to compute the decimal representation of the factoriadic (3-1-2[-0-0]
):
4-2-5
=(2! * 3) + (1! * 1) + (0! * 2)
=9
4-2-5-1-3
=(4! * 3) + (3! * 1) + (2! * 2) + (1! * 0) + (0! * 0)
=82
Still, 82
is not the right answer. To get it, we must divide it by the result of:
Pr(5, 5) / Pr(5, 3)
(=)(5 - 3)!
=120 / 60
=2
So 82 / 2
is 41
, all that I need to do is add 1
to get the ranking starting at 1.
Array // 5 choose 3 permutations
(
[1] => 1-2-3
[2] => 1-2-4
[3] => 1-2-5
[4] => 1-3-2
[5] => 1-3-4
[6] => 1-3-5
[7] => 1-4-2
[8] => 1-4-3
[9] => 1-4-5
[10] => 1-5-2
[11] => 1-5-3
[12] => 1-5-4
[13] => 2-1-3
[14] => 2-1-4
[15] => 2-1-5
[16] => 2-3-1
[17] => 2-3-4
[18] => 2-3-5
[19] => 2-4-1
[20] => 2-4-3
[21] => 2-4-5
[22] => 2-5-1
[23] => 2-5-3
[24] => 2-5-4
[25] => 3-1-2
[26] => 3-1-4
[27] => 3-1-5
[28] => 3-2-1
[29] => 3-2-4
[30] => 3-2-5
[31] => 3-4-1
[32] => 3-4-2
[33] => 3-4-5
[34] => 3-5-1
[35] => 3-5-2
[36] => 3-5-4
[37] => 4-1-2
[38] => 4-1-3
[39] => 4-1-5
[40] => 4-2-1
[41] => 4-2-3
[42] => 4-2-5
[43] => 4-3-1
[44] => 4-3-2
[45] => 4-3-5
[46] => 4-5-1
[47] => 4-5-2
[48] => 4-5-3
[49] => 5-1-2
[50] => 5-1-3
[51] => 5-1-4
[52] => 5-2-1
[53] => 5-2-3
[54] => 5-2-4
[55] => 5-3-1
[56] => 5-3-2
[57] => 5-3-4
[58] => 5-4-1
[59] => 5-4-2
[60] => 5-4-3
)
这篇关于计算置换的阶乘秩(N选择K)的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!