вариант 1 пермутации

public class Test {
    private static int n = 5;
    private static int permCounter = 0;
    private static int[] perm = new int[n];
    public static void permutate(int left, int counter) {
        if (left == n - 1) {
            print();
        } else {
            if (counter == n - 1) {
                return;
            } else {
                permutate(left + 1, 0);
                for (int i = counter + 1; i <= n - 1 - left; ++i) {
                    exchange(left);
                    permutate(left + 1, 0);
                }
            }
        }
    }

    private static void exchange(int left) {
        int val = perm[left];
        perm[left] = perm[left + 1];
        perm[left + 1] = val;
    }

    private static void print() {
        ++permCounter;
        System.out.print(permCounter + ":\t");
        for (int i = 0; i < n; ++i) {
            System.out.print(perm[i] + "\t");
        }
        System.out.println();
    }

    public static void main(String []args) {
        for (int i = 0; i < n; ++i) {
            perm[i] = i + 1;
        }
        permutate(0, 0);
    }
}