php - 字典顺序 nk 中的下一个排列
问题描述
我想编写按字典顺序返回下一个排列 n 选择 k 的函数。
到目前为止,我发现了以下算法
class Permutation
{
public function swap(& $a, $first, $second)
{
$tmp = $a[$first];
$a[$first] = $a[$second];
$a[$second] = $tmp;
}
function nextPermutation(& $a, $n, $k)
{
do {
$first = $n - 2;
while ($first != -1 && $a[$first] >= $a[$first + 1]) $first--;
if ($first == -1)
return false;
$second = $n - 1;
while ($a[$first] >= $a[$second]) $second--;
$this->swap($a, $first, $second);
$left = $first + 1;
$right = $n - 1;
while ($left < $right) {
$this->swap($a, $left++, $right--);
}
} while ($first > $k - 1);
return true;
}
public function run()
{
$n=10;
$k=4;
$a = array_merge(range(ord(0), ord(9)), range(ord('A'), ord('Z')), range(ord('a'), ord('z')));
$i = 0;
while ($this->nextPermutation($a, $n, $k)) {
$i++;
echo($i . ") ");
for ($j = 0; $j < $k; $j++) {
echo $a[$j] . " ";
}
echo("\n");
}
}
}
但它只能在 n 到 13 的情况下工作,然后变得越来越慢。我需要使它适用于 n=62 和 k=6。有可能做到吗?
解决方案
这个组合对象在英语组合学中没有特定名称,在俄语和法语组合学术语中它被称为“安排”A(n,k)
有 44 261 653 680 个排列A(62,6)
- 所以它们的生成和输出(~500 GB)需要很长时间。在像 C/C++/Delphi 这样的编译语言中生成(没有输出)可能需要大约几个小时(粗略估计每秒 10^6-10^7 个结果),但这个过程在 PHP(解释语言)中应该更慢。
您的代码使用通常排列的算法来生成n!
针对所需n!/(n-k)!
排列的结果。
用于生成安排的简单递归 Python 代码。n=25,k=5 时工作约 3 秒。不是最佳的,将在书中更好地检查。
n = 4
k = 2
ar = [0] * k
used = set()
def genArr(idx):
for i in range(n):
if not i in used:
used.add(i)
ar[idx] = i
if idx == k - 1:
print(ar) #comment for large n
else:
genArr(idx + 1)
used.remove(i)
genArr(0)
print('OK')
[0, 1, 2]
[0, 1, 3]
[0, 2, 1]
[0, 2, 3]
......
[2, 3, 1]
[3, 0, 1]
[3, 0, 2]
[3, 1, 0]
[3, 1, 2]
[3, 2, 0]
[3, 2, 1]
推荐阅读
- php - Symfony 表单将用户兴趣的选择存储到 UserInterests
- python - 在 python scapy 中解码 MX 记录的 DNS 应答 rrdata
- php - strpos 不适用于逗号分隔字符串中的第一个字符串
- javascript - 如何修复:在线共享点保存当前用户和状态的过滤查找
- python - Tornado-swirl 没有获取 URL 中的参数
- python - 如何获取导入某个包的python文件的路径?
- relational-database - 我不明白这个问题的答案与自然连接和投影
- javascript - 在 puppeteer/JavaScript 中重试 page.goto、page.waitForNavigation 等的最佳实践
- ruby-on-rails-5 - Rails 中的 Guard 子句,除非
- c++ - 从函数调用传递值时,std::tie 因“无法绑定非常量左值引用”而失败