如何得到xPy的所有排列?

I'd like to calculate all the permutations of size Y of a set of size X. That is if I had (1,2,3) and want all permutations of size 2, 3P2, it would be (1,2) (1,3) (2,1) (2,3) (3,1) (3,2).

我想计算一组x大小的Y的所有排列，也就是如果我有(1,2,3)并且想要所有大小为2,3p2的排列，它将是(1,2)(1,3)(2,3)(3,1)(3,1)(3,2)(3,2)

Both the GSL and C++ STL only provide xPx that I can see. Could someone point me at a C/C++ library which can do this or spell out a fast and memory efficient algorithm?

GSL和c++ STL都只提供我能看到的xPx。有人能给我指出一个C/ c++库，它可以做到这一点吗?

I'm trying to solve a very short cryptogram. I've figured out two letters and have decided to do an brute force attack. I have "ouglg ouyakl" and am checking every permutation against a very good dictionary. I've eliminated 2 letters so its 24P7 or 1,744,364,160 possibilities which isn't so bad. I have a Perl program running now, so this will be an interesting test of the total efficiency of programming time + run time. :)

我在尝试解一个很短的密码。我算出了两个字母，决定用蛮力攻击。我有"ouglg ouyakl"，我正在用一本很好的字典检查每一个排列。我去掉了两个字母，所以它有24P7或174364,160种可能性，这不算太糟。我现在正在运行一个Perl程序，因此这将是一个关于编程时间+运行时间总效率的有趣测试。:)

(No, I do not just want the answer to the cryptogram.)

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

3 个解决方案

#1

I've used this library before (note it is C++) in code that needed to do something similar. It has permutations and combinations, with and without repetition. For your problem, this should suffice (untested...):

我以前在代码中使用过这个库(注意它是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));

#2

You can get the combinations by using std::next_permutation() on a vector<bool> of flags. Taking your example of picking 2 elements from (1,2,3), start your vector as (false, true, true). Repeating next_permutation() on this will give you (true, false, true) then (true, true, false), before starting over.

您可以通过在标志的向量上使用std::next_permutation()来获得组合。以从(1,2,3)中选取2个元素为例，开始你的向量(false, true, true)。在这里重复next_permutation()将在重新开始之前给您(true、false、true)然后(true、true、false)。

Since you want permutations not combinations, map each combination to the set of actual elements (e.g. (true, false, true) becomes (1, 3)) and then generate all the permutations of these using next_permutation() again.

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

#3

I do not exacly get your question about cryptogram. But if you want to find longest permutation (anagram) of this words in your dictionary you can try his way.

我不太明白你关于密码的问题。但是如果你想在字典里找到最长的排列(字词)，你可以试试他的方法。

create bitmask of your word. You can probably use 64 bit arithmetics so you can fit almost 3 alpahbets inside.
创建你的单词的位掩码。你可以使用64位的算术，这样你就可以在里面放上几乎3个alpahbets。

a-> first bit, b-> second bit and so on. If you have word in your "ouglg ouyakl" case this mean

a->第一比特，b->第二比特等等。如果你在"ouglg ouyakl"这个词中有这个意思

 abcdefghijklmnopqrstuvxyzabcdefghijklmnopqrstuvxyzabcdefghijklmnop
 100000100011001000001001000000010000100100000100000000000000000000

(hope i did not missed something) Now you create same bitmasks for your vocabulary.

(希望我没有漏掉什么)现在您为您的词汇表创建了相同的位掩码。

And when you chek against vocabulary you just have to do is

当你违背词汇时，你只需要做的就是

 vocabulary & ( ouglg_ouyakl ^ vocabulary)

and this trows 0 if your vocabulary word is from ouglg_ouyakl.

如果你的词汇来自ouglg_ouyakl，那么这个trows 0。

About permutations

对排列

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]]

EDIT: prevous soluton was inapropriate for 24P7.

编辑:prevous soluton不适合24P7。

#1