0
$\begingroup$

Im working on a problem where i have 2 variables

A= (1,2,3) B= (3,2,1)

I have to calculate the number of permutations, and the number of paths by swaping adjancent numbers until A becomes B

For permutations Im currently using the following function in python

nPr = (math.factorial(n))/(math.factorial(n-n)) 

This one works as intended and the result is ok (in this case nPr = 6), however how can I calculate the number of paths (swaps of pairs) until i get to B?

The combination formula

(n!)/((n-r!)*(r!))

doesnt seem to make the job since it always comes out as 1. (when r = n)

So there has to be another way to do this, I tried using the factorial of nPr however when 6! = 720, meaning theres 720 posible paths to get to B and thats not true.

this was just one example of 3 digits but A and B can be sets of numbers of 2,3,4,5... etc

$\endgroup$
  • 1
    $\begingroup$ Welcome Math.SE! Take the tour to get familiar with this site. Mathematical expressions and equations can be formatted using LATEX syntax. If you receive useful answers, consider accepting one. $\endgroup$ – Shailesh Sep 28 '15 at 4:17
0
$\begingroup$

For a list of size n my idea would be:

You need maximum n-1 swaps to put the first digit into its correct position, then you need maximum n-2 swaps to put the second digit into its correct position, n-3 for the third and so on untill 0 for the last.

Therefore maximum (1/2)(n-1)(n) swaps

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.