Проверьте, являются ли два массива циклическими перестановками

Question

Учитывая два массива, как вы проверяете, является ли один циклической перестановкой другого?

Например, учитывая a = [1, 2, 3, 1, 5], b = [3, 1, 5, 1, 2] и c = [2, 1, 3, 1, 5], мы имеем, что a и b являются циклическими перестановками, но c не является циклической перестановкой того или другого.

Примечание: массивы могут содержать дубликаты элементов.

Answer 1

Стандартный прием заключается в том, чтобы объединить один из массивов с самим собой, а затем попытаться найти второй массив в объединенном массиве.

Например, «a», соединенное с самим собой:

[1, 2, 3, 1, 5, 1, 2, 3, 1, 5]

Поскольку вы видите 'b' в этом массиве, начиная с 3-го элемента, то a и b являются циклическими перестановками.

Answer 2

Эффективный способ обработки больших объемов данных - это преобразовать каждый из них в «каноническую» форму, а затем сравнить, чтобы убедиться, что они равны. Для этой задачи вы можете выбрать в качестве канонической формы всех повернутых перестановок ту, которая «сортирует самые маленькие».

Таким образом, каноническая форма для «a» и «b» - это [1, 2, 3, 1, 5], которые равны, поэтому они являются ациклическими перестановками.

Каноническая форма для 'c' - это [1, 3, 1, 5, 2], которая отличается.

Answer 3

Если A и B являются циклическими перестановками друг друга, A будет найден в двойном списке BB (как B в AA).

Answer 4

Вот простой adhoc подход к обнаружению циклических перестановок с O (n) временной сложностью.

a = [1, 2, 3, 1, 5], b = [3, 1, 5, 1, 2]

Найти индекс b [0] в a [], допустим, индекс равен 'x'. После начала навигация в обоих массивах. a [] начинается с индекса 'x' и b [] начинается с «0». Так что оба они должны иметь одинаковые значения. Если нет, они не циклические. Вот пример кода.

 public class CyclicPermutation {

    static char[] arr = { 'A', 'B', 'C', 'D' };
    static char[] brr = { 'C', 'D', 'K', 'B' };
    boolean dec = false;

    public static void main(String[] args) {
        boolean avail = true;
        int val = getFirstElementIndex(brr[0]);
        if(val ==Integer.MIN_VALUE){
            avail = false; 
            return;
            }

        for (int i = val, j = 0; j <= brr.length-1; ) {
            if (i > arr.length-1) {
                i = 0;
            }
            if (arr[i] == brr[j]) {
                i++;

                j++;

            } else {
                avail = false;
                System.out.println(avail);
                return;
            }


        }

   System.out.println(avail);
    }

    public static int getFirstElementIndex(char c) {

        for (int i = 0; i <= arr.length; i++) {
            if (arr[i] == c) {
                return i;
            }
        }
        return Integer.MIN_VALUE;
    }


}