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?

Unfortunately, Java has nothing resembling `yield`. You could approximate it with threads and message-passing, but the result would be cumbersomse, extremely inefficient and probably not in the spirit of the task at hand. — Marcelo Cantos, Apr 27 '10 at 22:28
Semantically, a Python generator is a separate thread of execution that bidirectionally communicates with its parent thread via the yield statement. In reality, generators are implemented in a smarter and much faster way that doesn't involve threads, but that's just an implementation detail. There's nothing to stop you from implementing generators using real threads, and in Java, that is pretty much the only way to achieve the desired effect. — Marcelo Cantos, Apr 27 '10 at 22:46
how is yield a thread?? it's just appending to a list and then returning it. Am I missing something?? — MK., Apr 27 '10 at 23:04
@Marcelo Cantos I don't see how could it be a thread if it needs to wait the generator to return a value to proceed. Please, could you elaborate more or give an example/link ? — Beothorn, Apr 28 '10 at 11:27
@Lucass, generators can be implemented using Java threads with two `BlockingQueue`s. Yield is implemented as a push onto the first queue followed by a get on the second queue. The next and send methods of Python's generator objects are implemented by doing a get on the first queue followed by a push on the second queue. There is obviously quite a bit more detail to sort out, but that's the essence of it. — Marcelo Cantos, Apr 28 '10 at 11:52
@MK, Python generators and the `yield` statement have nothing to do with populating lists. When `yield` is invoked, flow of control jumps back to the code that called the `get_pairs` function, and doesn't resume until the calling code invokes `next`. This is the only way stuff gets back to the caller; `get_pairs` doesn't return anything, in the normal sense. — Marcelo Cantos, Apr 28 '10 at 11:55
Did you consider to implement it in scala, and call scala from java? — user unknown, Apr 29 '10 at 01:52

score 2 · Accepted Answer · answered Apr 27 '10 at 22:58

2

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.

answered Apr 27 '10 at 22:58

panzi

7,517
5
42
54

1

Wow. Java is actually pretty verbose ;) – BalusC Apr 27 '10 at 23:01
1

that's why i hate it when people are mixing java/c# with functional programming. It looks bad. Why would you translate that simple loop into this Java monstrosity? – MK. Apr 28 '10 at 01:22
@MK C# has much better support for FP'ish type behavior. In this case C# would have been an easier conversion. – Corey Sunwold Apr 28 '10 at 03:04
1

@MK, Python generators aren't a functional programming concept. They are an efficient way to implement coroutines, which are a kind of constrained model of concurrency. They aren't as flexible as threads or processes, but they very efficiently solve a large and important subset of concurrency problems. A key advantage of this model is that you can consume and produce large, and even nominally infinite streams of data while consuming O(1) space, which isn't possible if you process things with lists. How would you implement the OP's code for a large input set that generated ten billion answers? – Marcelo Cantos Apr 28 '10 at 12:03
1

@Marcelo Cantos: And that's exactly what you can do in lazy *functional* languages like Haskell. There *everything* is lazy per default. – panzi Apr 28 '10 at 17:32
Just this is not sufficient for what op asked. – Beothorn Apr 28 '10 at 17:33
@panzi, you'll have no disagreement from me. I wasn't saying that functional language can't do this, merely that coroutines aren't a functional programming concept, _per se_. Of course they can solve these problems, but they do so by returning infinite (lazy) lists. – Marcelo Cantos Apr 28 '10 at 22:08
@MK: C# actually handles it pretty well ;) see my answer. – tzaman Apr 30 '10 at 23:32

score 1 · Answer 2 · answered Apr 29 '10 at 07:10

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.

score 0 · Answer 3 · edited May 23 '17 at 12:31

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.

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

3 Answers3