Hello, On Nov 8, 3:02 pm, "Ondrej Certik" <[EMAIL PROTECTED]> wrote: > On Sat, Nov 8, 2008 at 11:58 PM, Alan Bromborsky <[EMAIL PROTECTED]> wrote: > > > Does anyone know a good (fast) way of determining the number of > > permutations needed to order a short list of integers say 10 or less and > > that would also return the ordered list?
Are you asking number of transpositions (swapping two numbers) that are needed to sort a list? Only one permutation is ever needed -- the one that puts things in the right order. You can do something like this to sort the list and figure out the permutation used to put things in the right order: sage: a = [50, 30, 20, 10, 40] sage: sorted_a, perm = zip(*sorted(zip(a,range(len(a))))) sage: sorted_a (10, 20, 30, 40, 50) sage: (3, 2, 1, 4, 0) sage: [a[perm[i]] for i in range(len(a))] [10, 20, 30, 40, 50] >From perm, you can calculate the number of transpositions needed by calculating the length of the permutation which is given by the number of times a bigger number appears before a smaller one in the permutation. In the example above, this happens 7 times ( 3>2, 3>2, 3>0, 2>1, 2>0, 1>0, 4>0 ), sage: [1 if perm[i] > perm[j] else 0 for i in range(len(perm)) for j in range(len(perm)) if i < j] [1, 1, 0, 1, 1, 0, 1, 0, 1, 1] sage: sum(_) 7 Therefore, the minimum number of swaps/transpositions needed to order the list is 7. The inversions tell you the transpositions needed. sage: p = Permutation([i+1 for i in perm]) sage: p.inversions() [[0, 1], [0, 2], [0, 4], [1, 2], [1, 4], [2, 4], [3, 4]] sage: for i,j in reversed(p.inversions()): ....: a[i],a[j] = a[j],a[i] sage: a [10, 20, 30, 40, 50] --Mike --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "sympy" group. To post to this group, send email to sympy@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sympy?hl=en -~----------~----~----~----~------~----~------~--~---
