Làm thế nào để tạo ra sản phẩm Descartes qua các nhóm số ngẫu nhiên trong Java?

Question

Hãy nói rằng tôi có 2 nhóm số:

{1, 2, 3}, 
{4, 5} 

Tôi muốn tạo ra một thuật toán (trong Java) mà kết quả đầu ra 6 kết hợp sau đây:

1,4 
1,5 
2,4 
2,5 
3,4 
3,5 

Có thể có một số tùy ý của các nhóm và số lượng thành viên tùy ý trong mỗi nhóm. Vì vậy, trong ví dụ trên, có 2 nhóm với nhóm đầu tiên có 3 thành viên và nhóm thứ hai có 2 thành viên. Một ví dụ khác là sau (3 nhóm, 3 thành viên trong nhóm đầu tiên và 2 thành viên trong nhóm thứ hai và thứ ba):

{1, 2, 3}, 
{4, 5}, 
{6, 7} 

Trong đó sẽ mang lại 12 kết hợp sau đây:

1,4,6 
1,4,7 
1,5,6 
1,5,7 

2,4,6 
2,4,7 
2,5,6 
2,5,7 

3,4,6 
3,4,7 
3,5,6 
3,5,7 

Làm thế nào tôi có thể làm điều này trong Java? Tôi đang cố gắng sử dụng đệ quy và tôi đã xem xét một số similar question nhưng tôi vẫn sắp ra mắt. Cảm ơn đã giúp đỡ! (P.S. đây không phải là cho một bài tập về nhà)

Answer 1

Got một chút buồn chán và quyết định để cho nó một shot. Nên được chính xác những gì bạn cần:

public static void main(String args[]) { 

    ArrayList<int[]> input = new ArrayList<int[]>(); 
    input.add(new int[] { 1, 2, 3 }); 
    input.add(new int[] { 4, 5 }); 
    input.add(new int[] { 6, 7 }); 

    combine(input, new int[input.size()], 0); 
} 

private static void combine(ArrayList<int[]> input, int[] current, int k) { 

    if(k == input.size()) { 
     for(int i = 0; i < k; i++) { 
      System.out.print(current[i] + " "); 
     } 
     System.out.println(); 
    } else {    
     for(int j = 0; j < input.get(k).length; j++) { 
      current[k] = input.get(k)[j]; 
      combine(input, current, k + 1); 
     }  
    } 
} 

Answer 2

Một cách tiếp cận có thể (không nhất thiết là hiệu quả nhất) có thể là để có một cách tiếp cận phân chia và chinh phục. Nó tương đối đơn giản để tìm tất cả các hoán vị của hai nhóm (cách ngu ngốc nhất chỉ là lồng nhau cho các vòng lặp). Giả sử bạn viết một hàm có tên là permute và nó permute(A,B) trong đó A (ví dụ {(1), (2), (3)}) và B (ví dụ {(4), (5)} là các nhóm số và trả về tất cả các hoán vị của A & B là một nhóm đơn (ví dụ: {(1,4), (1,5), (2,4), (2,5), (3,4), (3,5) })

Vì vậy, khi bạn có N nhóm thay vì 2, điều dễ nhất cần làm là chỉ cần chọn ra một phần nhỏ của vấn đề.Hãy nói rằng bạn có nhóm A, B và C. Thay vì lo lắng về tất cả chúng một cách riêng biệt , bạn có thể nghĩ về nó như một cái gì đó như:

permute(permute(A,B),C)

Tìm tất cả các hoán vị của A và B đầu tiên. Một khi bạn có kết quả rằng, tất cả các hoán vị của kết quả đó với C. Và bốn nhóm A, B, C, D có thể trông giống như:

permute(permute(permute(A,B),C),D)

Và vân vân. Tại mỗi bước trên đường đi, bạn lấy kết quả hoán vị hiện tại và hoán đổi nó với nhóm tiếp theo trong danh sách các nhóm mà bạn nhận làm đầu vào. Bạn chỉ bao giờ kết hợp hai nhóm tại một thời điểm, vì vậy thuật toán không phải thay đổi tùy thuộc vào số lượng nhóm bạn nhận được làm đầu vào.

Khi bạn đang thực hiện đệ quy, có một vài câu hỏi lớn bạn cần phải trả lời:

1. Bạn có thể đệ quy phá vỡ vấn đề thành vấn đề nhỏ hơn, giải quyết được nhiều hơn? Tôi nghĩ rằng các ví dụ trên chứng minh rằng bạn có thể.

2. Trường hợp cơ sở là gì? Giải pháp nào khiến cho việc đệ quy dừng lại và thư giãn? Nó thường phải là một cái gì đó thực sự đơn giản mà đệ quy của bạn có thể làm việc theo hướng. Trong trường hợp này, nó có thể xuống đến một cái gì đó như permute(A,{}) trong đó {} là tập rỗng.

3. Trường hợp đệ quy là gì?Làm thế nào bạn sẽ phá vỡ một đoạn của vấn đề và recurse trên một tập hợp con nhỏ của vấn đề? Tôi nghĩ rằng lời giải thích ban đầu mang lại cho bạn một cách để làm điều này. Chỉ cần phá vỡ một nhóm tại một thời điểm và hoán đổi nó với kết quả ngày càng phát triển của bạn.

Chắc chắn có những giải pháp khác cho vấn đề này, đây chỉ là giải pháp đầu tiên xuất hiện trong đầu tôi. Khi N trở nên lớn hơn và lớn hơn, thuật toán này sẽ bị chậm quá mức vì nó không hiệu quả lắm.

Vì vậy, ngay cả khi bạn không sử dụng giải pháp này, tôi hy vọng nó giúp bạn đi đúng hướng!

Answer 3

Làm thế nào về mã giả sau (w/o đệ quy)

// Create the initial result filled with the first set of numbers 
List result = new List() 
For each number in the first set 
    result.add(new List(number)) 

// Iterate over the following sets to permutate over 
For each remaining set S 
    List newResult = new List() 
    For each list L in result 
    For each number N in S 
     newResult.add(copy of L with N added) 
    result = newResult 

Answer 4

Nếu bạn có thể sử dụng thư viện, Guava'sSets.cartesianProduct(List<Set<E>>) không chính xác những gì bạn đang tìm kiếm. (Tiết lộ: Tôi đóng góp cho ổi.)