c++ - 我如何获得 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++ 库或拼出一种快速且内存高效的算法吗？

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

(不，我不只是想要密码的答案。)

Answer 1

我用过 this以前的库(注意它是 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));