如何获得 xPy 的所有排列？

Question

我想计算一组大小 X 的大小 Y 的所有排列。也就是说，如果我有 (1,2,3) 并且想要大小 2, 3P2 的所有排列，则它将是 (1,2) ( 1,3) (2,1) (2,3) (3,1) (3,2)。

GSL和C++ STL都只提供我能看到的xPx。有人能给我指出一个可以做到这一点的 C/C++ 库，或者阐明一个快速且内存高效的算法吗？

我正在尝试解决一个非常短的密码。我已经弄清楚了两封信，并决定进行暴力攻击。我有“oulgg ouyakl”，并且正在根据一本非常好的字典检查每个排列。我已经消除了 2 个字母，所以它是 24P7 或 1,744,364,160 种可能性，这还不错。我现在正在运行一个 Perl 程序，因此这将是对编程时间 + 运行时间的总效率的有趣测试。 :)

（不，我不只是想要密码的答案。）

Answer 1

我之前在代码中使用过 这个 库（注意它是 C++）需要做类似的事情。它有排列和组合，有重复和没有重复。对于您的问题，这应该足够了（未经测试......）：

std::vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);

std::vector<int>::iterator first = v.begin(), middle = v.begin() + 2, last = v.end();

do {
    // do stuff with elements in range first...middle (but dont change them)
} while(next_partial_permutation(first, middle, last));

Answer 2

您可以通过在标志的 vector 上使用 std::next_permutation() 来获取组合。以从 (1,2,3) 中选取 2 个元素的示例为例，将向量启动为 (false, true, true)。在此重复 next_permutation() 将会得到 (true, false, true) 然后是 (true, true, false)，然后再重新开始。

由于您想要排列而不是组合，请将每个组合映射到实际元素集（例如 (true, false, true) 变为 (1, 3)），然后使用 next_permutation()。

Answer 3

我不太明白你关于密码的问题。但如果你想在你的字典中找到这个单词的最长排列（字谜），你可以尝试他的方法。

1. 创建您的单词的位掩码。您或许可以使用 64 位算术，这样您就可以在里面容纳几乎 3 个字母表。

一个->第一位，b->第二位等等。
如果你的“oulgg ouyakl”案例中有这个词，这意味着

 abcdefghijklmnopqrstuvxyzabcdefghijklmnopqrstuvxyzabcdefghijklmnop
 100000100011001000001001000000010000100100000100000000000000000000

（希望我没有错过任何东西）
现在您可以为您的词汇表创建相同的位掩码。

当您检查词汇量时，您只需要做的是，

 vocabulary & ( ouglg_ouyakl ^ vocabulary)

如果您的词汇量单词来自 ouglg_ouyakl，则此结果为 0。

关于排列编辑

for each permutation of numbers fom  1-n // that is 1,2 and 2,1
  for(i=0;i<end;i++)
    for(j=i+1;j<end;j++)
      SET[permutation[i]],SET[permutation[j]]

：先前的解决方案不适合 24P7。