检查两个数组是否为循环排列

Question

给定两个数组，如何检查一个数组是否是另一个数组的循环排列？

例如，给定a = [1, 2, 3, 1, 5]，b = [3, 1, 5, 1, 2]和c = [2, 1, 3, 1, 5]，我们知道a和b是循环排列但c不是任何一个数组的循环排列。

注意：这些数组可能有重复元素。

- dsg

---

可能是重复的问题：面试题：检查一个字符串是否为另一个字符串的旋转。 - Aryabhatta

@Aryabhatta -- 是的，这是一个重复问题。谢谢指出。 - dsg

Answer 1

这里的标准技巧是将其中一个数组与自身连接起来，然后尝试在连接后的数组中查找第二个数组。

例如，'a' 与自身连接即为:

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

因为你可以从第三个元素开始在该数组中看到 'b'，所以 a 和 b 是循环排列。

- Himadri Choudhury

---

我假设你预设数组长度相等。即使如此，为什么不可能存在误报呢？ - dsg

是的。如果数组长度不相等，那么它们显然不是彼此的排列。 - Himadri Choudhury

如果算法说它是一个排列，那么它就是通过构造得到的。如果您在位置ai处在'a'+'a'中找到了'b'，那么如果您将'a'向右移动i个位置，使ai成为'a'的第一个元素，则环绕将恰好是与您匹配的连接数组的第二个'a'部分。 - Himadri Choudhury

这就是证明。如果'a'和'b'是循环排列，那么该算法会告诉您需要将'a'移动多少次才能得到'b'。 - Himadri Choudhury

Answer 2

如果A和B是循环排列，那么A将会出现在双倍列表BB中（B也会在AA中出现）。

- Amadan

Answer 3

处理大量数据的高效方法是将它们转换为“规范”形式，然后进行比较以查看它们是否相等。对于这个问题，您可以选择将所有旋转排列的“规范”形式中最小的一个作为排序方式。

因此，'a'和'b'的规范形式是[1, 2, 3, 1, 5]，它们相等，因此它们是非循环置换。

'c'的规范形式是[1, 3, 1, 5, 2]，与之不同。

- karmakaze

---

我喜欢这个算法。它很直观，为什么它有效。当存在重复元素（例如a和b中的1）时，你能解释如何找到规范形式吗？ - dsg

把这些条目看作是字母，排列组合就像单词一样。'单词' 12315 排在 15123 前面，所以它是最小的，即规范化的。 - karmakaze

我明白了。所以找到规范表示需要进行 O(n^2) 的逐元素比较，其中 n 是数组的长度？也就是说，循环遍历所有可能的 n 个旋转，并保留当前的最小值，在每个旋转中执行 O(n) 次比较以确定是否更新最小值。也许有更好的方法... - dsg

考虑需要比较的数量，如果你有n个需要比较的数组，就像“大量数据”的情况。 - karmakaze

如果还不够清楚的话，拥有规范形式意味着您可以对值进行哈希以加快比较速度。 - karmakaze

太棒了！我为我的问题想出了完全相同的表示方法。 - mxxk

Answer 4

这里是一种简单的即兴方法，可在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;
    }


}

- Anvesh_vs

---

这样做不行，因为同一个字符可能会在数组中出现多次。 - Yuval