arrays - 带重复的部分排列。列出所有解决方案算法

Question

我会寻求您最好的意见和建议。我对不同的盒子和物体有疑问。

我来解释一下:比如我有2个盒子和3个物体。所以我用 2^3 = 8 种可能的解决方案来计算所有解决方案。方框 {-1, 0} 列表。对象列表 {0, 1, 2}。

我对一种解决方案的表示:数组[objects.length]

1 solution : [-1,-1,-1];
2 solution : [0,-1,-1];
3 solution : [-1,0,-1];
4 solution : [-1,-1,0];
5 solution : [0,0,-1];
6 solution : [-1,0,0];
7 solution : [0,-1,0];
8 solution : [0,0,0];

现在我介绍我的算法，但它不起作用:

Array box = {-1, 1}
Array object = {0, 1, 2}
Array solutions = {}

// INITIALISATION
Stack sbox = box;
Stack sobject = object;

WHILE sobject not empty DO
     object = Pop sobject;

     FOR i from 0 to box.length DO
          solution[object] = box[i];
     FIN POUR
END WHILE

但是这个解是不正确的，因为我只有6个解。

你能帮我提供不同的文件或建议吗？谢谢。

Answer 1

我不知道为什么你的盒子数组是 {-1, 0}，无论如何下面的代码是有效的。您只需要一个基数(框的数量)，然后一遍又一遍地除以排列总数。在你的情况下，你有 2^3=8 个解决方案，你的基数是 2，你在外循环中尝试 0、1、2、.. 7，并在内循环中划分基数。

    int[] box = {-1, 0};
    int objects = 3;
    int total = (int) Math.pow(box.length, objects);
    int radix = box.length;
    for (int i = 0; i < total; i++) {
        int v = i;
        for (int pos = 0; pos < objects; pos++) {
            System.out.print(box[v % radix] + " ");
            v = v / radix;
        }
        System.out.println();
    }

这样，当你有很多盒子时，你可以避免大堆栈(递归也需要堆栈)。在更复杂的情况下，您可以有多个基数，例如对于第一个盒子，允许使用 A 和 B，对于第二个盒子，允许使用 B、C 和 D。