0

I'm aware of Heap's algorithm to calculate permutations of a given sequence, but what if I wanted to calculate the permutations of a k-elements subset for a given sequence N?

The solution I'm thinking of this time is a backtracking one, but it would need to generate a new sequence of sub-elements each time deleting one and recursively calling the permutation function. This sounds expensive and I would like to know if there's a better solution

Albert
  • 1,085
  • 2
  • 10
  • 20
  • How big are n and k? No matter what, you need (n! - k!) answers, so this gets huge really, really quickly. – Dean J Jun 25 '15 at 13:32
  • You're right and the complexity will be daunting, however allocating space at each recursion is also expensive. I'm just wondering if there's a recursive standard algorithm to generate permutations (N,k) – Albert Jun 25 '15 at 13:34
  • @Albert There is an iterative algorithm to generate permutations of a given set. Are you seeking that one? – Vesper Jun 25 '15 at 13:53
  • @Vesper that might be good. Does it handle k subsets? – Albert Jun 25 '15 at 13:54
  • I don't get the question,then. Let's say your sequence `N` is `0,1,2,3,4,5,6,7,8,9`. You apparently want to get a subset of it, say `2 4 8` and then what, get all permutations of that? – Vesper Jun 25 '15 at 13:55
  • Perhaps I'm using the terms in the wrong way, I want something that can handle permutations of `0,1,2,3,4` with k = 2, i.e. `0,1` `0,2` `0,3`...`3,4` etc.. and since these are permutations `1,2` is different than `2,1` – Albert Jun 25 '15 at 13:56
  • 1
    use an [algorithm to generate combinations of size k](http://stackoverflow.com/questions/127704/algorithm-to-return-all-combinations-of-k-elements-from-n) followed by Heap's algorithm on the result, generate the next size k subset and repeat. – ryanpattison Jun 25 '15 at 13:57
  • And you already have the combination generator in place, according to your previous question. – Vesper Jun 25 '15 at 14:01
  • Thanks guys, I managed to have a good algorithm combining the twos. @rpattiso make it an answer and I'll accept it. – Albert Jun 25 '15 at 14:28

1 Answers1

0
  1. Use an algorithm to generate combinations of size K from the set of N. (Pick any from the SO question: Algorithm to return all combinations of k elements from n).
  2. Using the result, apply Heap's Algorithm to create all permutations of this k-element subset (or another Algorithm to generate all possible permutations of a list).
  3. Generate the next subset of size K and repeat (steps 1 and 2) until all subsets of size K have been enumerated.
Community
  • 1
  • 1
ryanpattison
  • 6,151
  • 1
  • 21
  • 28