What is the best way to translate this recursive python method into Java?

Question

In another question I was provided with a great answer involving generating certain sets for the Chinese Postman Problem.

The answer provided was:

def get_pairs(s):
    if not s: yield []
    else:
        i = min(s)
        for j in s - set([i]):
           for r in get_pairs(s - set([i, j])):
               yield [(i, j)] + r

for x in get_pairs(set([1,2,3,4,5,6])):
    print x

This will output the desire result of:

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

This really shows off the expressiveness of Python because this is almost exactly how I would write the pseudo-code for the algorithm. I especially like the usage of yield and and the way that sets are treated as first class citizens.

However, there in lies my problem.

What would be the best way to:

1.Duplicate the functionality of the yield return construct in Java? Would it instead be best to maintain a list and append my partial results to this list? How would you handle the yield keyword.

2.Handle the dealing with the sets? I know that I could probably use one of the Java collections which implements that implements the Set interface and then using things like removeAll() to give me a set difference. Is this what you would do in that case?

Ultimately, I'm looking to reduce this method into as concise and straightforward way as possible in Java. I'm thinking the return type of the java version of this method will likely return a list of int arrays or something similar.

How would you handle the situations above when converting this method into Java?

Answer 1

In order to translate a generator function to Java you have to reimplement it as a Iterable+Iterator. E.g.:

def foo(x):
   for i in xrange(10):
      yield x * i
...
for x in foo(5):
   print(x)

Becomes (warning: code is not tested):

import java.util.Iterator;
import java.util.Iterable;

class Foo implements Iterable<Integer> {
   public final int x;

   public Foo(int x) {
      this.x = x;
   }

   public Iterator<Integer> iterate() {
      return new Iterator<Integer> {
         int i = 0;

         public boolean hasNext() {
            return i < 10;
         }

         public Integer next() {
            return x * (i ++);
         }
      };
   }
}
...
for (int x : new Foo(5)) {
   System.out.println(x);
}

For the sets I would indeed use java.util.HashSet.

Answer 2

You probably want to run it on a JVM. Why not use Scala?

I think you can translate the python code into almost the same kind of code in scala. Much better then the verbose java stuff. And it's jvm bytecode in the end which will easily blend in/cooperate with your java app.

Answer 3

This isn't what you asked for, but I wanted to try it out, so here's a solution in C# using LINQ:

static IEnumerable<IEnumerable<int>> getPairs(IEnumerable<int> list)
{
    if (!list.Any())
        return new [] { new int[0] };

    var first = list.First();
    return from second in list.Skip(1)
           from pair in getPairs(list.Skip(1).Where(rest => rest != second))
           select Enumerable.Concat(new [] { first, second }, pair);
}

Doesn't actually return pairs, just ordered lists of integers, but chopping it up by twos after this is easy. Also, nice to see that C# can rival the conciseness of Python.
Testing it out:

foreach (var p in getPairs(new [] { 1, 2, 3, 4, 5, 6 }))
    Console.WriteLine("[" + 
        String.Join(",", p.Select(i => i.ToString()).ToArray()) + "]");

And the output:

[1,2,3,4,5,6]
[1,2,3,5,4,6]
[1,2,3,6,4,5]
[1,3,2,4,5,6]
[1,3,2,5,4,6]
[1,3,2,6,4,5]
[1,4,2,3,5,6]
[1,4,2,5,3,6]
[1,4,2,6,3,5]
[1,5,2,3,4,6]
[1,5,2,4,3,6]
[1,5,2,6,3,4]
[1,6,2,3,4,5]
[1,6,2,4,3,5]
[1,6,2,5,3,4]

Credit to Noldorin's answer to another LINQ question for some ideas.