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

Question

我正在尝试打印nCr的所有可能性,这是订单无关紧要时的组合.所以5C1有5种可能性:1,2,3,4,5.5C2有10种可能性:1 2,1 3,1 4,1 5,2 2,3,2,4,5 3,4 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;
    }
}

对我来说,这个解决方案的关键是将问题看作一个编号系统,你想要增加一个数字,每当你达到一个上限时,你只需将多余的数据带到左边的那个......你只是需要正确实现增加算法...