Java Tutorial: A Combinatorics Function

Xah Lee, 2005-02

Just for fun today, let's translate the following Python code to Java.

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

(see below for answer)

↓

Java Version:

import java.util.HashMap;

public class comb {
    static HashMap combo (int n) {
        HashMap result = new HashMap(100);

        for (int j=1; j < n; j++) {
            for (int i=1; i <= n; i++) {
                int m = ((i+j)-1) % n +1;
                if (i < m){ 
                    int[] v= {i,m};
                    result.put(i+","+m,v);
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        HashMap result = new HashMap(100);
        result = combo(5);
        System.out.println(result.toString());
    }
}

Some comments on the java version.

A list of key/value pairs is called HashMap and or HashTable in Java. They are under Java's java.util.* classes among other general list type of datatypes. So, we need to import that. In particular, java.util.HashMap.

See: http://java.sun.com/j2se/1.5.0/docs/api/java/util/HashMap.html

We declared “result” to be a type of HashMap, with initial slots for 100. (HashMap can grow automatically, but the Java lang conspicuously advice to us that room is provided in the HashMap declaration for an initial guess in concern for computers.)

Now, the value of pairs for this HashMap we decided to use a array of 2 slots. That's the “v”. (there's a Vector class under java.util, and it is of variable length. We don't need variable length.)

The next line of interest is «result.put(String.valueOf(i)+ ","+ String.valueOf(m),v);»

the “put(key object, value object)” is a method of HashMap. The key we want to use is a string of the form "m,n". Since m and n are type int, and "," is String, we need to convert them all to string and join them. The String.valueOf is the one to use to convert primitive types to String.

This line can also be written as: «result.put(i+ ","+ m,v);»

Now in the “main” method, again we need to declare a HashMap, to hold the result.

For a Perl version, see http://xahlee.org/perl-python/combinatorics.html

2005-02-11 Addendum: Note that the algorithm for this “2 things out of n” can be improved. Here's a Python code that illustrates:

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 a Java implementation of this algorithm, see: hashmap_equality.html

2005-02