Partial permutation with repetition. List all solutions algorithm

Question

I will be looking for your best advice and recommendations. I have a problem with different box and object.

Let me explain: For example, I have 2 box and 3 objects. So I count all solutions with 2^3 = 8 possible solutions. List of box {-1, 0}. List of objects {0, 1, 2}.

My representation for one solution: an array[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];

Now I present my algorithm that doesn't work:

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

But this solution is not correct because I have just 6 solutions.

Can you help me with different document or advice? Thanks.

Answer 1

I don't know why your box array is {-1, 0}, anyway the code below works. You just need a radix (the number of boxes) then divide the total number of permutations over and over again. In your case, you have 2^3=8 solutions, your radix is 2, you try 0, 1, 2, .. 7 in the outer loop, and divide the radix in the inner loop.

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

This way, you can avoid a big stack when you have a lot of boxes (recursion also requires the stack). In more complicated cases, you could have multiple radices, e,g. for the 1st box, item A and B are allowed, for the 2nd box, B, C and D are allowed.