Re: [perl-python] exercise: partition a list by equivalence

A slightly better version, only walks the set of cumulative list of sets once per pairing. -- Paul .import sets . .input = [[1, 2], [3, 4], [2, 3], [4, 5]] .input = [[1, 2], [3, 4], [4, 5]] .input = [[1, 2],[2,1], [3, 4], [4, 5],[2,2],[2,3],[6,6]] . .def merge(pairings): .ret

Re: [perl-python] exercise: partition a list by equivalence

Please consider my submission also (Python 2.3-compatible). -- Paul McGuire .import sets . .input = [[1, 2], [3, 4], [2, 3], [4, 5]] .input = [[1, 2], [3, 4], [4, 5]] .input = [[1, 2],[2,1], [3, 4], [4, 5],[2,2],[2,3],[6,6]] . .def merge(pairings): .ret = [] .f

Re: exercise: partition a list by equivalence

I started to collect i believe the 4 or so solutions by different people... but seems it's gonna take some an hour or more... So far the only other one i've run and find alright is Reinhold Birkenfeld's original. Others worth noting i'm aware of is David Epsteinn, improved versions from Reinhold Bi

Re: exercise: partition a list by equivalence

In article <[EMAIL PROTECTED]>, "John Machin" <[EMAIL PROTECTED]> wrote: > > it would be nice if the two working programs do not use some package. > > This problem shouldn't need to. > > Look at the newsgroup again. By my count there are apparently-working > versions from SIX people: Reinhold, b

Re: exercise: partition a list by equivalence

