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