Check if two arrays are cyclic permutations

Asked 2011-05-24T02:19:38.550

Given two arrays, how do you check if one is a cyclic permutation of the other?

For example, given a = [1, 2, 3, 1, 5], b = [3, 1, 5, 1, 2], and c = [2, 1, 3, 1, 5] we have that a and b are cyclic permutations but c is not a cyclic permutation of either.

Note: the arrays may have duplicate elements.

Edit Report

1 Answer

The standard trick here is to concatenate one of the arrays with itself, and then try to find the 2nd array in the concatenated array.

For example, 'a' concatenated with itself is:

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

Since you do see 'b' in this array starting from the 3rd element then a and b are cyclic permutations.

answered 2011-05-24T02:21:22.887

Check if two arrays are cyclic permutations

1 Answer

Your Answer