Каков наилучший способ перевести этот рекурсивный метод python в Java?

Question

В другой вопрос Мне был предоставлен отличный ответ, включающий генерацию определенных наборов для задачи китайского почтальона.

Ответ был следующий:

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

выдаст желаемый результат:

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

Это действительно демонстрирует выразительность Python, потому что это почти точно так, как я бы написал псевдокод для алгоритма.Мне особенно нравится использование yield и способа, которым наборы рассматриваются как первоклассные граждане.

Однако в этом и заключается моя проблема.

Что было бы лучшим способом:

1.Дублировать функциональность конструкции yield return в Java?Вместо этого было бы лучше сохранить список и добавить мои частичные результаты в этот список?Как бы вы справились с ключевым словом yield.

2. Обращаться с сетами?Я знаю, что мог бы, вероятно, использовать одну из коллекций Java, которая реализует интерфейс Set, а затем использовать такие вещи, как removeAll (), чтобы дать мне разницу в наборе.Это то, что вы будете делать в этом случае?

В конечном счете, я собираюсь свести этот метод к как можно более кратким и понятным способам в Java.Я думаю, что возвращаемый тип java-версии этого метода, скорее всего, вернет список массивов int или что-то подобное.

Как бы вы справились с описанными выше ситуациями при преобразовании этого метода в Java?

Answer 1

Чтобы перевести функцию генератора в Java, вам нужно переопределить ее как Iterable + Iterator. E.g.:

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

Становится (предупреждение: код не тестируется):

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

Для наборов я бы действительно использовал java.util.HashSet.

Answer 2

Возможно, вы хотите запустить его на JVM. Почему бы не использовать Scala?

Я думаю, вы можете перевести код на python в почти такой же код в scala. Гораздо лучше, чем многословный Java материал. В конце концов, это байт-код jvm, который будет легко сочетаться с вашим Java-приложением.

Answer 3

Это не то, что вы просили, но я хотел попробовать, поэтому вот решение на C # с использованием 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);
}

На самом деле не возвращает пары, только упорядоченные списки целых чисел, но разрезать его по двое после этого легко. Также приятно видеть, что C # может соперничать с лаконичностью Python.
Тестирование:

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

И вывод:

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

Благодарю Ответ Нолдорина на другой вопрос LINQ за некоторые идеи.