0

I'm looking for an efficient way to achieve this:

  1. you have a set of numbers, let's say that our set is equal to 4 (N = 4);
  2. you have to generate all permutations of 3 elements (K = 3);

Output for N = 4 and K = 3:

1 2 3
1 2 4
1 3 2
1 3 4
1 4 2
1 4 3
2 1 3
2 1 4
2 3 1
2 3 4
2 4 1
2 4 3
3 1 2
3 1 4
3 2 1
3 2 4
3 4 1
3 4 2
4 1 2
4 1 3
4 2 1
4 2 3
4 3 1
4 3 2

Anyone have a great, nice'n'quick algorithm up their sleeve or web reference??

Thanks!

nenito
  • 1,214
  • 6
  • 19
  • 33
  • 1
    This question has been answered a hundred times. Please search on your topic before posting. Flagged. – Tyler Durden Nov 01 '12 at 17:33
  • @TylerDurden the general way of doing this is to vote for close as exact duplicate. – Woot4Moo Nov 01 '12 at 18:09
  • @TylerDurden: There are familiar topics you are right, I've already checked them, but with this difference that you have permutations of N elements (N=K) not permutations of k objects from a set of n elements. – nenito Nov 01 '12 at 20:14
  • 1
    You can't go better than O(n!/(n-k)!) complexity since this is the number of the permutations. – SomeWittyUsername Nov 02 '12 at 11:28
  • @icepack: Then I should change the concept of the algorithm! :( – nenito Nov 02 '12 at 12:25
  • possible duplicate of [Algorithm to generate all possible permutations of a list?](http://stackoverflow.com/questions/2710713/algorithm-to-generate-all-possible-permutations-of-a-list) – Lukas Knuth Nov 04 '12 at 21:34

1 Answers1

1

Something like this pseudocode:

permute(set, output, len)  //output will hold all the permutations

for each number in the set do
    choose number and store it at output[0]
    if(!empty(set))
        call permute(set{without the number}, output + (len - 1)!, len-1) //adjust the position

Invoke by permute(set, output, k)

SomeWittyUsername
  • 18,025
  • 3
  • 42
  • 85
  • @Woot4Moo you're always welcomed to criticize as long as it constructive – SomeWittyUsername Nov 01 '12 at 17:25
  • i should have been more clear in my statement, it was hard to deduce if the original `output+1` was referring to the index of output or if it was meant to increment whatever the previous value was by 1 – Woot4Moo Nov 01 '12 at 17:32