How to find permutations of array of ints with java

Question

I am doing some practice where I have to find all the permutations of n numbers. I was given pseudo code, however, I am having difficulties translating it.

public void nextPerm(int[] a,int pivot,int suc){
    suc = 0;
    pivot = 0; 
    for(int i = a.length-1;; i--){
        if( i+1 != a.length)
            if(a[i] < a[i+1]){
                pivot = i;
                break;
            } else if(pivot == 0){
                reverseArray(a,pivot);//this just reverses the array from the right of the pivot point
                System.out.println(a);
        }
    }
    for(int i = a.length-1;;i--){
        if(a[i] > a[pivot]){
            suc = i;
            break;
        }
    }
    //swap pivot and suc
    int place = a[pivot];
    a[pivot] = a[suc];
    a[place] = a[pivot];
    reverseArray(a,pivot);
    System.out.println(Arrays.toString(a));
    
    
}



private void reverseArray(int[] a,int pivot) {//make pivot the index which it will reverse to the right of
    // TODO Auto-generated method stub
    int[] place = new int[a.length-pivot-1];
    int counter = 0;
    for(int i = a.length-1; i > pivot;i--){
        place[counter] = a[i];
        counter++;
    }
    counter = 0;
    int[] hold = new int[a.length];
    for(int i = 0; i <= pivot;i++){
        hold[i] = a[i];
        counter++;
    }
    for(int i = 0; i < place.length;i++){
        hold[counter] = place[i];
        counter++;
    }
    
    System.out.println(Arrays.toString(hold));
}

This is what I have so far. Basically each time I run nextPerm it adjusts an array to be another permutation. For more info check out the pages here: link to more info

Summary: nextPerm finds all the possible perms one at a time by manually changing the array.

So you want to find all the possible permutations of a given number (given as a string) using the logic for finding next permutation? — CodeHunter, Aug 06 '17 at 20:04
no given as int, but yes use basically then run nextPerm again to get the next perm, which manipulates array again to produce another permutation — Zoralikecury, Aug 06 '17 at 20:05
So basically the code should work like this: you start off with an array of lets say: {1,2,3,4} all those are ints. After the first iteration the array changes to 1243, then gets changed to 1324, and so on. I will give the sudo code that he gave us in a sec: — Zoralikecury, Aug 06 '17 at 20:10
scan the array from right-to-left if the current element is less than its right-hand neighbor call the current element the pivot stop scanning if the left end was reached without finding a pivot reverse the array (permutation was lexicographically last, so start over) return scan the array from right-to-left again if the current element is larger than the pivot call the current element the successor stop scanning swap the pivot and the successor reverse the portion of the array to the right of where the pivot was found return .... this be in better format pg 3 with link — Zoralikecury, Aug 06 '17 at 20:14
No need. I get it. You are just passing the output you obtained in the previous step as an input for the next step. That's it. — CodeHunter, Aug 06 '17 at 20:14
yes and sorry for bad explanation......will try my best to improve clarity in future questions — Zoralikecury, Aug 06 '17 at 20:15
change return type of your method from void to int[] and return the array which you are printing in your method. — CodeHunter, Aug 06 '17 at 20:26

score 0 · Answer 1 · answered Aug 06 '17 at 20:22

0

You just need to pass the output obtained in previous step as input to next step until you iterate over all possible permutations. Here is an explanation and pseudo code for the same.

Lets say that you have an array [1,2,3,4]. Total permutations possible with 4 elements in array would be 4! assuming all elements are distinct. So, just iterate the above code for nextPerm 4! times.

int fact = factorial(array.length);
for(int i = 0;i<fact;i++){
    int[] b  = nextPerm(array);
    array = b;
}

assuming that your nextPrem returns you the next permutated array.

answered Aug 06 '17 at 20:22

CodeHunter

2,017
2
21
47

.... I must've described my issues poorly, but I needed help with nextPerm I was having difficulties getting it to work the way the prof wanted it to. Thanks for the next parts help :) really appreciate it. – Zoralikecury Aug 06 '17 at 20:41
@Zoralikecury: Hope this link will help you better. This finds next lexicographical permutation of a string. Same idea is what your professor has implemented in the code he gave you. https://stackoverflow.com/questions/1622532/algorithm-to-find-next-greater-permutation-of-a-given-string – CodeHunter Aug 06 '17 at 21:06

How to find permutations of array of ints with java

1 Answers1