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
decoratesortundecorate 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  
Share this Question
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  
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  
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:
# <untested>
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  
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:
# <untested> 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  
P: n/a

On 6 Apr 2005 15:30:41 0700, "RickMuller" <rp******@gmail.com> wrote: 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 decoratesortundecorate 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?  
P: n/a

On 6 Apr 2005 17:59:04 0700, "Jordan Rastrick"
<jr*******@student.usyd.edu.au> wrote: 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:
# <untested> 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
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  
P: n/a

John Machin <sj******@lexicon.net> 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 order2 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).  
P: n/a

"Jordan Rastrick" <jr*******@student.usyd.edu.au> 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.   This discussion thread is closed Replies have been disabled for this discussion.   Question stats  viewed: 1867
 replies: 8
 date asked: Jul 18 '05
