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

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

 

[Raymond Hettinger]

[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
lowest = i
for j in xrange(i, len(a)):
if a[j] < a[lowest]:
lowest = j
if i != lowest:
a, a[lowest] = a[lowest], a
parity = -parity
print 'swapping %d with %d. parity is %d' % (i, lowest, parity)
print parity, a


Raymond

 

[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

 

[Raymond Hettinger]

[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

 

[John Machin]

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?

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?

 

[John Machin]

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

 

[Paul Rubin]

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

 

[Paul Rubin]

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.

 

[Dan Bishop]

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

It's also used in linear algebra, as part of the definition of the
determinant.

 

[RickMuller]

Well, it's a homework problem in the sense that I happen to be working
on it at my home, but, no, I'm not in school anymore. In Quantum
Mechanics we use determinants to enforce the Pauli principle, which
says that anytime two electrons are exchanged the wave function has to
change sign. In most Quantum Mechanical packages (for example,
PyQuante, http://pyquante.sf.net, which I wrote some years ago, is a
Python based quantum chemistry package) we don't actually have to
evaluate a determinant, we just evaluate the effect of the two-electron
operators on the permuted wave function. However, I'm working on some
quantum monte carlo codes where I'm trying to keep track of
configuration spin functions, which requires me to count every time I
flip orbitals.

 

[RickMuller]

Boy, what a snotty answer to a question that had nothing to do with a
homework assignment!

 

[RickMuller]

Thanks, this will indeed work. I guess I've gotten out of the habit of
writing cmp functions since Tim Peter's introduction to the sorting
chapter in the first edition of the Python Cookbook convinced me it was
inefficient. But the lists should be short here and this should work.

 

[RickMuller]

The combinatorics application is very close, since we use A(N) to
represent fermions in quantum mechanics.

 

[Raymond Hettinger]

[John Machin]

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.

As the dataset contains no duplicates, the parity will be the same irrespective
of sorting method.

3. Of what practical use (or even esoteric academic interest) is the
parity of the number of interchanges?

I presume the goal is academic, determining whether a permutation is a member of
the alternating group of even permutations (A4, A5, ...). For some problems,
that is a useful invariant. For instance, iirc, the parity determines whether a
given 15 puzzle arrangement is solvable.


Raymond

 

[RickMuller]

3. Of what practical use (or even esoteric academic interest) is the

I presume the goal is academic, determining whether a >permutation is a member of
the alternating group of even permutations (A4, A5, ...). For >some problems,
that is a useful invariant. For instance, iirc, the parity
determines whether a
given 15 puzzle arrangement is solvable.

To tell whether a wave function corresponds to bosons or fermions.

 

[Tim Peters]

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

So you want the parity ("sign") of the associated permutation.

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]

Good so far -- keep that much. Pass `order` to the function below.
It computes the sign in linear time.

phase = 0
for i in range(len(order)-1):
if order > order[i+1]: phase += 1

That part isn't correct. For example, it computes phase == 1 for both

[1, 0, 2]
and
[1, 2, 0]

but those obviously have different parities (since they're one
transposition apart).

phase = 2*(phase%2)-1

However, I can't prove that this works,

and there's *got* to be a more elegant way.

Why? There's no efficient way to solve this via counting
transpositions directly, although there is an efficient way by
computing the cycle structure. The following is an elegant way to do
the latter, but "elegance" requires buying into that this is necessary
if you want an efficient solution.

def permsign(p):
"""Return sign of permutation p.

p must be a permutation of the list range(len(p)).
The return value is 1 if p is even, or -1 if p is odd.

>>> for p in ([0,1,2], [0,2,1], [1,0,2],

... [1,2,0], [2,0,1], [2,1,0]):
... print p, permsign(p)
[0, 1, 2] 1
[0, 2, 1] -1
[1, 0, 2] -1
[1, 2, 0] 1
[2, 0, 1] 1
[2, 1, 0] -1
"""

n = len(p)
rangen = range(n)
if sorted(p) != rangen:
raise ValueError("p of wrong form")

# Decompose into disjoint cycles. We only need to
# count the number of cycles to determine the sign.
num_cycles = 0
seen = set()
for i in rangen:
if i in seen:
continue
num_cycles += 1
j = i
while True:
assert j not in seen
seen.add(j)
j = p[j]
if j == i:
break

return (-1)**(n - num_cycles)

 

[Peter Nuttall]

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.

<snip>

I would just write a quicksort and have a counter in the swap function.
A cunning way to do it would be to multiply the counter by -1 for each
swap. if you want I can write what I had in mind. Wikipedia has a good
article of quicksort.

Pete

 

[Paul Rubin]

I would just write a quicksort and have a counter in the swap function.
A cunning way to do it would be to multiply the counter by -1 for each
swap. if you want I can write what I had in mind. Wikipedia has a good
article of quicksort.

Writing a sorting function from scratch for this purpose seems like
reinventing the wheel. Tim's answer of simply counting the cycles
(without having to pay attention to their length) is really clever. I
didn't realize you could do that. Proving it is a cute exercise.
Hint: any cycle of odd length has an even number of swaps, and any
cycle of even length has an odd number of swaps (another exercise).

http://en.wikipedia.org/wiki/Even_and_odd_permutations
http://en.wikipedia.org/wiki/Permutation

 

[bearophileHUGS]

Tim's solution is very nice, it comes from basic things often taught in
good computer science courses.

In Python when you have to do many (-1)**n you can do:
(1-2*(n%2))
This seems quite faster.

Bearophile