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][1]}='x'; shift @pairings; N1: for my $aPair (@pairings) { for my $aGroup (@interm) { if (exists ${$aGroup}{$aPair->[0]}) {${$aGroup}{$aPair->[1]}='x'; next N1} if (exists ${$aGroup}{$aPair->[1]}) {${$aGroup}{$aPair->[0]}='x'; next N1} } push @interm, {$aPair->[0]=>'x'}; ${interm[-1]}{$aPair->[1]}='x'; } my @fin = shift @interm; N2: for my $group (@interm) { for my $newcoup (@fin) { foreach my $k (keys %$group) { if (exists ${$newcoup}{$k}) {map { ${$newcoup}{$_}='x'} (keys %$group); next N2;} } } push @fin, $group; } return map {[keys (%$_)]} @fin; } ----------------------------------------------- # Here's a direct translation of the Perl code above into python: © ©def merge(pairings): # pairings is a list of couples. e.g. [(9,2),(7,6),...] © © # interm is a list of groups. Each group is a list that hold © # equivalent numbers. interm stands for interim result. Each group © # is a dictionary. Keys are numbers, values are all dummy © # 'x'. Dictionary is used for ease of dealing with duplicates or © # checking existence. © interm=[]; © © # move first pair of pairings into interm as the first group © interm.append({pairings[0][0]:'x', pairings[0][1]:'x'}) ; del pairings[0] © © # go thru pairings. For each pair, check if it is in any group in © # interm. If any part of pair is in a group, then add the other © # part into that group. If no part of the pair is in any group, © # then add this pair into interm as a new group. © for aPair in pairings: © for aGroup in interm: © if (aGroup.has_key(aPair[0])): aGroup[aPair[1]]='x'; break © if (aGroup.has_key(aPair[1])): aGroup[aPair[0]]='x'; break © else: interm.append( {aPair[0]:'x'} ); interm[-1][aPair[1]]='x' © © # now make another pass of the groups in interm, because some pair © # that may connect two groups (i.e. with one element in one group, © # and second element in another group), yet the pair is simply © # consumed by a group. © # This pass will check if there are any element in any other © # group, if so, such two groups will be unioned. In this pass, we © # move things from interm into fin. fin==final. © fin=[]; fin.append(interm.pop(0)) © 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 © fin.append(group) © © # now turn the dictionaries into lists for return value © result=[]; © for group in fin: result.append(group.keys()) © return result © ------------------- I wrote this (Perl) program in 2003-09, and now basically forgot all about the internals. The original Perl code does not have inline comments, nor public consumable documentation as this is my own project. In the process of translation and the publication and explanation on this page, i eventually have to re-acquaint the algorithm i used as i go thru the lines. I was thinking of a quick brainless translation word-for-word, but that turned out not possible as i run into problems. (While i'm learning Python, i run into frustrations with the Python Documentation. (although it has far more quality than Perl documentations). The frustrations with documentations will be appended to this page later: How to write a tutorial ) The translation problem i run into is this. In Perl, there's a GOTO construct where in a loop one can say "break XYZ" to jump to a arbitrary outer loop labeled XYZ. Python has "break" but does not provide a GOTO jump as in Perl. In the process, i have to actually figure out (for the first time for me) how loops with GOTO jumps can be translated to alternative structure. This turned out not to be too hard. For a GOTO jump to a far outer group, one can use multiple breaks at the end of each loop, possibly in addiction adding a "else" clause to the different levels of the loops. (Python language can have a "else" clause for "for" loops. It is executed when the loop completes. (as opposed to when a break inside jumped out)) Here is a loop with GOTO, translated into Python without: N1: for my $aPair (@pairings) { for my $aGroup (@interm) { if (exists ${$aGroup}{$aPair->[0]}) {${$aGroup}{$aPair->[1]}='x'; next N1} if (exists ${$aGroup}{$aPair->[1]}) {${$aGroup}{$aPair->[0]}='x'; next N1} } push @interm, {$aPair->[0]=>'x'}; ${interm[-1]}{$aPair->[1]}='x'; } ©----------------------------------- © for aPair in pairings: © for aGroup in interm: © if (aGroup.has_key(aPair[0])): aGroup[aPair[1]]='x'; break © if (aGroup.has_key(aPair[1])): aGroup[aPair[0]]='x'; break © else: interm.append( {aPair[0]:'x'} ); interm[-1][aPair[1]]='x' © Below is another such trans-structure, distinct from the above. N2: for my $group (@interm) { for my $newcoup (@fin) { foreach my $k (keys %$group) { if (exists ${$newcoup}{$k}) {map { ${$newcoup}{$_}='x'} (keys %$group); next N2;} } } push @fin, $group; } ©----------------------------------- © 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 © fin.append(group) © The Python version above has not been tested much, but i suppose it is fine since it is basically a copy of the Perl code. The Perl version is fairly reliable, as it went thru the gauntlet of special cases testing and i've used it over the year in the larger program... however no any formal proof or exhaustive machine testing has been done. Later i might write some program to auto-test them... but that'd be another day. The Python version can also use some clean up, or even rewrite as a program in the Python language proper. Addenda or Errata will be added on this page. PS all together there are some 3 or so solutions posted on the newsgroups. (one by private email) I will have to filter them out and study them. Any interesting or important Addenda or Errata will be emailed out later. In addition to being archived here: http://xahlee.org/perl-python/partition_by_equiv.html Xah [EMAIL PROTECTED] http://xahlee.org/PageTwo_dir/more.html -- http://mail.python.org/mailman/listinfo/python-list