3

I've been looking around quite a bit to solve my issue. I got many problems solved but this one is still haunting me :S It's been a long time I haven't touch Java programming (programming in general) so be understanding out there! ;)

My goal is to get all the combination possible out of an array of integers. When I use the following code, applied to the test array of integer {1, 2, 3, 4}, I expect to have:
1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
2 1 3 4
2 1 4 3
(...)
but here is what I get
1 2 3 4
1 2 3 4 4 3
1 2 3 4 4 3 3 2 4

Does anybody have a clue, a suggestion or even a solution? Thanks in advance!

public class Calculation{
(...)
  public void Permute(ArrayList<Integer> soFar,ArrayList<Integer> rest){
    if(rest.isEmpty())    this.fillMatrice(convertIntegers(soFar)); // there it goes in a previously created arrow of int
    else{
        for(int k=0;k<rest.size();k++){
            ArrayList<Integer> next=new ArrayList<Integer>();
            next=soFar;
            next.add(rest.get(k));
            ArrayList<Integer> remaining=new ArrayList<Integer>();
            List<Integer> sublist = rest.subList(0, k);
            for(int a=0;a<sublist.size();a++)   remaining.add(sublist.get(a));
            sublist = rest.subList(k+1,rest.size());
            for(int a=0;a<sublist.size();a++)   remaining.add(sublist.get(a));
            Permute(next,remaining);
        }
    }
}
public static ArrayList<Integer> convertArray(int[] integers){
    ArrayList<Integer> convArray=new ArrayList<Integer>();
    for(int i=0;i<integers.length;i++)  convArray.add(integers[i]);
    return convArray;
}
public static int[] convertIntegers(List<Integer> integers){
    int[] ret = new int[integers.size()];
    for(int i=0;i<ret.length;i++)   ret[i]=integers.get(i).intValue();
    return ret;
}
public Calculation() {
    (...)
    ArrayList<Integer> soFar=new ArrayList<Integer>();
    int[] test={1,2,3,4};
    Permute(soFar,convertArray(test));
}
Improve this question

2 Answers 2

Reset to default
5

Try this, it seems to work, it uses recursion.

public class Permute {

    public static List<List<Integer>> permute(Integer...myInts){

        if(myInts.length==1){
            List<Integer> arrayList = new ArrayList<Integer>();
            arrayList.add(myInts[0]);
            List<List<Integer> > listOfList = new ArrayList<List<Integer>>();
            listOfList.add(arrayList);
            return listOfList;
        }

        Set<Integer> setOf = new HashSet<Integer>(Arrays.asList(myInts));   

        List<List<Integer>> listOfLists = new ArrayList<List<Integer>>();

        for(Integer i: myInts){
            ArrayList<Integer> arrayList = new ArrayList<Integer>();
            arrayList.add(i);

            Set<Integer> setOfCopied = new HashSet<Integer>();
            setOfCopied.addAll(setOf);
            setOfCopied.remove(i);

            Integer[] isttt = new Integer[setOfCopied.size()];
            setOfCopied.toArray(isttt);

            List<List<Integer>> permute = permute(isttt);
            Iterator<List<Integer>> iterator = permute.iterator();
            while (iterator.hasNext()) {
                List<java.lang.Integer> list = iterator.next();
                list.add(i);
                listOfLists.add(list);
            }
        }   

        return listOfLists;
    }

    public static void main(String[] args) {
        List<List<Integer>> permute = permute(1,2,3,4);
        System.out.println(permute);
    }

}

If you don't like the List> you can easily change from arrays to list using the methods from list and static methods from java.util.Collections and java.util.Arrays.

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

Thanks, that works as well. Though Set, HashSet and co are unknown to me and I am having a hard time to get through the logic of it all
Thank you, this also works for me, to fully understand your logic could you please expand what isttt variable name stands for?
not a meaningful name actualy, it is only used as a temporary variable to be passed again in the permute method. THe idea is: pick each number and concatenate it with all the permutations of the other recursively, and you do it until the sub-elements list has lenght = 1.
2

You can try Recursion to solve this issue:

public static void printPermutations(int[] n, int[] Nr, int idx) {
    if (idx == n.length) {  //stop condition for the recursion [base clause]
        System.out.println(Arrays.toString(n));
        return;
    }
    for (int i = 0; i <= Nr[idx]; i++) { 
        n[idx] = i;
        printPermutations(n, Nr, idx+1); //recursive invokation, for next elements
    }
}

More info can be had from this link: Combinatorics: generate all “states” - array combinations

You can replicate the same logic here as well.

Improve this answer

3 Comments

What if the size of the incoming array is very large?
Your code creates new arrays in every possible ways for n[i] from 0 to Nr[i] but doesn't permute the existing array. But actually this is very useful because the array I input in the Permutation method is coming from a previously computed int[][] containing defined size int[] which verify the following conditions: - its elements are inferior or equal to Degree - there sum is equal to Degree. My issue was to permute all the integer of every int[] created. Your solution enables to do both at ones. I just need to add a condition to test that the sum of integer in the array is equal to Degree.
@user1503780, you can modify the code however you need.It is just a psudo-code you can say.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.