John Machin wrote: > Reinhold Birkenfeld wrote: >> Reinhold Birkenfeld wrote: >> >> > My solution (which may not be the fastest or most effective, but > till >> > now is the shortest and it works): > > [snip RB] >> >> A recursive solution (around twice as fast as the above, though very >> slow st

Re: exercise: partition a list by equivalence

John Machin wrote: Xah is asserting his right to be recognised as the author of his artistic creations, line by line. Not very well, however, since his usage doesn't constitute a valid copyright notice :-). -- Erik Max Francis && [EMAIL PROTECTED] && http://www.alcyone.com/max/ San Jose, CA, USA

Re: exercise: partition a list by equivalence

Eric Pederson wrote: > > From: "Xah Lee" <[EMAIL PROTECTED]> > > ©for group in interm: > what do the funny little "©"s stand for? ...>>> import unicodedata as ucd; ucd.name('©'.decode('cp1252')) 'COPYRIGHT SIGN' Xah is asserting his right to be recognised as the author of his artistic creati

Re: exercise: partition a list by equivalence

Reinhold Birkenfeld wrote: > Reinhold Birkenfeld wrote: > > > My solution (which may not be the fastest or most effective, but till > > now is the shortest and it works): [snip RB] > > A recursive solution (around twice as fast as the above, though very > slow still...) > [snip RB2] > > Another

Re: [perl-python] exercise: partition a list by equivalence

Reinhold Birkenfeld wrote: > My solution (which may not be the fastest or most effective, but till > now is the shortest and it works): > > def merge(pairings): > sets = {} > for x1, x2 in pairings: > newset = (sets.get(x1, frozenset([x1])) > | sets.get(x2, froz

Re: exercise: partition a list by equivalence

On 20 Feb 2005 03:31:33 -0800, [EMAIL PROTECTED] wrote: >John Machin: >>FWIW, my offering is attached. < > >I'm sorry, I don't see the attach... (just the different title). > Here it is. I'll reply to the rest tomorrow. It's way past sleep-time here. ! !class _Stopper: !pass ! !def merge_JM

Re: exercise: partition a list by equivalence

> From: "Xah Lee" <[EMAIL PROTECTED]> > > The GOTO statement from Perl has been messed up. hey, I didn't do it! > > This block: > Âfor group in interm: what do the funny little "Â"s stand for? Eric Pederson http://www.songzilla.blogspot.com ::: domai

Re: exercise: partition a list by equivalence

John Machin: >Perhaps I'm missing a posting of yours -- what are merge2 and merge4? What is "this random pairs test"? What is xMax (nPairs isn't hard to guess), and how are you generating your input data?< merge2 and this random pairs test comes from the post by Brian Beck. merge4 is the first in

Re: exercise: partition a list by equivalence

Xah Lee wrote: > when i try to run the following program, Python complains about some > global name frozenset is not defined. Is set some new facility in > Python 2.4? http://www.python.org/doc/2.3/whatsnew/ http://www.python.org/doc/2.4/whatsnew/whatsnew24.html You must be running 2.3. If you p

[perl-python] exercise: partition a list by equivalence

when i try to run the following program, Python complains about some global name frozenset is not defined. Is set some new facility in Python 2.4? ©# from Reinhold Birkenfeld ©def merge(pairings): ©sets = {} ©for x1, x2 in pairings: ©newset = (sets.get(x1, frozenset([x1])) ©

Re: exercise: partition a list by equivalence - merge_JM.py (0/1)

On 19 Feb 2005 17:56:27 -0800, [EMAIL PROTECTED] wrote: >John Machin>FWIW, here's a brief UAT report: > >Here is something else for you. >Note: for more correct comparisons, for the following tests I've >disabled the use of Psyco in Graph (usually enabled, if present). >This looks faster than merg

Re: exercise: partition a list by equivalence

John Machin>FWIW, here's a brief UAT report: Here is something else for you. Note: for more correct comparisons, for the following tests I've disabled the use of Psyco in Graph (usually enabled, if present). This looks faster than merge2 for this (quite sparse) random pairs test: . import graph #

Re: exercise: partition a list by equivalence

an interesting problem so developed now is to write a function that generate test cases for the purpose of testing performance. (just for fun) the design of this function could be interesting. We want to be able to give parameters in this function so as to spit out all possible screw test cases. F

Re: exercise: partition a list by equivalence

Reinhold Birkenfeld wrote: > Xah Lee wrote: > > here's the answer to the partition by equivalence exercise. > > Your Python solution is, as expected, wrong (try with > [[10, 8], [7, 3], [1, 7], [5, 4], [2, 2], [3, 8], [7, 10], [2, 3], [6, > 10], [3, 2]] > for example). > > The solution by John Len

Re: [perl-python] exercise: partition a list by equivalence

Reinhold Birkenfeld wrote: def merge(pairings): sets = {} for x1, x2 in pairings: newset = (sets.get(x1, frozenset([x1])) | sets.get(x2, frozenset([x2]))) for i in newset: sets[i] = newset return [list(aset) for aset in set(sets.itervalues()

Re: exercise: partition a list by equivalence

The GOTO statement from Perl has been messed up. This block: ©for group in interm: ©for newcoup in fin: ©for k in group.keys(): ©if newcoup.has_key(k): ©for kk in group.keys(): newcoup[kk]='x'; ©break ©break ©

Re: exercise: partition a list by equivalence

In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] wrote: > David Eppstein: > > However it might be easier to treat the input pairs as the edges of a > > graph and apply a depth-first-search based graph connected components > > algorithm. || This would be O(n), though. > > Is the DFS the best one

Re: exercise: partition a list by equivalence

Bearophile: > I presume the complexity is O(n+a); n (the nodes) > is proportional to the number of pairs, and a > (the arcs) depends on the "intricacy" of the input pairs. Opps... n (the number of nodes) is the number of different numbers contained in the pairs :-] Bearophile -- http://mail.pyt

Re: exercise: partition a list by equivalence

David Eppstein: > However it might be easier to treat the input pairs as the edges of a > graph and apply a depth-first-search based graph connected components > algorithm. || This would be O(n), though. Is the DFS the best one here (instead of BFS)? With the graph implementation that I've just s

Re: [perl-python] exercise: partition a list by equivalence

Xah Lee wrote: > here's the answer to the partition by equivalence exercise. Your Python solution is, as expected, wrong (try with [[10, 8], [7, 3], [1, 7], [5, 4], [2, 2], [3, 8], [7, 10], [2, 3], [6, 10], [3, 2]] for example). The solution by John Lenton is wrong, too. The solution by Brian Be

[perl-python] exercise: partition a list by equivalence

here's the answer to the partition by equivalence exercise. --- # Perl code sub merge($) { my @pairings = @{$_[0]}; my @interm; # array of hashs # chop the first value of @pairings into @interm $interm[0]={$pairings[0][0]=>'x'}; ${interm[0]}{$pairings[0]

Re: exercise: partition a list by equivalence

On Fri, Feb 18, 2005 at 09:57:59PM -0800, John Machin wrote: > > > > this, together with you saying that it is hard to explain, makes me > > think that you aren't comfortable thinking of lists as mutable > > objects. > > How so? There is no connection between is/== and mutability. Let me > amplify

Re: exercise: partition a list by equivalence

John Lenton wrote: > On Fri, Feb 18, 2005 at 04:52:46PM -0800, John Machin wrote: > > > > needs "if rev[first] == rev[second]: continue" here > > > > > > an 'is' is enough, and better. > > > > Good point. You're redeeming yourself :-) > > this, together with you saying that it is hard to explain,

Re: exercise: partition a list by equivalence

In article <[EMAIL PROTECTED]>, David Eppstein <[EMAIL PROTECTED]> wrote: > It can be solved by union-find > (e.g. with UnionFind from ): Here's a cleaned up version, after I added a proper iter() method to the UnionFind data structure: import UnionFind

Re: exercise: partition a list by equivalence

On Fri, Feb 18, 2005 at 04:52:46PM -0800, John Machin wrote: > > > needs "if rev[first] == rev[second]: continue" here > > > > an 'is' is enough, and better. > > Good point. You're redeeming yourself :-) this, together with you saying that it is hard to explain, makes me think that you aren't com

Re: [perl-python] exercise: partition a list by equivalence

Well, it looks like David posted a good solution, but I haven't tested it (I'm assuming his works fine). I fixed mine up anyway... it actually works now. If you're not using 2.4 you'll have to import sets.Set as set. def merge(pairList): pairList = set(tuple(sorted(p)) for p in pairList)

Re: exercise: partition a list by equivalence

In article <[EMAIL PROTECTED]>, "John Machin" <[EMAIL PROTECTED]> wrote: > You don't need to think. This problem has been extensively picked over > by folk who are a lot smarter than us, starting from 30 years ago. > Google for "disjoint set" and "union-find". One gets the impression > that the b

Re: [perl-python] exercise: partition a list by equivalence

Brian Beck wrote: Brian Beck wrote: > [code] Ah heck, nevermind... it worked for my small test cases but the algorithm is just wrong. -- Brian Beck Adventurer of the First Order -- http://mail.python.org/mailman/listinfo/python-list

Re: [perl-python] exercise: partition a list by equivalence

Brian Beck wrote: > [code] Whoops, that should say: def merge(pairs): pairs = set(tuple(sorted(p)) for p in pairs) merged = [] # Each loop will result in a new, complete sublist in the result. while pairs: p = set(pairs.pop()) remove = set([]) for pair in pai

Re: [perl-python] exercise: partition a list by equivalence

Xah Lee wrote: merge($pairings) takes a list of pairs, each pair indicates the sameness of the two indexes. Returns a partitioned list of same indexes. For example, if the input is merge( [ [1,2], [2,4], [5,6] ] ); that means 1 and 2 are the same. 2 and 4 are the same. Therefore 1==2==4. The result

Re: exercise: partition a list by equivalence

John Lenton wrote: > On Fri, Feb 18, 2005 at 03:21:10PM -0800, John Machin wrote: > > Not robust in the face of input like: > > [[1,1]] > > or > > [[1,2], [1,2]] > > or > > [[1,2], [2,1]] > > or > > [[1,2], [2,3], [3,1]] > > oops, my bad. > > > > > needs "if first == second: continue" here > > > >

Re: [perl-python] exercise: partition a list by equivalence

Hello John, Try your python code on this example: merge([[1,2], [3,4], [1,2], [5,3]]) The result given by your function is: [[3, 4, 5]] Sorry... To Xah: next time you propose an exercise, write some UNIT TESTS!!! Then people will be able to test if there answers are correct or not. Cyril

Re: exercise: partition a list by equivalence

On Fri, Feb 18, 2005 at 03:21:10PM -0800, John Machin wrote: > Not robust in the face of input like: > [[1,1]] > or > [[1,2], [1,2]] > or > [[1,2], [2,1]] > or > [[1,2], [2,3], [3,1]] oops, my bad. > > needs "if first == second: continue" here > > > if has_first and has_second: > >

Re: exercise: partition a list by equivalence

John Lenton wrote: > On Thu, Feb 17, 2005 at 03:46:20PM -0800, Xah Lee wrote: > > here's another interesting algorithmic exercise, again from part of a > > larger program in the previous series. > > > > Here's the original Perl documentation: > > > > =pod > > > > merge($pairings) takes a list of p

Re: [perl-python] exercise: partition a list by equivalence

On Thu, Feb 17, 2005 at 03:46:20PM -0800, Xah Lee wrote: > here's another interesting algorithmic exercise, again from part of a > larger program in the previous series. > > Here's the original Perl documentation: > > =pod > > merge($pairings) takes a list of pairs, each pair indicates the > sam

Re: [perl-python] exercise: partition a list by equivalence

Xah Lee wrote: here's another interesting algorithmic exercise, again from part of a larger program in the previous series. Here's the original Perl documentation: =pod merge($pairings) takes a list of pairs, each pair indicates the sameness of the two indexes. Returns a partitioned list of same in

Re: [perl-python] exercise: partition a list by equivalence

>For those of you unfamiliar with math lingoes, partition a list means > to create sublists, based on some criteria. Typical moronic mathematicians with their exclusionary lingoes...why can't they just say "create sublists based on some criteria" like normal people? - alex23 -- http://mail.pyth

[perl-python] exercise: partition a list by equivalence

here's another interesting algorithmic exercise, again from part of a larger program in the previous series. Here's the original Perl documentation: =pod merge($pairings) takes a list of pairs, each pair indicates the sameness of the two indexes. Returns a partitioned list of same indexes. For