>
> I think it's harder for some people to see why the
>
> assert j not in seen
>
> must be true, although that's obvious after just a few hours' thought .
That's where you get to leave comments like:
#it follows logically that
assert j not in seen
or
#by implication
assert j not in see
On 7 Apr 2005 10:44:49 -0700, [EMAIL PROTECTED]
<[EMAIL PROTECTED]> wrote:
> Tim's solution is very nice, it comes from basic things often taught in
> good computer science courses.
I dunno, that comes from my Abstract Algebra course a heck of a lot
more than it came from any of my CS classes (I g
[Paul Rubin]
> Writing a sorting function from scratch for this purpose seems like
> reinventing the wheel.
Yup! list.sort() is going to be mounds faster.
> Tim's answer of simply counting the cycles (without having to pay
> attention to their length) is really clever. I didn't realize you coul
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
--
http://mail.python.org/mailman/listinfo/python-list
Peter Nuttall <[EMAIL PROTECTED]> writes:
> 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 so
On Wed, Apr 06, 2005 at 03:30:41PM -0700, RickMuller 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 would just write 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.
So you want the parity ("sign") of the associated permutation.
> I coul
>> 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 inva
[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
Boy, what a snotty answer to a question that had nothing to do with a
homework assignment!
--
http://mail.python.org/mailman/listinfo/python-list
The combinatorics application is very close, since we use A(N) to
represent fermions in quantum mechanics.
--
http://mail.python.org/mailman/listinfo/python-list
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.
--
http://mail.p
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 Qua
Paul Rubin wrote:
> John Machin <[EMAIL PROTECTED]> writes:
...
> > 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 alter
"Jordan Rastrick" <[EMAIL PROTECTED]> 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
John Machin <[EMAIL PROTECTED]> 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 s
On 6 Apr 2005 17:59:04 -0700, "Jordan Rastrick"
<[EMAIL PROTECTED]> 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:
>
>#
>phase = 1
>def mycmp(x,y):
> global phase
> c =
On 6 Apr 2005 15:30:41 -0700, "RickMuller" <[EMAIL PROTECTED]> 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
[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 perf
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 = -pha
[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.
[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:
>
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
23 matches
Mail list logo
