Permutations of ArrayList

Question

I am working on a problem where I have to obtain all permutations of an arraylist of numbers. The only restriction is that any number can't start with 0, so if we have [0,1,2] we would obtain

[1,2,0]

[1,0,2]

[2,0,1]

[2,1,0]

I know how to do this with 3 loops but the thing is that I have to repeat this to different sets of numbers with different sizes, so I need one method that I can apply to different sets of numbers. Unfortunately, I have no clue how to do this. I imagine I have to use some kind of recursive function but I don't know how to implement it so the numbers cant start with a 0. Any ideas? Please help me understand the problem, don't just post working code.

share your implementation (even if it start with 0) so we could help you fine tuning it — shahaf, Apr 28 '18 at 14:19
Get your permutations (which is best acquired using recursion) into an ArrayList. Before the ArrayList is returned, Iterate through it and remove any elements that start with 0. — DevilsHnd - 退職した, Apr 28 '18 at 14:39

score 1 · Answer 1 · answered Apr 28 '18 at 14:50

Curious question! Interesting code kata.

I naively think I would have a recursive method that takes:

a list of the items currently chosen by the caller
a set of the items available for the callee

The method would iterate over the set to chose 1 more item and call itself with the list extended by this item, and the set reduced by this item. Upon return, remove from list, add back to set and go on with next item (take a defensive copy of the set of course).

If the current list is empty, the selected first item cannot be 0, as per your rules. If you must collect the permutations somewhere (not just print), a 3rd argument would be required for a collection or an observer.

The recursion obvioulsy stops when the available set is empty, at which point the permutation is sent to the collection or observer.

If items can repeat, you may have benefit from sorting them first in order to skip electing the same item again at a given position.

Beware this quires a recursion depth of N, for N items. But the danger is minimal because even with N=10000, it may not stackoverflow, but the CPU time to complete would be order(N!) (probably end of universe...)

balderdash · Answer 2 · 2018-04-28T14:53:03.633

0

You could solve this recursively as described here: Permutation of an ArrayList of numbers using recursion. The only thing that is missing there is your restriction with the zeros, which could be solved somehow like this (the loop is taken from the example above):

for (List<Integer> al : myLists) {

    // The part you need to add:
    if (al.get(0) == 0) {
        continue;
    }

    String appender = "";
    for (Integer i : al) {
        System.out.print(appender + i);
        appender = " ";
    }
    System.out.println();
}

You basically check the first element of each permutation and skip the ones with a leading zero. The continue jumps to the next iteration of the loop and therefore to the next permutation.

edited Apr 28 '18 at 14:53

answered Apr 28 '18 at 14:45

balderdash

95
10

so i used this to create all permutations but i see a problem, and that is that when the list you are giving has many numbers, the combinations are impossible to store and the program finish because it exceeded the memory heap, so it would be ideal to calculate one permutationn do the operations i want to do with that, and dispose that permutation, so i only work with one permutation at a time instead of having all possible combinations store in an array. – JuanMartinez Apr 29 '18 at 16:44
The problem is not storing the results in an array, but the recursion depth. Each time you call the function, the return address is pushed onto the call stack. The problem here is that if your recursion is too deep because you have a very large list, the call stack runs out of space and you receive a stack overflow. You could use an iterative approach to compute the permutations, but keep in mind that calculating all permutations is in O(n!) which is not that efficiently solvable for large inputs. – balderdash May 03 '18 at 21:25

Permutations of ArrayList

2 Answers2