K个桶中N个对象的所有可能组合

Question

假设我有 3 个标有 A、B、C 的盒子，我有 2 个球，B1 和 B2。我想在盒子里得到这些球的所有可能组合。请注意，知道每个盒子里是哪个球很重要，这意味着 B1 和 B2 不一样。

A         B         C
B1, B2
B1        B2
B1                  B2
B2        B1        
B2                  B1
          B1, B2
          B1        B2
          B2        B1
                    B1, B2

编辑

如果这个问题有已知的算法，请告诉我它的名字。

Answer 1

设N为桶数（示例中为3），M为球数（2）。现在，让我们看一下示例中 [0..N**M) - [0..9) 范围内的数字；我们用 radix = N 表示这些数字。对于问题中的示例，我们有 trinary numbers

现在我们可以很容易地解释这些数字：第一个数字表示第一个球的位置，第二个数字表示第二个球的位置。

      |--- Second Ball position [0..2]
      ||-- First Ball position  [0..2]  
      ||
  0 = 00 - both balls are in the bucket #0 (`A`)
  1 = 01 - first ball is in the bucket #1 ('B'), second is in the bucket #0 (`A`)
  2 = 02 - first ball is in the bucket #2 ('C'), second is in the bucket #0 (`A`)
  3 = 10 - first ball is in the bucket #0 ('A'), second is in the bucket #1 (`B`)
  4 = 11 - both balls are in the bucket #1 (`B`)
  5 = 12 ...
  6 = 20
  7 = 21 ...
  8 = 22 - both balls are in the bucket #2 (`C`)

一般算法为：

对于 0 .. N**M 范围内的每个数字
i第一个球（i = 0..M-1）会在桶里#(number / N**i) % N（这里/代表整数除法，% 余数）

如果你只想要总数，答案很简单N ** M，在上面的例子中3 ** 2 == 9

C#代码算法本身很容易实现：

static IEnumerable<int[]> BallsLocations(int boxCount, int ballCount) {
  BigInteger count = BigInteger.Pow(boxCount, ballCount);

  for (BigInteger i = 0; i < count; ++i) {
    int[] balls = new int[ballCount];
    int index = 0;

    for (BigInteger value = i; value > 0; value /= boxCount)
      balls[index++] = (int)(value % boxCount);

    yield return balls;
  }
}

是可以纠结的答案表示：

static IEnumerable<string> BallsSolutions(int boxCount, int ballCount) {
  foreach (int[] balls in BallsLocations(boxCount, ballCount)) {
    List<int>[] boxes = Enumerable
      .Range(0, boxCount)
      .Select(_ => new List<int>())
      .ToArray();

    for (int j = 0; j < balls.Length; ++j)
      boxes[balls[j]].Add(j + 1);

    yield return string.Join(Environment.NewLine, boxes
      .Select((item, index) => $"Box {index + 1} : {string.Join(", ", item.Select(b => $"B{b}"))}"));
  }
}

演示：

  int balls = 3;
  int boxes = 2;

  string report = string.Join(
    Environment.NewLine + "------------------" + Environment.NewLine, 
    BallsSolutions(boxes, balls));

  Console.Write(report);

结果：

Box 1 : B1, B2, B3
Box 2 : 
------------------
Box 1 : B2, B3
Box 2 : B1
------------------
Box 1 : B1, B3
Box 2 : B2
------------------
Box 1 : B3
Box 2 : B1, B2
------------------
Box 1 : B1, B2
Box 2 : B3
------------------
Box 1 : B2
Box 2 : B1, B3
------------------
Box 1 : B1
Box 2 : B2, B3
------------------
Box 1 : 
Box 2 : B1, B2, B3

Fiddle

Answer 2

有一个非常简单的递归实现，在每个级别将当前球添加到每个盒子。处理完所有球后，递归结束。

这里有一些 Java 代码来说明。我们使用 Stack 来表示每个盒子，这样我们就可以在每一层递归之后简单地弹出最后添加的球。

void boxBalls(List<Stack<String>> boxes, String[] balls, int i)
{
    if(i == balls.length)
    {
        System.out.println(boxes);
        return;
    }
    
    for(Stack<String> box : boxes)
    {
        box.push(balls[i]);
        boxBalls(boxes, balls, i+1);
        box.pop();
    }
}

测试：

String[] balls = {"B1", "B2"};
List<Stack<String>> boxes = new ArrayList<>();
for(int i=0; i<3; i++) boxes.add(new Stack<>());

boxBalls(boxes, balls, 0);

输出：

[[B1, B2], [], []]
[[B1], [B2], []]
[[B1], [], [B2]]
[[B2], [B1], []]
[[], [B1, B2], []]
[[], [B1], [B2]]
[[B2], [], [B1]]
[[], [B2], [B1]]
[[], [], [B1, B2]]

K个桶中N个对象的所有可能组合

All possible combinations of N objects in K buckets

algorithm

combinations

enumeration

permutation

编辑