¿Cuál es la mejor manera de traducir este método recursivo de python a Java?

Question

En another question recibí una gran respuesta que implicaba la generación de ciertos conjuntos para el problema del cartero chino.

La respuesta siempre era:

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 

Esta es la salida el resultado deseo de:

[(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)] 

Esto realmente muestra la expresividad de Python, porque esto es casi exactamente cómo iba a escribir el seudo -code para el algoritmo. Me gusta especialmente el uso del rendimiento y la forma en que los conjuntos se tratan como ciudadanos de primera clase.

Sin embargo, ahí radica mi problema.

¿Cuál sería la mejor manera:

1.Duplicate la funcionalidad del yield return construir en Java? ¿Sería mejor mantener una lista y anexar mis resultados parciales a esta lista? ¿Cómo manejarías la palabra clave yield?

2. ¿Manejar el manejo de los juegos? Sé que probablemente podría usar una de las colecciones de Java que implemente que implementa la interfaz Set y luego usar cosas como removeAll() para darme una diferencia establecida. ¿Es esto lo que harías en ese caso?

En última instancia, estoy tratando de reducir este método de la manera más concisa y directa posible en Java. Estoy pensando que el tipo de devolución de la versión java de este método probablemente devuelva una lista de matrices en int o algo similar.

¿Cómo manejarías las situaciones anteriores al convertir este método en Java?

Answer 1

Para traducir una función del generador a Java, tiene que volver a implementarla como Iterable + Iterador. Ej .:

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

Se convierte en (advertencia: el código no se ha probado):

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

Para los conjuntos de hecho yo usaría java.util.HashSet.

Answer 2

Probablemente desee ejecutarlo en una JVM. ¿Por qué no usar Scala?

Creo que puede traducir el código python en casi el mismo tipo de código en scala. Mucho mejor que las cosas detalladas de Java. Y es jvm bytecode al final que se integrará fácilmente/cooperará con su aplicación java.

Answer 3

Esto no es lo que pidieron, pero quería probarlo, así que aquí tiene una solución en C# usando 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); 
} 

no vuelven en realidad pares, acaba de pedir listas de números enteros, pero cortarlo de a dos después de esto es fácil. Además, es bueno ver que C# puede rivalizar con la concisión de Python.
prueba a cabo:

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

Y la salida:

[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] 

crédito a Noldorin's answer a otra pregunta LINQ para algunas ideas.