Qual è il modo migliore per tradurre questo metodo Python ricorsivo in Java?

Question

In another question Mi è stata fornita una grande risposta che comporta la generazione di determinati set per il Problema postino cinese.

La risposta fornita è stata:

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 

Questa volontà di uscita il risultato desiderio:

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

questa mostra davvero fuori l'espressività di Python, perché questo è quasi esattamente come vorrei scrivere la pseudo codice per l'algoritmo. Mi piace soprattutto l'utilizzo della resa e il modo in cui i set vengono trattati come cittadini di prima classe.

Tuttavia, nel mio caso, il mio problema.

Quale sarebbe il modo migliore per:

1.Duplicate la funzionalità del ritorno resa costruire in Java? Sarebbe preferibile invece mantenere una lista e aggiungere i risultati parziali a questa lista? Come gestiresti la parola chiave yield.

2. Gestire la gestione dei set? So che probabilmente potrei usare una delle collezioni Java che implementa l'implementazione dell'interfaccia Set e quindi usare cose come removeAll() per darmi una differenza di set. È questo che vorresti fare in quel caso?

In definitiva, sto cercando di ridurre questo metodo in modo più conciso e diretto possibile in Java. Sto pensando che il tipo restituito della versione java di questo metodo probabilmente restituirà una lista di array int o qualcosa di simile.

Come gestireste le situazioni precedenti quando convertite questo metodo in Java?

Answer 1

Per tradurre una funzione generatore in Java, è necessario reimplementarla come Iterable + Iterator. Es .:

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

diventa (attenzione: il codice non è testato):

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

per i set avrei realmente usare java.util.HashSet.

Answer 2

Probabilmente si desidera eseguirlo su una JVM. Perché non usare Scala?

Penso che si possa tradurre il codice Python in quasi lo stesso tipo di codice in scala. Molto meglio della roba verbosa di Java. Ed è il bytecode jvm alla fine che si confonderà facilmente/coopererà con la tua app java.

Answer 3

Questo non è quello che hai chiesto, ma ho voluto provare, quindi ecco una soluzione in C# utilizzando 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); 
} 

in realtà non tornare coppie, appena ordinato liste di numeri interi, ma smantellarlo a due dopo questo è facile. Inoltre, è bello vedere che C# può competere con la concisione di Python.
Test it out:

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

E l'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] 

credito per Noldorin's answer ad un'altra domanda LINQ per alcune idee.