Ondrej Certik wrote: > On Sun, Nov 9, 2008 at 9:08 AM, Mike Hansen <[EMAIL PROTECTED]> wrote: > >> 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] >> > > > Thanks Mike for a thorough answer! > > Alan, are the answers sufficient? > > Ondrej > > > > > YES!
--~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "sympy" group. To post to this group, send email to [email protected] 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 -~----------~----~----~----~------~----~------~--~---
