import java.util.Scanner;
import java.util.ArrayList;
import java.util.Date;
 
class Permute {
 
    public static void main(String[] args) {
        System.out.println("Enter the numbers separated by spaces: ");
        Scanner sc = new Scanner(System.in);
        ArrayList<Integer> input = new ArrayList();
        String line = sc.nextLine();
        String[] splits = line.split(" ");
        for (int i = 0; i < splits.length; i++) {
            input.add(Integer.parseInt(splits[i]));
        }
        // System.out.println(input.toString());
        // System.out.println(new Date().getTime());
        permute(input);
        // System.out.println(new Date().getTime());
    }
 
    public static void permute(ArrayList<Integer> input) {
        long start = new Date().getTime();
        ArrayList<ArrayList<Integer>> permutations = new ArrayList();
        permutations.add(new ArrayList<Integer>());
        for (int i = 0; i < input.size(); i++) {
            int element = input.get(i);
            //System.out.print(element + ":");
            ArrayList<ArrayList<Integer>> temp = new ArrayList();
            for (int j = 0; j < permutations.size(); j++) {
                ArrayList<Integer> tmp = new ArrayList();
                tmp.addAll(permutations.get(j));
                for (int k = 0; k <= permutations.get(j).size(); k++) {
                    tmp.add(k, element);
                    temp.add(tmp);
                    //System.out.println(tmp + " " + permutations.get(j));
                    tmp = new ArrayList();
                    tmp.addAll(permutations.get(j));
                }
            }
            permutations = temp;
        }
        long end = new Date().getTime();
        System.out.println("Total permutations = " + permutations.size());
        System.out.println("Time taken = " + (end-start)+ "ms.");
        System.out.println(permutations.toString());
    }
}

aW1wb3J0IGphdmEudXRpbC5TY2FubmVyOwppbXBvcnQgamF2YS51dGlsLkFycmF5TGlzdDsKaW1wb3J0IGphdmEudXRpbC5EYXRlOwoKY2xhc3MgUGVybXV0ZSB7CgogICAgcHVibGljIHN0YXRpYyB2b2lkIG1haW4oU3RyaW5nW10gYXJncykgewogICAgICAgIFN5c3RlbS5vdXQucHJpbnRsbigiRW50ZXIgdGhlIG51bWJlcnMgc2VwYXJhdGVkIGJ5IHNwYWNlczogIik7CiAgICAgICAgU2Nhbm5lciBzYyA9IG5ldyBTY2FubmVyKFN5c3RlbS5pbik7CiAgICAgICAgQXJyYXlMaXN0PEludGVnZXI+IGlucHV0ID0gbmV3IEFycmF5TGlzdCgpOwogICAgICAgIFN0cmluZyBsaW5lID0gc2MubmV4dExpbmUoKTsKICAgICAgICBTdHJpbmdbXSBzcGxpdHMgPSBsaW5lLnNwbGl0KCIgIik7CiAgICAgICAgZm9yIChpbnQgaSA9IDA7IGkgPCBzcGxpdHMubGVuZ3RoOyBpKyspIHsKICAgICAgICAgICAgaW5wdXQuYWRkKEludGVnZXIucGFyc2VJbnQoc3BsaXRzW2ldKSk7CiAgICAgICAgfQogICAgICAgIC8vIFN5c3RlbS5vdXQucHJpbnRsbihpbnB1dC50b1N0cmluZygpKTsKICAgICAgICAvLyBTeXN0ZW0ub3V0LnByaW50bG4obmV3IERhdGUoKS5nZXRUaW1lKCkpOwogICAgICAgIHBlcm11dGUoaW5wdXQpOwogICAgICAgIC8vIFN5c3RlbS5vdXQucHJpbnRsbihuZXcgRGF0ZSgpLmdldFRpbWUoKSk7CiAgICB9CgogICAgcHVibGljIHN0YXRpYyB2b2lkIHBlcm11dGUoQXJyYXlMaXN0PEludGVnZXI+IGlucHV0KSB7CiAgICAgICAgbG9uZyBzdGFydCA9IG5ldyBEYXRlKCkuZ2V0VGltZSgpOwogICAgICAgIEFycmF5TGlzdDxBcnJheUxpc3Q8SW50ZWdlcj4+IHBlcm11dGF0aW9ucyA9IG5ldyBBcnJheUxpc3QoKTsKICAgICAgICBwZXJtdXRhdGlvbnMuYWRkKG5ldyBBcnJheUxpc3Q8SW50ZWdlcj4oKSk7CiAgICAgICAgZm9yIChpbnQgaSA9IDA7IGkgPCBpbnB1dC5zaXplKCk7IGkrKykgewogICAgICAgICAgICBpbnQgZWxlbWVudCA9IGlucHV0LmdldChpKTsKICAgICAgICAgICAgLy9TeXN0ZW0ub3V0LnByaW50KGVsZW1lbnQgKyAiOiIpOwogICAgICAgICAgICBBcnJheUxpc3Q8QXJyYXlMaXN0PEludGVnZXI+PiB0ZW1wID0gbmV3IEFycmF5TGlzdCgpOwogICAgICAgICAgICBmb3IgKGludCBqID0gMDsgaiA8IHBlcm11dGF0aW9ucy5zaXplKCk7IGorKykgewogICAgICAgICAgICAgICAgQXJyYXlMaXN0PEludGVnZXI+IHRtcCA9IG5ldyBBcnJheUxpc3QoKTsKICAgICAgICAgICAgICAgIHRtcC5hZGRBbGwocGVybXV0YXRpb25zLmdldChqKSk7CiAgICAgICAgICAgICAgICBmb3IgKGludCBrID0gMDsgayA8PSBwZXJtdXRhdGlvbnMuZ2V0KGopLnNpemUoKTsgaysrKSB7CiAgICAgICAgICAgICAgICAgICAgdG1wLmFkZChrLCBlbGVtZW50KTsKICAgICAgICAgICAgICAgICAgICB0ZW1wLmFkZCh0bXApOwogICAgICAgICAgICAgICAgICAgIC8vU3lzdGVtLm91dC5wcmludGxuKHRtcCArICIgIiArIHBlcm11dGF0aW9ucy5nZXQoaikpOwogICAgICAgICAgICAgICAgICAgIHRtcCA9IG5ldyBBcnJheUxpc3QoKTsKICAgICAgICAgICAgICAgICAgICB0bXAuYWRkQWxsKHBlcm11dGF0aW9ucy5nZXQoaikpOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICB9CiAgICAgICAgICAgIHBlcm11dGF0aW9ucyA9IHRlbXA7CiAgICAgICAgfQogICAgICAgIGxvbmcgZW5kID0gbmV3IERhdGUoKS5nZXRUaW1lKCk7CiAgICAgICAgU3lzdGVtLm91dC5wcmludGxuKCJUb3RhbCBwZXJtdXRhdGlvbnMgPSAiICsgcGVybXV0YXRpb25zLnNpemUoKSk7CiAgICAgICAgU3lzdGVtLm91dC5wcmludGxuKCJUaW1lIHRha2VuID0gIiArIChlbmQtc3RhcnQpKyAibXMuIik7CiAgICAgICAgU3lzdGVtLm91dC5wcmludGxuKHBlcm11dGF0aW9ucy50b1N0cmluZygpKTsKICAgIH0KfQ==

MSAyIDMgNCA1

1 2 3 4 5