## Cyclic Equality

### April 9, 2013

We begin by writing a function that produces a cyclic list; this is easy in Scheme, but may be harder in some other languages:

`(define (cycle . xs) (set-cdr! (last-pair xs) xs) xs)`

The first task is to determine the length of the cyclic list. That can be done by chasing pointers down the cdrs of the list until finding a pointer to the original head of the list. We use Scheme’s `eq?`

predicate to test pointer equivalence:

`(define (len xs)`

(let loop ((ys (cdr xs)) (n 1))

(if (eq? xs ys) n (loop (cdr ys) (+ n 1)))))

The algorithm to determine if the two cyclic lists are equal uses two loops. The outer loop indexes through all locations where the element at the head of the *xs* cyclic list is equal to an element of the *ys* cyclic list. For each place where they match, an inner loop compares equivalent elements of the two lists to see if they are the same. The algorithm reports success if the inner loop completes the cycle, and reports failure if the outer loop completes the cycle without finding a successful match.

The algorithm to test equality isn’t hard, but keeping track of all the pointers involved is tedious: *xs* and *ys* are the original heads of the two cyclic lists, *xs* remains constant while *ys* iterates through the elements of the cyclic list, and *x* and *y* are the current elements of the *xs* and *ys* cyclic lists as they are being compared in the inner loop:

`(define (ceq? eql? xs ys)`

