Was ist der beste Weg, um diese rekursive Python-Methode in Java zu übersetzen?

Question

In another question wurde mir eine große Antwort zur Verfügung gestellt, die bestimmte Sätze für das chinesische Postman-Problem erzeugt.

Die Antwort zur Verfügung gestellt wurde:

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 

Dies wird Ausgang des Wunsch Ergebnis:

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

Dies zeigt wirklich die Ausdruckskraft Python ab, weil dies fast genau ist, wie ich die Pseudo schreiben würde -code für den Algorithmus Ich mag besonders die Verwendung von Rendite und die Art und Weise, wie Sets als erstklassige Bürger behandelt werden.

Allerdings liegt da mein Problem.

1.Duplicate die Funktionalität der yield return-Konstrukt in Java: zu

Was wäre der beste Weg? Wäre es stattdessen besser, eine Liste zu führen und meine Teilergebnisse an diese Liste anzuhängen? Wie würden Sie mit dem Keyword Yield umgehen?

2.Handle den Umgang mit den Sätzen? Ich weiß, dass ich wahrscheinlich eine der Java-Sammlungen verwenden könnte, die implementiert, die die Set-Schnittstelle implementiert und dann Dinge wie removeAll() verwendet, um mir einen Set-Unterschied zu geben. Würden Sie das in diesem Fall tun?

Letztendlich versuche ich, diese Methode in Java so übersichtlich wie möglich zu machen. Ich denke, der Rückgabetyp der Java-Version dieser Methode wird wahrscheinlich eine Liste von int-Arrays oder etwas ähnliches zurückgeben.

Wie würden Sie mit den obigen Situationen umgehen, wenn Sie diese Methode in Java konvertieren?

Answer 1

Um eine Generatorfunktion in Java zu übersetzen, müssen Sie sie als Iterable + Iterator neu implementieren. Z.B .:

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

Wird (Warnung: Code wird nicht geprüft):

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

Für die Sets, die ich in der Tat java.util.HashSet verwenden würde.

Answer 2

Sie möchten es wahrscheinlich auf einer JVM ausführen. Warum nicht Scala benutzen?

Ich denke, dass Sie den Python-Code in fast die gleiche Art von Code in Scala übersetzen können. Viel besser als das ausführliche Java-Zeug. Und es ist jvm Bytecode am Ende, die leicht in Ihre Java-App integrieren/kooperieren wird.

Answer 3

Dies ist nicht das, was Sie gefragt, aber ich wollte es ausprobieren, so ist hier eine Lösung in C# LINQ mit:

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

Haben Paare nicht wirklich zurückkehren, bestellt nur Listen von ganzen Zahlen, aber zu zweit zu schneiden, nachdem dies einfach ist. Es ist auch schön zu sehen, dass C# mit der Prägnanz von Python konkurrieren kann.
Testen Sie es aus:

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

Und die Ausgabe:

[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 Noldorin's answer auf eine andere LINQ Frage für einige Ideen.