Velocity Reviews > Perl > [perl-python] combinatorics fun

# [perl-python] combinatorics fun

Xah Lee
Guest
Posts: n/a

 02-10-2005
a year ago i wrote this perl program as part of a larger program.

as a exercise of fun, let's do a python version. I'll post my version
later today.

=pod

combo(n) returns a collection with elements of pairs that is all
possible combinations of 2 things from n. For example, combo(4)
returns {'3,4' => ['3',4],'1,2' => [1,2],'1,3' => [1,3],'1,4' =>
[1,4],'2,3' => ['2',3],'2,4' => ['2',4]}; Hash form is returned
instead of array for this program.

=cut

sub combo (\$) {
my \$max=\$_[0];
my %hh=();
for (my \$j=1; \$j < \$max; ++\$j) {
for (my \$i=1; \$i <= \$max; ++\$i) {
my \$m = ((\$i+\$j)-1)%\$max+1;
if (\$i < \$m){ \$hh{"\$i,\$m"}=[\$i,\$m];}
}
}
return \%hh;
}

use Data:umper;
\$Data:umper::Indent=0;
print Dumper combo(5);

This is Perl-Python a-day. To subscribe, see
http://xahlee.org/perl-python/python.html

Xah
http://www.velocityreviews.com/forums/(E-Mail Removed)
http://xahlee.org/PageTwo_dir/more.html

David Eppstein
Guest
Posts: n/a

 02-10-2005
In article <(E-Mail Removed). com>,
"Xah Lee" <(E-Mail Removed)> wrote:

> combo(n) returns a collection with elements of pairs that is all
> possible combinations of 2 things from n. For example, combo(4)
> returns {'3,4' => ['3',4],'1,2' => [1,2],'1,3' => [1,3],'1,4' =>
> [1,4],'2,3' => ['2',3],'2,4' => ['2',4]}; Hash form is returned
> instead of array for this program.

def combo(n):
return dict([('%d,%d'%(i,j),(i,j))
for j in range(n) for i in range(j)])

import pprint
pprint.pprint(combo(5))

output:

{'0,1': (0, 1),
'0,2': (0, 2),
'0,3': (0, 3),
'0,4': (0, 4),
'1,2': (1, 2),
'1,3': (1, 3),
'1,4': (1, 4),
'2,3': (2, 3),
'2,4': (2, 4),
'3,4': (3, 4)}

Note I'm using 0-based indexing, use range(1,n+1) and range(1,j+1)
instead if you really need it to be 1-based.

Also I'm using Python 2.3, I think in 2.4 you can take out the square
brackets and it would still work.

--
David Eppstein
Computer Science Dept., Univ. of California, Irvine
http://www.ics.uci.edu/~eppstein/

axel@white-eagle.invalid.uk
Guest
Posts: n/a

 02-11-2005
In comp.lang.perl.misc Xah Lee <(E-Mail Removed)> wrote:
> a year ago i wrote this perl program as part of a larger program.

> sub combo (\$) {
> my \$max=\$_[0];
> my %hh=();
> for (my \$j=1; \$j < \$max; ++\$j) {
> for (my \$i=1; \$i <= \$max; ++\$i) {
> my \$m = ((\$i+\$j)-1)%\$max+1;
> if (\$i < \$m){ \$hh{"\$i,\$m"}=[\$i,\$m];}
> }
> }
> return \%hh;
> }

Well, it's not obfuscated Perl. It is, however, an obfuscated algorithm.

Sane people would use something along the lines of:

sub combo {
my \$max = shift;
my %hh=();
for my \$i ( 1 .. \$max ) {
for my \$j ( \$i + 1 .. \$max ) {
\$hh{"\$i,\$j"} = [\$i, \$j];
}
}
return \%hh;
}

Axel

Haibao Tang
Guest
Posts: n/a

 02-11-2005
I am no longer resisting. As time goes, the nausea when I first saw Mr.
Lee's smelly "technical posts" is starting to fade. The discussion
group should have a high tolerance towards polymorphic people these
days.

Xah Lee
Guest
Posts: n/a

 02-11-2005
David Eppstein's code is very nice.

Here's the python version of the perl code:

© '''returns all possible (unordered) pairs out of n numbers 1 to
n.
© Returns a dictionary. The keys are of the form "n,m",
© and their values are tuples. e.g. combo(4) returns
© {'3,4': (3, 4), '1,4': (1, 4), '1,2': (1, 2),
© '1,3': (1, 3), '2,4': (2, 4), '2,3': (2, 3)}'''
© m = ((i+j)-1) % n + 1

So sweet.

Xah
(E-Mail Removed)
http://xahlee.org/PageTwo_dir/more.html

bruno modulix
Guest
Posts: n/a

 02-11-2005
YYUsenet wrote:
> Xah Lee wrote:
>

(snip insanities)
>>

>
> Why are you posting this to comp.lang.python? This obviously has nothing
> to do with python at all. If you are trying to teach people python,
> claiming that "...let's do a python version. I'll post my version later
> today." Isn't really the proper way to do it. An even better method
> would be to set up a website dedicated to nothing but it, and stop
> posting here with garbage code that no one wants to read, and that helps
> no one. Please, consider others a little bit when you go off on your
> wild hope that you might be able to teach other people what you
> obviously know nothing about, teaching people from a language that you
> know nothing about. *PLEASE STOP POSTING*!! *NOBODY WANTS YOU TO POST*!!
>

The guy is an obvious, well-known and self-proclaimed troll. Dont feed
the troll.

--
bruno desthuilliers
ruby -e "print '(E-Mail Removed)'.split('@').collect{|p|
p.split('.').collect{|w| w.reverse}.join('.')}.join('@')"
--