## 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.

Pages: 1 2

### 24 Responses to “Cyclic Equality”

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

```import Data.List

cyclic :: Eq a => [a] -> [a] -> Bool
cyclic xs ys = length xs == length ys && isInfixOf xs (ys ++ ys)
```
3. jpverkamp said

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:

```(define (cycle-equal? c1 c2)
(define len (cycle-length c1))
(and (= len (cycle-length c2))
(let loop ([ci1 c1] [ci2 c2])
(cond
[(cycle-reset? ci1) #f]
[(cycle-reset? ci2) (loop (cycle-tail ci1) c2)]
[(equal? (cycle-take len ci1)
(cycle-take len ci2)) #t]
[else (loop ci1 (cycle-tail ci2))]))))
```

Then here’s one essentially equivalent to Remco Niemeijer’s (although I had to write the `contains?` function myself):

```
(define (list-cycle-equal? lsc1 lsc2)
(and (= (length lsc1) (length lsc2))
(contains? (append lsc1 lsc1) lsc2)))
```

Check out the full post for the `cycle` data structure and the definition of `contains?`.

4. Maurits said

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.

5. Anonymous said

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))

6. jpverkamp said

@Maurits:

Here’s one that I think is O(m + n):

```(define (cycle-lexical-min c [< <] [= =])
(define (cycle-< c1 c2)
(cycle-< (cycle-tail c1) (cycle-tail c2)))))

(let loop ([min c] [c (cycle-tail c)])
(cond
[(cycle-reset? c) min]
[(cycle-< c min) (loop c (cycle-tail c))]
[else (loop min (cycle-tail c))])))

(define (lexical-cycle-equal? c1 c2 [< <] [= =])
(equal? (cycle-take (cycle-length c1) (cycle-lexical-min c1 < =))
(cycle-take (cycle-length c2) (cycle-lexical-min c2 < =))))
```

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 another O(n + n) for the `cycle-length` and `cycle-take`, plus a final additional O(max(m, n)) for the `equal?`. So overall it would be O(3m + 3n + max(m, n)) which is O(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.

7. programmingpraxis said

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

8. programmingpraxis said

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

9. jpverkamp said

’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` amortized O(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 be O(m2 + n2) because `cycle-<` will run through the entire list, but the average should still be O(m + n).

10. Maurits said

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).

11. cosmin said

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] … hash[A[n] + A[1..n-1]], where

hash[x[1..n]] = (x*q^(n-1) + x*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)

12. Matthew Feng said
```two_list = [input("list %s: " % i) for i in range(1, 3)];
valid = False;
for a in range(0, len(two_list)):
var = two_list[a:]+two_list[:a];
if var == two_list:
valid = True;
break;
print(valid);
```
13. Johan said

This should be O(n) tops, no?

```def cyclic(A, B):
""" https://programmingpraxis.com/2013/04/09/cyclic-equality/ """
if len(A) != len(B):
return False
for i in xrange(len(B)):
if A == B[i:] + B[:i]:
return True
return False
```
14. AlexR said

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.

```def equal_cycles(s, t):
S = "".join([str(x) for x in s])
T = "".join([str(x) for x in t])
return len(S) == len(T) and T in S + S
```
15. […] 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 […]

16. Huy Le said

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

17. […] Question is from here. […]

18. Matthew said

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]) 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 ```

19. hibbsi said

oops.. forgot how to format…

```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])
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
```
20. […] 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 […]

21. Alcriss said

bool check = true;

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

check = Checkpoint(_input1, _input2);
if (check == false )
{
Console.Write(“\n The lists are not equal! “);
Console.Clear();
goto Start;
}
else
{
Console.Write(“\n The lists are equal! “);
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;
}

22. jaysonsoi said

c#:

namespace Cyclic
{
class Program
{
static void Main(string[] args)
{

Console.WriteLine(“-Cyclic-“);
Console.Write(“Input 1st list: “);
Console.Write(“Input 2nd list: “);

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.”);
}

}
//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;
}
}
}

23. 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
}