Cách tốt nhất để dịch phương pháp python đệ quy này thành Java là gì?

Question

Trong another question Tôi đã được cung cấp một câu trả lời tuyệt vời liên quan đến việc tạo ra các bộ nhất định cho vấn đề Người đưa thư Trung Quốc.

Câu trả lời được cung cấp là:

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 

chí này ra mong muốn kết quả của:

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

Điều này thực sự cho thấy ngoài khơi biểu cảm của Python vì đây là gần như chính xác làm thế nào tôi sẽ viết các giả -code cho thuật toán. Tôi đặc biệt thích việc sử dụng năng suất và cách mà các bộ đó được coi là công dân hạng nhất.

Tuy nhiên, có vấn đề nằm ở đó.

Cách tốt nhất để:

1.Sửa đổi chức năng của cấu trúc trả về lợi nhuận trong Java? Thay vào đó, nó sẽ là tốt nhất để duy trì một danh sách và nối thêm một phần kết quả của tôi vào danh sách này? Bạn sẽ xử lý từ khóa lợi nhuận như thế nào.

2. Xử lý giao dịch với các bộ? Tôi biết rằng tôi có lẽ có thể sử dụng một trong các bộ sưu tập Java mà triển khai thực hiện giao diện Set và sau đó sử dụng những thứ như removeAll() để cho tôi một sự khác biệt thiết lập. Đây có phải là những gì bạn sẽ làm trong trường hợp đó?

Cuối cùng, tôi đang tìm cách giảm phương pháp này thành một cách ngắn gọn và đơn giản nhất có thể trong Java. Tôi nghĩ kiểu trả về của phiên bản java của phương thức này có thể sẽ trả về một danh sách các mảng int hoặc một cái gì đó tương tự.

Bạn sẽ xử lý các tình huống ở trên khi chuyển đổi phương thức này sang Java như thế nào?

Answer 1

Để dịch một hàm máy phát điện sang Java, bạn phải thực hiện lại nó dưới dạng Iterable + Iterator. Ví dụ .:

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

trở thành (cảnh báo: mã không được kiểm tra):

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

Đối với bộ Tôi thực sự sẽ sử dụng java.util.HashSet.

Answer 2

Có thể bạn muốn chạy trên JVM. Tại sao không sử dụng Scala?

Tôi nghĩ bạn có thể dịch mã python thành hầu như cùng một loại mã trong scala. Tốt hơn nhiều sau đó là công cụ java dài dòng. Và đó là bytecode jvm cuối cùng sẽ dễ dàng hòa trộn/hợp tác với ứng dụng java của bạn.

Answer 3

Đây không phải là những gì bạn yêu cầu, nhưng tôi muốn thử nó ra, vì vậy đây là một giải pháp trong C# sử dụng 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); 
} 

Không thực sự trở lại cặp, chỉ cần ra lệnh danh sách các số nguyên, nhưng cắt nó lên bởi twos sau khi điều này là dễ dàng. Ngoài ra, tốt đẹp để thấy rằng C# có thể cạnh tranh với conciseness của Python.
Kiểm tra nó ra:

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

Và kết quả:

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

tín dụng để Noldorin's answer đến một câu hỏi LINQ cho một số ý tưởng.