sorting a list and counting interchanges

[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.

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

[Raymond Hettinger]

Re: sorting a list and counting interchanges

[RickMuller][color=blue]
> 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.[/color]

This sounds like a homework problem but will offer a solution anyway:
[color=blue][color=green][color=darkred]
>>> phase = 1
>>> def mycmp(x, y):[/color][/color][/color]
global phase
phase = -phase
return cmp(x, y)
[color=blue][color=green][color=darkred]
>>> sorted('abracad abra', cmp=mycmp)[/color][/color][/color]
['a', 'a', 'a', 'a', 'a', 'b', 'b', 'c', 'd', 'r', 'r'][color=blue][color=green][color=darkred]
>>> phase[/color][/color][/color]
-1



Raymond Hettinger

[Raymond Hettinger]

Re: sorting a list and counting interchanges

[RickMuller][color=blue]
> 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.[/color]

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

[Jordan Rastrick]

Re: sorting a list and counting interchanges

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

[Raymond Hettinger]

Re: sorting a list and counting interchanges

[Jordan Rastrick][color=blue]
> 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[/color]

You're right. An important test was omitted.


Raymond

[John Machin]

Re: sorting a list and counting interchanges

On 6 Apr 2005 15:30:41 -0700, "RickMuller " <rpmuller@gmail .com> wrote:
[color=blue]
>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?
>[/color]

1. What is an "interchang e"?

2. Without a definition that refers only to to the input and output,
one would have to say that "interchang e" 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?

[John Machin]

Re: sorting a list and counting interchanges

On 6 Apr 2005 17:59:04 -0700, "Jordan Rastrick"
<jrastrick@stud ent.usyd.edu.au > wrote:
[color=blue]
>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[/color]

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 :-)

[color=blue]
> phase = -phase
> return c[/color]

[Paul Rubin]

Re: sorting a list and counting interchanges

John Machin <sjmachin@lexic on.net> writes:[color=blue]
> 1. What is an "interchang e"?[/color]

Swapping two elements during the sort.
[color=blue]
> 2. Without a definition that refers only to to the input and output,
> one would have to say that "interchang e" implies "event" and so the
> number of interchanges would depend on the sorting method.[/color]

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.
[color=blue]
> 3. Of what practical use (or even esoteric academic interest) is the
> parity of the number of interchanges?[/color]

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).

[Paul Rubin]

Re: sorting a list and counting interchanges

"Jordan Rastrick" <jrastrick@stud ent.usyd.edu.au > writes:[color=blue]
> 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[/color]

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.