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の表現力を実際に示しています。これは、アルゴリズムの擬似コードを作成する方法とほぼ同じだからです。私は特に、利回りの使い方と、セットが一級市民として扱われる方法が好きです。

しかし、そこに私の問題があります。

次の方法が最適です。

1.Javaでyieldreturn構文の機能を複製しますか？代わりに、リストを維持し、私の部分的な結果をこのリストに追加するのが最善でしょうか？歩留まりキーワードをどのように処理しますか。

2.セットの取り扱いは？Setインターフェイスを実装するJavaコレクションの1つを使用してから、removeAll（）などを使用してセットの違いを得ることができると思います。その場合、これはあなたがすることですか？

最終的に、私はこのメソッドをJavaで可能な限り簡潔でわかりやすい方法に減らすことを目指しています。このメソッドのJavaバージョンのreturnタイプは、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);
}

実際にはペアを返しません。整数の順序付きリストを返すだけですが、これ以降は2で切り刻むのは簡単です。また、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質問に対するNoldorinの回答の功績によるものです。

于 2010-04-30T23:13:11.550 に答える