CODEWITHSUNDEEP
algorithmpermutation
Luka Horvat
Luka Horvat

Reputation: 4402

Generate a list of permutations paired with their number of inversions

I'm looking for an algorithm that generates all permutations of a set. To make it easier, the set is always [0, 1..n]. There are many ways to do this and it's not particularly hard.

What I also need is the number of inversions of each permutation. What is the fastest (in terms of time complexity) algorithm that does this?

I was hoping that there's a way to generate those permutations that produces the number of inversions as a side-effect without adding to the complexity.

The algorithm should generate lists, not arrays, but I'll accept array based ones if it makes a big enough difference in terms of speed.

Plus points (...there are no points...) if it's functional and is implemented in a pure language.

Upvotes: 0

Views: 724

Answers (2)

btilly
btilly

Reputation: 46417

Here is an algorithm that does the task, is amortized O(1) per permutation, and generates an array of tuples of linked lists that share as much memory as they reasonably can.

I'll implement all except the linked list bit in untested Python. Though Python would be a bad language for a real implementation.

def permutations (sorted_list):
    answer = []
    def add_permutations(reversed_sublist, tail_node, inversions):
        if (0 == len(sorted_sublist)):
            answer.append((tail_node, inversions))
        else:
            for idx, val in enumerate(reversed_sublist):
                add_permutations(
                    filter(lambda x: x != val),
                    ListNode(val, tail_node,
                    inversions + idx
                )

    add_permutations(reversed(sorted_list), EmptyListNode(), 0)
    return answer

You might wonder at my claim of amortized O(1) work with all of this copying. That's because if m elements are left we do O(m) work then amortize it over m! elements. So the amortized cost of the higher level nodes is a converging cost per bottom call, of which we need one per permutation.

Upvotes: 1

MBo
MBo

Reputation: 80197

There is Steinhaus–Johnson–Trotter algorithm that allows to keep inversion count easily during permutation generation. Excerpt from Wiki:

Thus, from the single permutation on one element,
1
one may place the number 2 in each possible position in descending
order to form a list of two permutations on two elements,
1 2
2 1
Then, one may place the number 3 in each of three different positions
for these three permutations, in descending order for the first 
permutation 1 2, and then in ascending order for the permutation 2 1:
1 2 3
1 3 2
3 1 2
3 2 1
2 3 1
2 1 3

At every step of recursion we insert the biggest number in the list of smaller numbers. It is obvious that this insertion adds M new inversions, where M is insertion position (counting from the right). For example, if we have 3 1 2 list (2 inversions), and will insert 4

3 1 2 4  //position 0, 2 + 0 = 2 inversions
3 1 4 2  //position 1, 2 + 1 = 3 inversions
3 4 1 2  //position 2, 2 + 2 = 4 inversions
4 3 1 2  //position 3, 2 + 3 = 5 inversions

pseudocode:

function Generate(List, Count)
   N = List.Length
   if N = N_Max then
      Output(List, 'InvCount = ': Count)
   else
      for Position = 0 to N do
         Generate(List.Insert(N, N - Position), Count + Position)

P.S. Recursive method is not mandatory here, but I suspect that it is natural for functional guys

P.P.S If you are worried about inserting into lists, consider Even's speedup section that uses only exchange of neighbour elements, and every exchange increments or decrements inversion count by 1.

Upvotes: 1

Related Questions