打印 y 槽中 x 对象的所有组合 (Java)

Question

如果您有 x 个对象（可以用 1 表示）要放置在 y 个槽中（空槽可以用 0 表示），请编写一个函数来打印将对象放置在槽中的所有可能方式。该方法将对象的数量和总槽数作为输入。

例如， possibleCombinations(3, 5) 应该打印 3 个对象可以放置在 5 个槽中的方式：

11100, 11010, 11001, 10110, 10101, 10011, 01110, 01101, 01011, 00111

我已经考虑将递归作为一种选择，但我不知道该怎么走关于对其进行设置，使其适用于任意数量的对象。任何帮助将不胜感激！

Answer 1

这是一些伪代码，显然我没有使用非常好的数据结构。但如果可能的话，您可以查看每个调用，检查包含或不包含每个项目的情况，然后从那里继续。这是 else 语句中的一对递归调用。

func(a,b)
case 0,0
  return null;
case a>b
  return null;
else
  return {1,func(a-1,b-1)} & {0,func(a,b-1)};

Answer 2

这是一些java代码：

public static void possibilities(int k,int n) {
    aux(k,n,new StringBuilder());
}
public static void aux(int k,int n,StringBuilder sb) {
    if (n == 0 && k == 0) {
        System.out.println(sb);
        return;
    } else if (n<k) {
        return;
    }
    if (k>0) { 
        aux(k-1,n-1,new StringBuilder(sb).append(1));
    }
    aux(k,n-1,new StringBuilder(sb).append(0));
}

aux() 实际上完成了工作，它完成了所有可能性：添加 0 或添加 1，并在最后仅打印那些“使用”所有可能的 1 的

编辑： 更改递归结束条件，以修剪不会在末尾打印的情况。

Answer 3

这提醒我您可以在 wolframalpha.com 并获得正确答案。

此答案中的步骤是：

• 创建 1 组：111
• 创建 0 组：00
• 加入它们：11100
• 显示所有排列：

Answer 4

下面是我将如何执行 3、5。从字符串 111 开始。 5 - 3 = 2，因此总共添加 2 个零。每个零a1b1c1d有四个可能的位置。 4 ^ 2 表示 16 个可能的位置，将第一个位置编码为 0 - 3，将第二个位置编码为 (0 - 3) * 4。现在枚举 0 - 15，并打印出结果组合。在这个方案中，前 5 个输出是：

00111, 01011, 01101, 01110, 01011

我们有一个重复。当您需要组合时，此机制会打印出排列。可能有一种方法可以枚举组合，但最简单的解决方案是仅对结果进行索引并确保不会两次返回相同的结果。