用 Java 打印所有可能的 nCr 组合

Question

提问by Pat Needham

I'm trying to print out all possibilities of nCr, which are the combinations when order doesn't matter. So 5C1 there are 5 possibilities: 1 , 2, 3, 4, 5. 5C2 there are 10 possibilities: 1 2, 1 3, 1 4, 1 5, 2 3, 2 4, 2 5, 3 4, 3 5, 4 5.

我试图打印出 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.

I made functions that print what I want for r = 2, r = 3, and r = 4, and I sort of see the pattern, but I cant seem to make a working method for variable r:

我制作了打印我想要的 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++;
    }
}

So I think the layout of my last method is right, but I'm just not doing the right things, because when I call printCominbations(5, 2), it prints

所以我认为我最后一个方法的布局是正确的，但我只是没有做正确的事情，因为当我调用时printCominbations(5, 2)，它会打印

when it should be what I said earlier for 5C2.

什么时候应该是我之前对 5C2 所说的。

EditThe last example was bad. This is a better one to illustrate what it's doing wrong: printCombinations(5, 3)gives this:

编辑最后一个例子很糟糕。这是一个更好的说明它做错printCombinations(5, 3)了什么：给出这个：

How do I get it to be:

我如何让它成为：

Answer 1

回答by Mostafa Zeinali

How about this:

这个怎么样：

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

The key to this solution for me was to look at the problem as a numbering system and you want to increase a number by one and every time you reach an upper bound, you just carry the excess to the left one and ... You just need to implement the increasing algorithm correctly...

对我来说，此解决方案的关键是将问题视为一个编号系统，并且您希望将数字加一，每次达到上限时，您只需将多余的部分移到左边，然后……您只需需要正确实现递增算法...

Answer 2

回答by A.H.

The first point where your code deviates from the expectation is here:

您的代码偏离预期的第一点在这里：

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

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

So ask yourself three things:

所以问自己三件事：

What should have happenedin that line of code with the given state of the variables?
Why doesn't do my code exactly that?
What must be changed to achieve that?

在给定变量状态的那行代码中应该发生什么？
为什么我的代码不完全那样？
必须改变什么才能实现这一目标？

The answer for the first part is like this:

第一部分的答案是这样的：

It should have incremented the 2to 3and it should have set the following numbers to 4, 5, ... similarto the initialisation of nums.

它应该增加2to3并且应该将以下数字设置为 4, 5, ...类似于的初始化nums。

The second and third part is your part again.

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

BTW: When you come back because you need more help, please explain in detail what you have deduced so far andclean up and shorten the question quite a bit.

BTW：当您因为需要更多帮助而回来时，请详细说明您到目前为止的推论，并将问题清理和缩短很多。

Answer 3

回答by Mostafa Zeinali

OK... What is the solution when we know we need loops, but not the number of them?? RECURSION... You need to use a recursive implementation. Have this in mind: ANYTIME, you need loops but the number of the nested loops can only be known at runtime, based on the specific parameters of the problem, you should use recursive methods... I'll give you some time to try it yourself, I'll be back to give you the final implementation...

好的...当我们知道我们需要循环而不是循环的数量时，有什么解决方案？递归...您需要使用递归实现。记住这一点：ANYTIME，你需要循环但嵌套循环的数量只能在运行时知道，根据问题的具体参数，你应该使用递归方法......我会给你一些时间尝试自己来吧，我会回来给你最终实现的......

Answer 4

回答by user2114956

I have done it in c++

我已经用 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;
}

Answer 5

回答by KK.

The layout of function printCombination()seems wrong. The while loop will iterate two times, for count = 1and count = 2.

功能布局printCombination()似乎有误。while 循环将迭代两次， forcount = 1和count = 2。

When count = 1, only values in nums[0][here]will change, since in this case k - count = 1. Hence,
1,2
1,3
1,4 and
1,5.

当时count = 1，只有中的值nums[0][here]会改变，因为在这种情况下k - count = 1。因此，
1,2
1,3
1,4 和
1,5。

And when count = 2, only values in nums[here][1]will change, since here k - count = 0. Hence
1,5
2,5
3,5
4,5 and
5,5

当count = 2，只有值nums[here][1]会改变，因为这里k - count = 0。因此
1,5
2,5
3,5
4,5 和
5,5

用 Java 打印所有可能的 nCr 组合

提问by Pat Needham

回答by Mostafa Zeinali

回答by A.H.

回答by Mostafa Zeinali

回答by user2114956

回答by KK.

相关推荐

最近更新

标签

用 Java 打印所有可能的 nCr 组合

提问by Pat Needham

回答by Mostafa Zeinali

回答by A.H.

回答by Mostafa Zeinali

回答by user2114956

回答by KK.

相关推荐

垂直轴中间的 Java JLabel 文本

java 从 Guava 的 Splitter 创建一个 String[]

java 如何在Java中制作圆角图像

java Android java更改可绘制图像

相关推荐

最近更新

标签