(let ((n (len xs)))

(if (not (= n (len ys))) #f

(let loop1 ((n n) (ys ys))

(cond ((zero? n) #f)

((eql? (car xs) (car ys))

(let loop2 ((x (cdr xs)) (y (cdr ys)))

(cond ((eq? x xs) #t)

((eql? (car x) (car y))

(loop2 (cdr x) (cdr y)))

(else (loop1 (- n 1) (cdr ys))))))

(else (loop1 (- n 1) (cdr ys))))))))

Here are some examples:

`> (ceq? = (cycle 1 2 3 4) (cycle 1 2 3 4))`

#t

> (ceq? = (cycle 1 2 3 4) (cycle 2 3 4 1))

#t

> (ceq? = (cycle 1 2 3 4) (cycle 3 4 1 2))

#t

> (ceq? = (cycle 1 2 3 4) (cycle 4 1 2 3))

#t

> (ceq? = (cycle 1 2 3 4) (cycle 1 2 3 5))

#f

> (ceq? = (cycle 1 1 1 1) (cycle 1 1 1 1))

#t

> (ceq? = (cycle 1 1 1 1) (cycle 1 1 1 2))

#f

> (ceq? = (cycle 1 1 1 1) (cycle 1 1 1))

#f

You can run the program at http://programmingpraxis.codepad.org/fcVpNq5G.

[…] today’s Programming Praxis exercise, our goal is to determine if one list is cyclically equal to another. […]

My Haskell solution (see http://bonsaicode.wordpress.com/2013/04/09/programming-praxis-cyclic-equality/ for a version with comments):

Here are my Racket versions: Cyclic equality on jverkamp.com

First, this one uses a

`cycle`

struct and loops across all of the possible pairings:Then here’s one essentially equivalent to Remco Niemeijer’s (although I had to write the

`contains?`

function myself):Check out the full post for the

`cycle`

data structure and the definition of`contains?`

.The solutions presented so far appear to be O(mn). I wonder if it is worth trying to define a “canonical form” for a cyclic list, putting both lists into canonical form (at some cost), and then doing the O(n) array comparison.

For example, we could define the “canonical form” of the list to be the lexicographically minimal form (least-element-first; if there is a tie for the least element, use the second element as a tiebreak, etc.)

If this can be done in time < O(n^2), this is a win.

To have something less than O(n^2):

Both cyclic lists could be transformed to regular lists which would be O(n).

The lists could be sorted with a O(nlog(n)) sorting algorithm. Comparing the elements in both lists is O(n).

This results in O(nlogn(n))

@Maurits:

Here’s one that I think is

O(m + n):I’m not completely sure about the runtime of finding the lexical minimum. In the general case (with few duplicates), it’ll be

O(n)though. Then there’s anotherO(n + n)for the`cycle-length`

and`cycle-take`

, plus a final additionalO(max(m, n))for the`equal?`

. So overall it would beO(3m + 3n + max(m, n))which isO(m + n). The constant could be improved with a better abstraction, but not the big-O time.Also it completely fails on lists that are all the same element since

`cycle-<`

will not terminate. I’d have to rework`cycle-reset?`

and add a check for that to get around that issue.@Anonymous:

That would only check if the two lists have the same elements, ignoring the ordering within the cycle.

Sorting will not work. The order of the elements in the cyclic lists is important.

Jpverkamp: Regarding failing to terminate: You could precalculate the length of the list in O(n) time and count elements to terminate.

’tis true. Mostly I didn’t go that originally way since it makes the code uglier (having to carry around an extra counter). But yes, it would solve the problem at hand. I went ahead and updated

`cycle-lexical-min`

to loop a maximum of one time around either cycle and made`cycle-length`

amortizedO(1)by caching the result in the cycle struct. The code is on at the bottom of my blog post or on GitHub. Because of that check, I think the worst case would beO(m2 + n2)because`cycle-<`

will run through the entire list, but the average should still beO(m + n).Here we go: use Booth’s algorithm from http://en.wikipedia.org/wiki/Lexicographically_minimal_string_rotation to put each cycle in canonical form. O(n).

The problem is very nice and it can be solved linearly in many ways. Two of my favorites:

1. Using string matching. Let’s denote the two lists A and B. Creating C = A + A (concatenating the first string with itself), the problem is equivalent with deciding if B is or is not a sub-string of C. Any string matching algorithm that runs in O(n) will solve the problem optimally.

2. Using rolling hashes. This version is practically similar with the previous one when Rabin-Karp is used. I like this approach the most because it is very simple and easy to implement. The algorithm tries to compare hash[B[1..n]] sequentially with hash[A[1..n]], hash[A[2..n] + A[1]] … hash[A[n] + A[1..n-1]], where

hash[x[1..n]] = (x[1]*q^(n-1) + x[2]*q^(n-2) + … + x[n]) % p, with p a prime and q a positive integer

Having one A-hash computed then the next A-hash can be easily computed in O(1) as follows:

hash[A[i+1..n] + A[1..i]] = ((hash[A[i..n] + A[1..i-1]] – A[i]*q^(n-1))*q + A[i]) % p, if q^(n-1) % p is pre-computed

Complexity: at most n steps x O(1) + O(n) pre-computation of hash[A[1..n]], hash[B[1..n]] and q^(n-1) % p => O(n)

This should be O(n) tops, no?

Here’s a linear-time Python program which takes advantage of Python’s built-in linear-time substring search operator “in”. It uses @cosmin’s trick #1.

[…] a simple Elisp challenge suggested by a problem from by ProgrammingPraxis. We call one string a cycle of another if one string can be transformed into the other by a […]

My Haskell solution:

check xs ys = if n /= length ys

then False

else loop xs ys n

where n = length xs

loop xs ys n

| n == 0 = False

| xs == ys = True

| xs /= ys = loop (cycle xs) ys (n-1)

cycle xs = last xs:init xs

[…] Question is from here. […]

Java solution here.

here’s what I just typed up in ruby (2.0.0):

def ceq?(l1, l2)

s = l1.size, l2.size

if ((l1.size == l2.size))

match = false

(0...l1.size).each do |i|

match = true

(0...l1.size).each do |j|

match = false if (l1[j] != l2[(i+j) % s[1]])

end

break if match

end

return match

end

end

`def ceq2?(l1, l2)`

if ((l1.size == l2.size))

for i in (0...l1.size)

return true if l1.rotate(i) == l2

end

return false

end

end

oops.. forgot how to format…

[…] I mentioned in the post, my An Elisp Challenge post was suggested by this Programming Praxis post. The next Programming Praxis post was a followup that discussed Booth’s Algorithm, which […]

bool check = true;

Start:

Console.Write(“\n Enter 1st list: ” );

string[] _input1 = Console.ReadLine().Split(‘ ‘);

Console.Write(“\n Enter 2nd list: “);

string[] _input2 = Console.ReadLine().Split(‘ ‘);

check = Checkpoint(_input1, _input2);

if (check == false )

{

Console.Write(“\n The lists are not equal! “);

Console.ReadLine();

Console.Clear();

goto Start;

}

else

{

Console.Write(“\n The lists are equal! “);

Console.ReadLine();

Console.Clear();

goto Start;

}

}

//METHODS

public static bool Checkpoint(string[] input1, string[] input2)

{

bool here = true;

if ((input1.Length > input2.Length) || (input2.Length > input1.Length))

{

return false;

}

else if (input1.Length == input2.Length)

{

for (int i = 0; i < input1.Length;)

{

here = Match(input1[i], input2);

if (here == false)

{

return false;

}

else if (here == true)

{

i++;

}

}

} return true;

}

public static bool Match(string entry, string[] input2)

{

for (int i = 0; i < input2.Length; i++)

{

if (entry == input2[i])

{

return true;

}

} return false;

}

c#:

namespace Cyclic

{

class Program

{

static void Main(string[] args)

{

Console.WriteLine(“-Cyclic-“);

Console.Write(“Input 1st list: “);

string _1stList = Console.ReadLine();

Console.Write(“Input 2nd list: “);

string _2ndList = Console.ReadLine();

if (_1stList.Length != _2ndList.Length)

{

Console.WriteLine(“\nThe two lists are not cyclic.”);

}

if (_1stList == _2ndList)

{

Console.WriteLine(“\nThe two lists are cyclic.”);

}

if (FirststListIsCyclicToSecond(GetUniqueCharacters(_1stList),GetUniqueCharacters(_2ndList),_1stList,_2ndList))

{

Console.WriteLine(“\nThe two lists are cyclic.”);

}

else

{

Console.WriteLine(“\nThe two lists are not cyclic.”);

}

Console.ReadLine();

}

//Methods

public static string GetUniqueCharacters(string _stringParam)

{

string _returnString = “”;

bool _flag = false;

for (int i = 0; i i; x–)

{

if (_stringParam[i] == _stringParam[x])

{

_flag = true;

break;

}

}

if (!_flag)

{

_returnString += _stringParam[i];

}

}

return _returnString;

}

public static bool FirststListIsCyclicToSecond(string _1stUnique, string _2ndUnique,string _1st,string _2nd)

{

bool _return=false;

for (int i = 0; i < _1stUnique.Length; i++)

{

if (GetStringCount(_1st, _1stUnique[i]) == GetStringCount(_1st, _2ndUnique[i]) && GetStringCount(_2nd, _2ndUnique[i]) == GetStringCount(_2nd, _1stUnique[i]))

{

_return = true;

}

else

{

_return = false;

}

}

return _return;

}

public static int GetStringCount(string _stringPar, char _checkChar)

{

int _return = 0;

for (int i = 0; i < _stringPar.Length; i++)

{

if (_stringPar[i] == _checkChar)

{

_return++;

}

}

return _return;

}

}

}

Here’s my solution in Go:

func cyclicLists(list1 []int, list2 []int) bool {

sizeL := len(list1)

if sizeL != len(list2) {

return false

}

maxL := sizeL * 2

pointer1, pointer2 := 0, 0

for pointer2 != sizeL {

if list1[pointer1 % sizeL] == list2[pointer2 % sizeL] {

pointer2++

}

pointer1++

if pointer1 > maxL {

return false

}

}

return true

}