Combinatorics Function Example in Perl and Python

Xah Lee, 2005-02

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

=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);

Here's the Python version. So sweet.

# -*- coding: utf-8 -*-
# Python

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. 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)}'''
    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)

For a Java version, see http://xahlee.org/java-a-day/combinatorics.html

2005-02-11 Addendum:

Note that 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.html

Page created: 2005-02.
© 2005 by Xah Lee.