CODEWITHSUNDEEP
javaarraylistcombinationspermutation
JuanMartinez
JuanMartinez

Reputation: 29

Permutations of ArrayList<Integer>

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.

Upvotes: 2

Views: 456

Answers (2)

balderdash
balderdash

Reputation: 95

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.

Upvotes: 0

user2023577
user2023577

Reputation: 2111

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...)

Upvotes: 1

Related Questions