import java.security.SecureRandom;
import java.time.Instant;
import java.util.*;

public class Main {
    private final static int counterOutput = 1000;

    public static void main(String[] args) {
        int[] ary = {3,2,5,9,10,1,6,5,8,7,4,0};
        //int[] ary = {3,2,5,9,10};
        ary = bestBogo(ary);
    }

    public static int[] bestBogo(int[] ary) {
        SecureRandom sr = new SecureRandom();
        List<Integer> permutations = new ArrayList<>();
        int[] shuffledArray = new int[ary.length];
        List<String> knownPermutations = new ArrayList<>();
        int count = 0;
        int permutationCount = 0;
        long before = 0;
        long after = 0;
        for (int i = 0; i < ary.length; i++) {
            permutations.add(i);
        }
        do {
            if ((count % counterOutput) == 0) {
                before = System.currentTimeMillis();
            }
            StringBuilder sb = new StringBuilder();
            do {
                sb.setLength(0);
                Collections.shuffle(permutations, sr);
                permutations.forEach(sb::append);
                ++permutationCount;
            } while (knownPermutations.contains(sb.toString()));
            for (int i = 0; i < ary.length; i++) {
                shuffledArray[i] = ary[permutations.get(i)];
            }
            if ((count++ % counterOutput) == (counterOutput - 1)) {
                after = System.currentTimeMillis();
                System.out.println("Iteration/Permutations " + count + " / " + permutationCount + ": " + Arrays.toString(shuffledArray));
                System.out.println("Time spent checking per " + counterOutput + " permutations: " + (after - before) + "ms");
            }
            knownPermutations.add(sb.toString());
        } while (!isSorted(shuffledArray));
        return shuffledArray;
    }

    public static boolean isSorted(int ary[]) {
        for (int i = 1; i < ary.length; i++) {
            if (ary[i] < ary[i-1]) {
                return false;
            }
        }
        return true;
    }
}