Thuật toán để có được tất cả các kết hợp của kích thước n từ một mảng (Java)?

Question

Ngay bây giờ tôi đang cố gắng viết một hàm lấy một mảng và một số nguyên n, và đưa ra một danh sách kết hợp mỗi kích thước n (do đó, một danh sách các mảng int). Tôi có thể viết nó bằng cách sử dụng n vòng lặp lồng nhau, nhưng điều này chỉ hoạt động cho một kích thước cụ thể của tập hợp con. Tôi không thể tìm ra cách tổng quát hóa nó để làm việc cho bất kỳ kích thước kết hợp nào. Tôi nghĩ rằng tôi cần phải sử dụng đệ quy?

Đây là mã cho tất cả các kết hợp của 3 yếu tố và tôi cần một thuật toán cho bất kỳ số lượng yếu tố nào.

import java.util.List; 
import java.util.ArrayList; 

public class combinatorics{ 
    public static void main(String[] args) { 

     List<int[]> list = new ArrayList<int[]>(); 
     int[] arr = {1,2,3,4,5}; 
     combinations3(arr,list); 
     listToString(list); 
    } 

    static void combinations3(int[] arr, List<int[]> list){ 
     for(int i = 0; i<arr.length-2; i++) 
      for(int j = i+1; j<arr.length-1; j++) 
       for(int k = j+1; k<arr.length; k++) 
        list.add(new int[]{arr[i],arr[j],arr[k]}); 
    } 

    private static void listToString(List<int[]> list){ 
     for(int i = 0; i<list.size(); i++){ //iterate through list 
      for(int j : list.get(i)){ //iterate through array 
       System.out.printf("%d ",j); 
      } 
     System.out.print("\n"); 
     } 
    } 
} 

Answer 1

Đây là vấn đề được nghiên cứu kỹ về việc tạo tất cả các tập con k, hoặc k-combinations, có thể dễ dàng thực hiện mà không cần đệ quy.

Ý tưởng là để có mảng có kích thước k giữ chuỗi các chỉ số của các yếu tố từ mảng đầu vào (mà là những con số 0-n - 1) trong thứ tự tăng dần. (Tập hợp con sau đó có thể được tạo bằng cách lấy các mục theo các chỉ mục này từ mảng ban đầu.) Vì vậy, chúng ta cần tạo tất cả các chuỗi chỉ mục như vậy.

Trình tự chỉ mục đầu tiên sẽ là [0, 1, 2, ... , k - 1], ở bước thứ hai, chuyển sang [0, 1, 2,..., k], sau đó đến [0, 1, 2, ... k + 1] v.v. Chuỗi có thể có cuối cùng sẽ là [n - k, n - k + 1, ..., n - 1].

Trên mỗi bước, thuật toán tìm mục gần nhất với mục cuối có thể được tăng lên, tăng dần và lấp đầy các mục phù hợp với mục đó.

Để minh họa, hãy xem xét n = 7 và k = 3. chuỗi chỉ số đầu tiên là [0, 1, 2], sau đó [0, 1, 3] và vân vân ... Tại một số điểm chúng tôi có [0, 5, 6]:

[0, 5, 6] <-- scan from the end: "6" cannot be incremented, "5" also, but "0" can be 
[1, ?, ?] <-- "0" -> "1" 
[1, 2, 3] <-- fill up remaining elements 

next iteration: 

[1, 2, 3] <-- "3" can be incremented 
[1, 2, 4] <-- "3" -> "4" 

Như vậy, [0, 5, 6] Tiếp theo là [1, 2, 3], sau đó đi [1, 2, 4], vv

Code:

int[] input = {10, 20, 30, 40, 50}; // input array 
int k = 3;        // sequence length 

List<int[]> subsets = new ArrayList<>(); 

int[] s = new int[k];     // here we'll keep indices 
             // pointing to elements in input array 

if (k <= input.length) { 
    // first index sequence: 0, 1, 2, ... 
    for (int i = 0; (s[i] = i) < k - 1; i++); 
    subsets.add(getSubset(input, s)); 
    for(;;) { 
     int i; 
     // find position of item that can be incremented 
     for (i = k - 1; i >= 0 && s[i] == input.length - k + i; i--); 
     if (i < 0) { 
      break; 
     } 
     s[i]++;     // increment this item 
     for (++i; i < k; i++) { // fill up remaining items 
      s[i] = s[i - 1] + 1; 
     } 
     subsets.add(getSubset(input, s)); 
    } 
} 

