8

在另一个问题中，我得到了一个很好的答案，涉及为中国邮递员问题生成某些集合。

提供的答案是：

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.在Java中复制yield return构造的功能？最好保留一个列表并将我的部分结果附加到该列表中吗？您将如何处理 yield 关键字。

2.Hand 处理套组？我知道我可能会使用其中一个实现 Set 接口的 Java 集合，然后使用 removeAll() 之类的东西来给我一个集合差异。在那种情况下你会这样做吗？

最终，我希望在 Java 中将此方法简化为尽可能简洁和直接的方式。我在想这个方法的java版本的返回类型可能会返回一个int数组列表或类似的东西。

将此方法转换为 Java 时，您将如何处理上述情况？

4

3 回答 3

2

为了将生成器函数转换为 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。

于 2010-04-27T22:58:33.927 回答
1

您可能希望在 JVM 上运行它。为什么不使用 Scala？

我认为您可以将 python 代码翻译成 scala 中几乎相同类型的代码。比冗长的java东西要好得多。最后它是 jvm 字节码，可以轻松地与您的 java 应用程序融合/合作。

于 2010-04-29T07:10:55.937 回答
0

这不是您要求的，但我想尝试一下，所以这里有一个使用 LINQ 的 C# 解决方案：

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]

归功于Noldorin对另一个 LINQ 问题的一些想法的回答。

于 2010-04-30T23:13:11.550 回答