How do I get all permutations of xPy in C?

Question

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).

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?

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. :)

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

Answer 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...):

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

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.

1. create bitmask of your word. You can probably use 64 bit arithmetics so you can fit almost 3 alpahbets inside.

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

 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.

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.

Answer 3

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.

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.