Что лучший способ состоит в том, чтобы перевести этот рекурсивный метод Python в Java?
В другом вопросе мне предоставили большое вовлечение ответа, генерирующее определенные наборы для китайской проблемы Почтальона.
Предоставленный ответ был:
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, потому что это почти точно, как я записал бы псевдокод для алгоритма. Мне особенно нравится использование урожая и и способ, которым наборы рассматривают как граждан первого класса.
Однако там во лжи моя проблема.
Что было бы лучшим способом к:
1. Копировать функциональность конструкции возврата урожая в Java? Вместо этого было бы лучше вести список и добавить мои частичные результаты к этому списку? Как Вы обработали бы ключевое слово урожая.
2. Обработать контакт с наборами? Я знаю, что мог, вероятно, использовать один из наборов Java, который реализует, который реализует интерфейс Set и затем использование вещей как removeAll (), чтобы дать мне разность множеств. Это то, что Вы сделали бы в этом случае?
В конечном счете я надеюсь уменьшать этот метод в максимально краткий и простой путь в Java. Я думаю, что тип возврата версии Java этого метода, вероятно, возвратит список международных массивов или чего-то подобного.
Как Вы обработали бы ситуации выше при преобразовании этого метода в Java?
3 ответа
Для того, чтобы перевести функцию-генератор на Java, вы должны перереализовать ее как Iterable+Iterator. Например:
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.
Вы, вероятно, захотите запустить его на JVM. Почему бы не использовать Scala?
Я думаю, что вы можете перевести код Python в почти такой же код в scala. Намного лучше, чем многословный Java-материал. В конце концов, это байт-код jvm, который будет легко смешиваться / взаимодействовать с вашим java-приложением.
Это не то, что вы просили, но я хотел попробовать, поэтому вот решение на 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 для некоторых идей.