// generate actual subset by index sequence 
int[] getSubset(int[] input, int[] subset) { 
    int[] result = new int[subset.length]; 
    for (int i = 0; i < subset.length; i++) 
     result[i] = input[subset[i]]; 
    return result; 
} 

Answer 2

Bạn có thể thực hiện điều này với lặp lại.

Dưới đây là một giải pháp mà tính toán bao nhiêu mảng chúng ta nên tạo ra và sau đó xây dựng cho họ sử dụng toán học để tính toán mà mục từ mảng nguồn phải ở trong những gì diễn ra:

public static void combinations(int n, int[] arr, List<int[]> list) { 
    // Calculate the number of arrays we should create 
    int numArrays = (int)Math.pow(arr.length, n); 
    // Create each array 
    for(int i = 0; i < numArrays; i++) { 
     int[] current = new int[n]; 
     // Calculate the correct item for each position in the array 
     for(int j = 0; j < n; j++) { 
      // This is the period with which this position changes, i.e. 
      // a period of 5 means the value changes every 5th array 
      int period = (int) Math.pow(arr.length, n - j - 1); 
      // Get the correct item and set it 
      int index = i/period % arr.length; 
      current[j] = arr[index]; 
     } 
     list.add(current); 
    } 
} 

Cập nhật:

Dưới đây là phiên bản được tối ưu hóa giúp giảm đáng kể số lượng cuộc gọi đến Math.pow

public static void combinations(int n, int[] arr, List<int[]> list) { 
    // Calculate the number of arrays we should create 
    int numArrays = (int)Math.pow(arr.length, n); 
    // Create each array 
    for(int i = 0; i < numArrays; i++) { 
     list.add(new int[n]); 
    } 
    // Fill up the arrays 
    for(int j = 0; j < n; j++) { 
     // This is the period with which this position changes, i.e. 
     // a period of 5 means the value changes every 5th array 
     int period = (int) Math.pow(arr.length, n - j - 1); 
     for(int i = 0; i < numArrays; i++) { 
      int[] current = list.get(i); 
      // Get the correct item and set it 
      int index = i/period % arr.length; 
      current[j] = arr[index]; 
     } 
    } 
} 

Answer 3

Nếu tôi hiểu vấn đề của bạn một cách chính xác, this bài viết dường như chỉ đến những gì bạn đang cố gắng làm.

Để trích dẫn từ bài viết:

Phương pháp 1 (Fix Elements và tái phát)

Chúng tôi tạo ra ‘dữ liệu []’ một mảng tạm thời mà các cửa hàng tất cả các kết quả đầu ra từng người một. Ý tưởng là bắt đầu từ chỉ mục đầu tiên (chỉ số = 0) trong dữ liệu [], một bởi một yếu tố sửa lỗi tại chỉ mục này và lặp lại cho các chỉ mục còn lại. Để mảng đầu vào là {1, 2, 3, 4, 5} và r là 3. Đầu tiên chúng ta sửa 1 tại chỉ số 0 trong dữ liệu [], sau đó lặp lại các chỉ mục còn lại, sau đó chúng ta sửa 2 tại chỉ số 0 và tái diễn. Cuối cùng, chúng tôi sửa 3 và lặp lại cho các chỉ mục còn lại. Khi số phần tử trong dữ liệu [] trở thành bằng r (kích thước của kết hợp ), chúng tôi in dữ liệu [].

Phương pháp 2 (Bao gồm và loại trừ mọi phần tử)

Giống như các phương pháp trên, Chúng tôi tạo ra một mảng dữ liệu tạm thời []. Ý tưởng ở đây tương tự như Tập hợp con số. Chúng tôi từng người một xem xét mỗi phần tử của mảng đầu vào, và tái diễn cho hai trường hợp:

1. Yếu tố được bao gồm trong sự kết hợp hiện tại (Chúng tôi đặt yếu tố trong dữ liệu [] và tăng tiếp theo chỉ số có sẵn trong dữ liệu [])
2. Yếu tố được loại trừ kết hợp hiện tại (chúng tôi không đặt yếu tố và không thay đổi chỉ số)

Khi số phần tử trong dữ liệu [] trở thành bằng r (kích thước của một sự kết hợp ), chúng tôi in nó.