在Java中打印所有可能的nCr組合

Question

我試圖列出nCr的所有可能性，它們是順序無關緊要時的組合。所以5C1有5種可能性：1,2,3,4,5。5C2有10種可能性：1 2，1 3，1 4，1 5，2 3，2 4，2 5，3 4，3 5， 4 5.

我做了打印我想要的r = 2，r = 3和r = 4的函數，我看到了這個模式，但我似乎無法爲變量r創建一個工作方法：

public void printCombinationsChoose2(int n, int k) //for when k = 2 
{ 
    for (int a = 1; a < n; a++) 
    { 
     for (int b = a + 1; b <= n; b++) 
     { 
      System.out.println("" + a + " " + b); 
     } 
    } 
} 

public void printCombinationsChoose3(int n, int k) //for when k = 3 
{ 
    for (int a = 1; a < n - 1; a++) 
    { 
     for (int b = a + 1; b < n; b++) 
     { 
      for (int c = b + 1; c <= n; c++) 
      { 
       System.out.println("" + a + " " + b + " " + c); 
      } 
     } 
    } 
} 

public void printCombinationsChoose4(int n, int k) //for when k = 4 
{ 
    for (int a = 1; a < n - 2; a++) 
    { 
     for (int b = a + 1; b < n - 1; b++) 
     { 
      for (int c = b + 1; c < n; c++) 
      { 
       for (int d = c + 1; d <= n; d++) 
       { 
        System.out.println("" + a + " " + b + " " + c + " " + d); 
       } 
      } 
     } 
    } 
} 

public void printCombinations(int n, int k) //Doesn't work 
{ 
    int[] nums = new int[k]; 
    for (int i = 1; i <= nums.length; i++) 
     nums[i - 1] = i; 

    int count = 1; 

    while (count <= k) 
    { 
     for (int a = nums[k - count]; a <= n; a++) 
     { 
      nums[k - count] = a; 

      for (int i = 0; i < nums.length; i++) 
       System.out.print("" + nums[i] + " "); 
      System.out.println(); 
     } 
     count++; 
    } 
} 

所以我覺得我的最後一個方法的佈局是正確的，但我只是沒有做正確的事，因爲當我打電話printCominbations(5, 2)，它打印

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

磨片它應該是我之前說過的5C2。

編輯 最後一個例子很糟糕。這是一個更好的，說明它在做什麼錯：printCombinations(5, 3)給出了這樣的：

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

我如何得到它是：

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

Answer 1

如何：

public class Test { 

    public static void main(final String[] args) { 
     print_nCr(7, 4); 
    } 

    public static final void print_nCr(final int n, final int r) { 
     int[] res = new int[r]; 
     for (int i = 0; i < res.length; i++) { 
      res[i] = i + 1; 
     } 
     boolean done = false; 
     while (!done) { 
      System.out.println(Arrays.toString(res)); 
      done = getNext(res, n, r); 
     } 
    } 

    ///////// 

    public static final boolean getNext(final int[] num, final int n, final int r) { 
     int target = r - 1; 
     num[target]++; 
     if (num[target] > ((n - (r - target)) + 1)) { 
      // Carry the One 
      while (num[target] > ((n - (r - target)))) { 
       target--; 
       if (target < 0) { 
        break; 
       } 
      } 
      if (target < 0) { 
       return true; 
      } 
      num[target]++; 
      for (int i = target + 1; i < num.length; i++) { 
       num[i] = num[i - 1] + 1; 
      } 
     } 
     return false; 
    } 
} 

的關鍵在於這種解決方案對我來說是看問題的編號系統，並且希望通過一個增加一個號碼，每次到達一個上限，您只需攜帶多餘的向左一個...你只需要正確實現增加算法...

Answer 2

的功能佈局printCombination()似乎是錯誤的。 while循環將迭代兩次，對於count = 1和count = 2。

當count = 1時，只有nums[0][here]中的值會發生變化，因爲在這種情況下爲k - count = 1。 因此，
1,2-
1,3
1,4和
1,5。

而且當count = 2時，只有在nums[here][1]的值會改變，因爲這裏k - count = 0。 因此
1,5
2,5
3,5
4,5和
5,5

Answer 3

OK ...什麼是該解決方案時，我們知道我們需要循環，而不是他們的數量？ RECURSION ... 您需要使用遞歸實現。請記住：ANYTIME，你需要循環，但是隻能在運行時知道嵌套循環的數量，根據問題的具體參數，你應該使用遞歸方法...我會給你一些時間來嘗試它自己，我會回來給你最終實施...

Answer 4

在您的代碼與預期偏離第一點是在這裏：

... 
1 2 5 
1 2 5 <-- first bad output 
1 3 5 
... 

所以問自己三件事：

• 什麼應該發生在那行代碼與給定的變量狀態？

• 爲什麼不完全按照我的代碼？

• 必須改變什麼才能實現這個目標？

對於第一部分的答案是這樣的：

• 應該已經遞增到2和3它應該已經設置了以下數字 4，5，... 相似初始化爲nums。

第二和第三部分是你的部分。

順便說一句：當你回來因爲你需要更多的幫助時，請詳細解釋一下你迄今爲止推導出的什麼和清理並縮短了相當多的問題。

Answer 5

我在C++做了

#include <iostream> 

using namespace std; 
#define ARR_LIMIT 100 
int arr[ARR_LIMIT]; 

void _ncr(int N,int R, int n,int r , int start) 
{ 
    if(r>0) 
    { 
     for(int i = start ; i <= start + (n-r); i++) 
     { 
      arr[R-r] = i; 
      _ncr(N,R,N-i, r-1, i+1); 
     } 
    } 
    else 
    { 
     for(int i=0;i<R;i++) 
     { 
      cout << arr[i] << " "; 
      if(i==R-1) 
       cout<<"\n"; 
     } 
    } 

} 

void ncr(int n,int r) 
{ 
    //Error checking of parameters 
    bool error = false; 
    if(n < 1) 
    { 
     error = true; 
     cout<< "ERROR : n should be greater 0 \n"; 
    } 
    if(r < 1) 
    { 
     error = true; 
     cout<< "ERROR : r should be greater 0 \n"; 
    } 
    if(r > n) 
    { 
     error = true; 
     cout<< "ERROR : n should be greater than or equal to r \n"; 
    } 
    // end of Error checking of parameters 
    if(error) 
     return; 
    else 
     _ncr(n,r,n,r,1); 
} 

int main() 
{ 
    int n,r; 
    cout << "Enter n : "; 
    cin >> n; 
    cout << "Enter r : "; 
    cin >> r; 
    ncr(n,r); 
    return 0; 
}