Code Fun: Generate All Possible 2-Tuple

Problem

write a function combo(n), return given all possible pairs. order in the pair does not matter.

e.g. combo(4) returns

[(3, 4), (1, 4), (1, 2), (1, 3), (2, 4), (2, 3)]

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

use Data::Dumper;
 $Data::Dumper::Indent = 0;

=pod

combo(n) returns a collection with elements of pairs that is all possible combinations of 2 things from n.

e.g. 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;
}

print Dumper combo(4);
# $VAR1 = {'3,4' => [3,4],'2,3' => [2,3],'1,4' => [1,4],'1,3' => [1,3],'2,4' => [2,4],'1,2' => [1,2]};

Python

Here's the Python version. Sweet.

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

The algorithm used in above codes can be improved. Here is one by David Eppstein http://www.ics.uci.edu/~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 .