Geek asks and answers

Effectively calculate the following permutation of length k from n options

I need to efficiently calculate the next permutation of the length kfrom the n selection. Wikipedia lists an excellent algorithm for calculating the next permutation of a length nfrom n.

The best I can think of is to use this algorithm (or the Steinhaus-Johnson-Trotter algorithm ), and then just taking into account the first kelements of the list, and repeating it whenever the changes are all above this position.

Limitations:

  • The algorithm should calculate the next permutation giving no more than the current permutation. If he needs to generate a list of all permutations, it will take up too much memory.
  • It should be able to compute a permutation only of length kof n(this is where another algorithm fails

non-restrictions:

  • Doesn't care if he's in place or not
  • I don’t care if it is in lexicographical order or in any case in this case
  • I don’t care how efficiently he calculates the next permutation. Of course, he cannot give me the next permutation, having made a list of all the possible ones.
+5
source share
1 answer

You can break this problem into two parts:

1) Find all size subsets kfrom a size set n.

2) For each such subset, find all permutations of the subset of size k.

2, . 1 . " k [0...n-1].

1) [0...k-1]

2) , S:

2a) j , j ∈ S ∧ j+1 ∉ S. j == n-1, ; .

2b) , j, i...j-1 ( - , j ). i 0, i-i...j-i-1. j j+1.

+1

More articles:


All Articles