Permutation matrix with dynamic variable (days), each day should "generate" one for-loop?

user_19828182 0
Viewed 32

I want to make a permutation matrix using a dynamic variable (days).

My current code has 3 loops (for 3 days), and if I wanted to add another day or delete one day, I would have to add/delete one complete for-loop.

public static ArrayList<ArrayList<Integer>> computePermutations(int stops, int days) {
        int maxPerDay = stops - (days - 1);
        ArrayList<ArrayList<Integer>> permutationMatrix = new ArrayList<ArrayList<Integer>>();
        for (int m = 1; m <= maxPerDay; m++) {
            for (int n = 1; n <= maxPerDay; n++) {
                for (int o = 1; o <= maxPerDay; o++) {
                    if (m + n + o == stops) {
                        ArrayList<Integer> possibleSolution = new ArrayList<Integer>(Arrays.asList(m, n, o));
                        permutationMatrix.add(possibleSolution);
                    }
                }
            }
        }
        return permutationMatrix;
    }

I also need to update the line: ArrayList<Integer> possibleSolution = new ArrayList<Integer>(Arrays.asList(m, n, o));, so the parameters (m, n, o) change depending on the amount of days.

permutation matrix java
1 Answers

Your question in essence can be summarized as follows

If I have to compute the permutation of n elements, do I need n embedded for cycles?

And the answer is no. It is solvable with embedding n cycles, you are correct in observing that, but it is not necessary, nor advisable. The problem with this kind of solution is that your program will assume in advance the number of items to permutate and will have difficulty in handling the case when the number of elements to permutate is dynamic.

First of all, you need to understand what a stack is, that is a Last In, First Out (LIFO) data-structure, which means that you can always push elements to its top, but whenever you need to take out an element, you take it to the top.

So, you need to implement the following (I'm not taking the fun of the actual implementation):

  • you create an empty stack
  • you add 1 to its top
  • while your stack is not empty
    • if you are not at the last element, push the first element that's not already in the stack
    • else if you are at the last element, then you have found a new permutation and
      • while stack.top is n or there is no stack.top < i <= n that's not already in the stack, stack.pop
      • if the stack is empty, then the algorithm ends
      • else
        • current <- stack.top
        • stack.push(the first element that's higher than current and is not in the stack)

So, you are able to use one main loop and inside that loop you will only need some loops to find the next unused element instead of a loop for every index.

user_4365600
Related