Python, Perl: Combinatorics Function Example
In 2003 i wrote the following Perl program as part of a larger program. As a exercise of fun, let's do a Python version. (Python solution below)
Perl
# -*- coding: utf-8 -*- # perl =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::Dumper; print Dumper combo(4);
Python
Here's the Python version. Sweet.
# -*- coding: utf-8 -*- # python 2 def combo (n): '''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. For example, 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)}''' result={} for j in range(1,n): for i in range(1,n+1): m = ((i+j)-1) % n + 1 if (i < m): result["%d,%d"%(i,m)]=(i,m) return result print combo(4)
The algorithm used in above codes can be improved. Here is one by David Eppstein, using a “list comprehension” syntax in Python.
def combo2(n): return dict([('%d,%d'%(i,j),(i,j)) for j in range(1,n+1) for i in range(1,j)])
For more about this syntax, see: List Comprehension .
Java
For a Java version, see: Java Tutorial: A Combinatorics Function .