There was a task to realize the search for "the number of permutations of a sequence 1,2 ... n which have exactly k inversions" by input data. I did it through dynamics, everything works correctly, but in the output stream, you need to output not only the number of subsequences, but also the smallest among them in lexicographical order.

I used the following algorithm for output: create an array array storing elements 1,2,3 ... n in direct sequence, then go from element ni to n, where i (1, n) interchange the elements, and increment the counter for each change , until he (the counter) reaches the required quantity (k). This scheme works with k <= (1 + 2 + 3 + ... + n-2). That is, when n = 4, k = 1 - 1243.

However, for numbers that exceed these values ​​(that is, when, according to the algorithm, the first element is replaced), the algorithm no longer plows n = 5, k = 7 - 51432, although there are smaller subsequences (25431, for example).

How can you modify it, or solve this subtask differently? There was an idea with a complete search - that is, we go from a direct sequence, gradually increasing it and checking whether it fits us through an additional function - but this implementation is eating too many resources.

  • Thanks for the puzzle :) - Alexander VoidEx Ruchkin
  • When you calculate - do you accidentally get the inversions yourself? then you just have to keep the minimum ... - Harry
  • dynamics should be typed ... If you can put the minimum and then everything is typed, then we must put. And the check further only depends on the number of those remaining. By the way, counting the number of all permutations is more difficult. - pavel

1 answer 1

All the same, I managed without brute force, because "realized" the algorithm for which the increase in permutations occurs, I quote it below, it may be useful to someone.

In the same way, we output a direct sequence and then change the m [k] symbol on it with m [n], where k changes on the interval [mas.size () - 2,0], n changes on the interval [mas.size () - 1, k + 1] (the passage in k is the outer loop, in n - the inner loop). For each replacement, increment the counter until we find the right amount.