Python, Perl: Combinatorics Function Example

By Xah Lee. Date:

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 .