3

The question is:
Given a sequence of positive integers A={1,2,3,...,N}.
Count the number of sequences you can get after making K adjacent swaps on it for a given N ?
My approach:
My algorithm to solve such a programming question is very naive. I could only think of making all the possible k swaps and then count the sequences.
Can anyone help me out with a better algorithm?

user3757909
  • 75
  • 5
  • Perhaps move this question to: http://math.stackexchange.com/ Seems like pretty basic prob & stats. –  Jun 19 '14 at 20:03

1 Answers1

3

Inversions

The key to this type of problem (of swapping adjacent elements) is to consider the number of inversions in the permutation after each swap.

Two elements a[i] and a[j] form an inversion if a[i] > a[j] and i < j.

The number of inversions in a permutation is the number of pairs of elements which form an inversion.

The reason this is useful is because whenever you perform a swap of adjacent elements, the inversion count either goes up by 1 or goes down by 1.

Hint to solve problem

Therefore, after K swaps the total number of inversions must be one of the following values: K,K-2,K-4, etc.

So we have reduced the problem to one of counting the number of permutations with K or K-2 or K-4, etc. inversions. The number of permutations with a given number of inversions is given by the triangle of Mahonian numbers.

Code to solve problem

All you need to do is to compute row N of the triangle (code can be found here) and then sum the appropriate entries:

row = mahonian_row(N)
print sum(row[n] for n in range(K+1) if n%2==K%2 and n<len(row))
Community
  • 1
  • 1
Peter de Rivaz
  • 33,126
  • 4
  • 46
  • 75
  • What if it is a swap of any two elements rather than adjacent? – ChuNan Jun 20 '14 at 15:25
  • 2
    In that case you should start thinking about the permutation in terms of its cycle decomposition. The cycle decomposition of a permutation would tell you how many non-adjacent swaps are needed (by simply subtracting 1 from the lengths of the cycles), so you will end up counting the number of possible decompositions into cycles with a length constraint. This is likely to involve a sum of entries in Pascal's triangle instead of the Mahonian triangle. – Peter de Rivaz Jun 20 '14 at 15:57