Check two arrays for cyclic permutations in C#

Question

I would like to know how to check if an int array is a cyclic permutation of another (or is equal) efficiently in C#.

For example, the following arrays are cyclic permutations: {1,2,3}, {2,3,1} and {3,1,2}, whereas {2,1,3} is not. Any ideas?

Answer 1

If you have hard problem, convert it to simple problem, following code use linkedlist to solve the problem, it's not best for performance, but easy to understand.

public class SameTest<T>
{
    public bool TestCircularArray(IEnumerable<T> array1, IEnumerable<T> array2)
    {
        if (array1 == null)
            throw new ArgumentNullException("array1");
        if (array2 == null)
            throw new ArgumentNullException("array2");

        // if they are the same, the length must be the same
        if (array1.Count() != array2.Count())
            return false;

        // two empty array assume to same
        if (!array1.Any())
            return true;

        // convert array2 to linkedlist
        var linkedList = new LinkedList<T>(array2);

        LinkedListNode<T> node = null;

        foreach (T item1 in array1)
        {
            // first find the element in link
            if (node == null)
            {
                node = linkedList.Find(item1);
                if (node == null)
                    return false;
                continue;
            }

            node = node.Next;
            // reach tail move to head
            if (node == null)
                node = linkedList.First;

            if (!item1.Equals(node.Value))
                return false;
        }


        return true;
    }
}

[TestMethod]
public void TestMethod1()
{
    int[] array1 = {2, 3, 1};
    int[] array2 = {1, 2, 3};
    int[] array3 = {2, 1, 3};

    var tester = new SameTest<int>();

    var result = tester.TestCircularArray(array1, array2);

    Assert.AreEqual(true, result);

    result = tester.TestCircularArray(array2, array3);

    Assert.AreEqual(false, result);
}

Answer 2

The following method should produce the desired behaviour:

bool IsCyclicPermutation(int[] a, int[] b) {
    if (a == null || b == null || a.Length != b.Length) return false;

    for (int i = 0; i < a.Length; i++)
    {
        if (a[i] == b[0]) // Potential starting point of cycle found
        {
            bool isCyclic = true;
            for (int j = 1; j < b.Length && isCyclic; j++)
            {
                if (a[(j + i) % a.Length] != b[j]) isCyclic = false;
            }
            if (isCyclic) return true; // Cycle found
        }
    }

    return false; // No cycles found
}

---

EDIT If it is the case that there are no duplicate numbers, you can use the modified code as below for slightly better performance:

bool IsCyclicPermutation(int[] a, int[] b) {
    if (a == null || b == null || a.Length != b.Length) return false;

    for (int i = 0; i < a.Length; i++)
    {
        if (a[i] == b[0]) // Starting point of potential cycle found
        {
            bool isCyclic = true;
            for (int j = 1; j < b.Length && isCyclic; j++)
            {
                if (a[(j + i) % a.Length] != b[j]) isCyclic = false;
            }
            return isCyclic;
        }
    }

    return false; // No cycles found
}

---

The following tests have been performed:

var arr1 = new int[] {1, 2, 3};
var arr2 = new int[] {2, 3, 1};
var arr3 = new int[] {3, 1, 2};
var arr4 = new int[] {2, 1, 3};

IsCyclicPermutation(arr1, arr1); // True
IsCyclicPermutation(arr1, arr2); // True
IsCyclicPermutation(arr1, arr3); // True
IsCyclicPermutation(arr2, arr1); // True
IsCyclicPermutation(arr2, arr2); // True
IsCyclicPermutation(arr2, arr3); // True
IsCyclicPermutation(arr3, arr1); // True
IsCyclicPermutation(arr3, arr2); // True
IsCyclicPermutation(arr3, arr3); // True
IsCyclicPermutation(arr4, arr1); // False
IsCyclicPermutation(arr4, arr2); // False
IsCyclicPermutation(arr4, arr3); // False

As for performance, it's hard to tell without something to compare it against, although I do believe it is O(n) with n being the size of the input arrays.

Answer 3

Sure:

DotNetFiddle Working Example

using System;
using System.Linq;
using System.Collections.Generic;

public class Program
{
    public static void Main()
    {
        var test1 = new [] {1, 2, 3};
        var test2 = new [] {2, 3, 1};
        var test3 = new [] {3, 1, 2};
        var test4 = new [] {2, 1, 3};

        test1.IsCiruclarPermutation(test2);
        test1.IsCiruclarPermutation(test3);
        test2.IsCiruclarPermutation(test1);
        test2.IsCiruclarPermutation(test3);
        test3.IsCiruclarPermutation(test1);
        test3.IsCiruclarPermutation(test2);

        test4.IsCiruclarPermutation(test1);
        test4.IsCiruclarPermutation(test2);
        test4.IsCiruclarPermutation(test3);
    }
}

public static class ArrayExtensions
{
    public static bool IsCiruclarPermutation(this int[] source, int[] dest)
    {
        Console.Write(string.Join(",", source) + " is a Ciruclar Permutation of ");
        Console.Write(string.Join(",", dest));

        var left = source.ToList();
        var right = dest.ToList();
        right.AddRange(dest);

        var result = false;

        for (int idx = 0; idx < left.Count; idx++)      
        {
            var compareTo = right.Skip(idx).Take(left.Count);
            result = Enumerable.SequenceEqual(left, compareTo);
            if (result) break;
        }

        Console.WriteLine("  " + result.ToString());
        return result;
    }
}

Output:

1,2,3 is a Ciruclar Permutation of 2,3,1 True

1,2,3 is a Ciruclar Permutation of 3,1,2 True

2,3,1 is a Ciruclar Permutation of 1,2,3 True

2,3,1 is a Ciruclar Permutation of 3,1,2 True

3,1,2 is a Ciruclar Permutation of 1,2,3 True

3,1,2 is a Ciruclar Permutation of 2,3,1 True

2,1,3 is a Ciruclar Permutation of 1,2,3 False

2,1,3 is a Ciruclar Permutation of 2,3,1 False

2,1,3 is a Ciruclar Permutation of 3,1,2 False

Answer 4

int[] array1 = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
int[] array2 = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
        int tmp = array1[0];
        int index = Array.IndexOf(array2, tmp);
        int n = array1.Length;

        for (int i = 1; i < n; i++)
        {
            if (index + i < array1.Length)
            {
                if (array1[i] != array2[index+i])
                {
                    Console.WriteLine("Arrays are not equal");
                    break;

                }
            }
            else
            {
                if (array1[i] != array2[index + i - n])
                {
                    Console.WriteLine("Arrays are not equal");
                    break;
                }
            }

        }

I assume the length of the arrays and their elements are the same. The above code does the job at O(n). Double check the index!