如何获得xPy的所有排列？

我想计算一组大小为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

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

std::vector v; v.push_back(1); v.push_back(2); v.push_back(3); std::vector::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()重复next_permutation()会给你(true, false, true)然后(true, true, false) 。

由于您希望排列不是组合，因此将每个组合映射到实际元素集（例如(true, false, true)变为（1,3）），然后再次使用next_permutation()生成这些组合的所有排列。

Answer 3

我没有得到你关于密码的问题。 但是如果你想在你的字典中找到这个单词的最长排列（anagram），你可以试试他的方式。

1. 创建你的单词的位掩码。 你可以使用64位算术，这样你就可以在里面装上近3个alpahbets。

a->第一位，b->第二位，依此类推。 如果你在“ouglg 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 

编辑：普遍的soluton不适合24P7。