Jaki jest najlepszy sposób na przetłumaczenie tej metody python rekursywny na Java?

Question

W another question otrzymałem wspaniałą odpowiedź, w tym generowanie pewnych zestawów dla problemu chińskiego listonosza.

Odpowiedź warunkiem było:

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 

ten wyświetli wynik pragnienie:

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

To naprawdę popisuje się wyrazistość Python bo to jest prawie dokładnie tak, jak chciałbym napisać pseudo -Kod dla algorytmu. Szczególnie podoba mi się wykorzystanie plonów i sposób, w jaki zestawy te są traktowane jako pierwszorzędni obywatele.

Jednak mój problem leży w kłamstwie.

Jaki byłby najlepszy sposób:

1.Duplicate funkcjonalność zamian plastyczności skonstruować w Java? Czy zamiast tego najlepiej będzie utrzymywać listę i dołączać moje częściowe wyniki do tej listy? Jak poradzisz sobie ze słowem kluczowym yield.

2.Zachowaj postępowanie z zestawami? Wiem, że prawdopodobnie mógłbym użyć jednej z kolekcji Java, która implementuje interfejs Set, a następnie używać rzeczy takich jak removeAll(), aby dać mi ustawioną różnicę. Czy to właśnie zrobiłbyś w tym przypadku?

Koniec końców, staram się zredukować tę metodę w sposób tak zwięzły i bezpośredni, jak to możliwe w Javie. Myślę, że zwracany typ wersji java tej metody prawdopodobnie zwróci listę tablic int lub coś podobnego.

Jak radziłbyś sobie z powyższymi sytuacjami podczas konwersji tej metody na Javę?

Answer 1

Aby przetłumaczyć funkcję generatora na Javę, należy ją ponownie zastosować jako Iterable + Iterator. Np .:

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

Staje (uwaga: kod nie testowane):

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

dla zbiorów I rzeczywiście mogliby wykorzystać java.util.HashSet.

Answer 2

Prawdopodobnie chcesz uruchomić go na maszynie JVM. Dlaczego nie skorzystać z Scali?

Myślę, że możesz przetłumaczyć kod Pythona na prawie taki sam kod w scala. Znacznie lepiej niż pełne gadżety java. W końcu jest to kod bajtowy jvm, który z łatwością wtopi się w/współpracujesz z aplikacją java.

Answer 3

To nie jest to, co prosiłeś, ale chciałem go wypróbować, więc o to rozwiązanie w C# za pomocą 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); 
} 

faktycznie nie wrócić pary, tylko nakazał listy liczb całkowitych, ale rozdrabnianie go po dwójkach po tym jest łatwe. Również miło widzieć, że C# może rywalizować ze zwięzłością Pythona.
Testowanie go:

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

a wyjście:

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

zgłosił Noldorin's answer do innego pytania LINQ dla niektórych pomysłów.