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 --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
