How to get first permutation only?

This class generates and prints the different permutations of n objects.

public class Permutacoes {

current permutation number

    private static int cont = 0;

stores the current permutation

private static char[] p;

main method: receives the vector whose elements will be exchanged

    /**
     * @param vet
     */
    public static void permuta(char [] vet) {

        p = new char[vet.length];
        permuta(vet,0);

    }

recursive method that implements the permutations

    /**
     * @param vet
     * @param n
     */
    private static void permuta(char []vet, int n) {

        if (n == vet.length) {

            cont++;
            imprime();

        } else {

            for (int i=0; i < vet.length; i++) {

                boolean achou = false;

                for (int j = 0; j < n; j++) {

                    if (p[j]==vet[i]) achou = true;

                }

                if (!achou) {

                    p[n] = vet[i];
                    permuta(vet,n+1);

                }

            } //--for

        } //--if/else

    } //--permutation

prints the current permutation

    private static void imprime() {

        System.out.println();
        System.out.print("(" + cont + ") : ");
        for (int i=0; i < p.length; i++) System.out.print(p[i] + " ");

    } //--print

main method for class testing

    public static void main(String[] args) {

        char v[] = {'A','B','C'};
        Permutacoes.permuta(v);
    }

}

outputs:

(1) : A B C 
(2) : A C B 
(3) : B A C 
(4) : B C A 
(5) : C A B 
(6) : C B A

I need only this:

(1) : A B C 
(2) : A C B 

1 answer

  • answered 2019-11-13 18:44 kaya3

    Assuming you want permutation #2 in lexicographic order (e.g. ABC → ACB), you should search for the right-most index i such that arr[i-1] != arr[i], and swap them. This assumes the array starts as permutation #1, i.e. in sorted order, so we should sort the array first to guarantee this.

    The solution below works out-of-place and returns a new array, to avoid mutating the original one. It should be easy to adapt if you want it to work in-place instead.

    import java.util.Arrays;
    
    public class SecondPermutation {
        public static char[] of(char[] orig) {
            char[] next = Arrays.copyOf(orig, orig.length);
            Arrays.sort(next);
    
            // find right-most non-equal adjacent pair
            int i = next.length - 1;
            while(i > 0 && next[i-1] == next[i]) {
                --i;
            }
    
            if(i == 0) {
                throw new IllegalArgumentException("Array has no next permutation");
            }
    
            // swap them
            char tmp = next[i];
            next[i] = next[i-1];
            next[i-1] = tmp;
    
            return next;
        }
    }