454,519 Members | 1,831 Online
Need help? Post your question and get tips & solutions from a community of 454,519 IT Pros & Developers. It's quick & easy.

# sorting a list and counting interchanges

 P: n/a I have to sort a list, but in addition to the sorting, I need to compute a phase factor that is +1 if there is an even number of interchanges in the sort, and -1 if there is an odd number of interchanges. I could write a bubble sort, count the number of interchanges, and compute the factor, but I have a feeling that there some decorate-sort-undecorate solution buried in this problem somewhere. However, I can't see it. Can anyone else help me with this? I was thinking of something along the lines of zipping the list with a range() of the same length, sorting that, and then counting the number of times the second list has an item smaller than its previous item. In other words a = [1,10,2,7] b = zip(a,range(len(a))) b.sort() a_sorted = [i for i,j in b] order = [j for i,j in b] phase = 0 for i in range(len(order)-1): if order[i] > order[i+1]: phase += 1 phase = 2*(phase%2)-1 However, I can't prove that this works, and there's *got* to be a more elegant way. Thanks in advance, Rick Jul 18 '05 #1
8 Replies

 P: n/a [RickMuller] I have to sort a list, but in addition to the sorting, I need to compute a phase factor that is +1 if there is an even number of interchanges in the sort, and -1 if there is an odd number of interchanges. This sounds like a homework problem but will offer a solution anyway: phase = 1 def mycmp(x, y): global phase phase = -phase return cmp(x, y) sorted('abracadabra', cmp=mycmp) ['a', 'a', 'a', 'a', 'a', 'b', 'b', 'c', 'd', 'r', 'r'] phase -1 Raymond Hettinger Jul 18 '05 #2

 P: n/a [RickMuller] I have to sort a list, but in addition to the sorting, I need to compute a phase factor that is +1 if there is an even number of interchanges in the sort, and -1 if there is an odd number of interchanges. It occurs to me that the previously posted comparison count won't do it. The only idea that comes to mind is to do a selection sort and count the number of swaps. a = [1,10,2,7] parity = 1 for i in xrange(len(a)-1): x = a[i] lowest = i for j in xrange(i, len(a)): if a[j] < a[lowest]: lowest = j if i != lowest: a[i], a[lowest] = a[lowest], a[i] parity = -parity print 'swapping %d with %d. parity is %d' % (i, lowest, parity) print parity, a Raymond Jul 18 '05 #3

 P: n/a Unless I'm mistaken, this doesnt quite work, because it switches the parity of phase every time a comparison is made, rather than every time a swap is made. So: # phase = 1 def mycmp(x,y): global phase c = cmp(x,y) if c > 0: # i.e. a swap will be performed in the sort phase = -phase return c Jul 18 '05 #4

 P: n/a [Jordan Rastrick] Unless I'm mistaken, this doesnt quite work, because it switches the parity of phase every time a comparison is made, rather than every time a swap is made. So: # phase = 1 def mycmp(x,y): global phase c = cmp(x,y) if c > 0: # i.e. a swap will be performed in the sort phase = -phase return c You're right. An important test was omitted. Raymond Jul 18 '05 #5

 P: n/a On 6 Apr 2005 15:30:41 -0700, "RickMuller" wrote: I have to sort a list, but in addition to the sorting, I need tocompute a phase factor that is +1 if there is an even number ofinterchanges in the sort, and -1 if there is an odd number ofinterchanges.I could write a bubble sort, count the number of interchanges, andcompute the factor, but I have a feeling that there somedecorate-sort-undecorate solution buried in this problem somewhere.However, I can't see it. Can anyone else help me with this? 1. What is an "interchange"? 2. Without a definition that refers only to to the input and output, one would have to say that "interchange" implies "event" and so the number of interchanges would depend on the sorting method. 3. Of what practical use (or even esoteric academic interest) is the parity of the number of interchanges? Jul 18 '05 #6

 P: n/a On 6 Apr 2005 17:59:04 -0700, "Jordan Rastrick" wrote: Unless I'm mistaken, this doesnt quite work, because it switches theparity of phase every time a comparison is made, rather than every timea swap is made. So:# phase = 1def mycmp(x,y): global phase c = cmp(x,y) if c > 0: # i.e. a swap will be performed in the sort That's rather a wild assumption. It's not part of the language definition that the first argument is at a lower index in the list than the second argument. Perhaps it's been coded as though: c = cmp(y, x); if c < 0: swap() In any case I doubt if the OP's Data Structures & Algorithms 101 tutor is interested in anything so practical as the implementation of Python's list.sort() method :-) phase = -phase return c Jul 18 '05 #7

 P: n/a John Machin writes: 1. What is an "interchange"? Swapping two elements during the sort. 2. Without a definition that refers only to to the input and output, one would have to say that "interchange" implies "event" and so the number of interchanges would depend on the sorting method. The number of interchanges depends on the sorting method, but whether the number is odd or even is invariant. Every permutation of elements is either an odd permutation or an even permutation. 3. Of what practical use (or even esoteric academic interest) is the parity of the number of interchanges? It is of considerable interest in combinatorics. The group of even permutations on N elements is called the alternating group A(N). It's an order-2 subgroup of the symmetric group S(N) which is the group of all the permutations on N elements. The odd permutations are of course a coset of A(N). Jul 18 '05 #8

 P: n/a "Jordan Rastrick" writes: def mycmp(x,y): global phase c = cmp(x,y) if c > 0: # i.e. a swap will be performed in the sort phase = -phase return c That doesn't necessarily work. You don't know that c>0 will always result in a swap. You don't know that the sorting algorithm necessarily never swaps an element with itself. You have to find all the cycles in the permutation and count the length of each one. Is this a homework problem? If yes, the above should be enough of a hint. Jul 18 '05 #9

### This discussion thread is closed

Replies have been disabled for this discussion.