Cyclic Equality
April 9, 2013
Two cyclic lists are equal if they have the same number of elements in the same order. For instance, the cyclic lists (1 2 3 4 5) and (3 4 5 1 2) are equal. So are the cyclic lists (1 1 2 2) and (2 1 1 2), and also the cyclic lists (1 1 1 1) and (1 1 1 1). The two cyclic lists (1 2 3 4) and (1 2 3 5) are not equal because they have different elements, and the cyclic lists (1 1 1) and (1 1 1 1) are not equal because they have different lengths.
Your task is to write a function that takes two cyclic lists and determines if they are equal. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
[…] 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
cyclestruct 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
cycledata structure and the definition ofcontains?.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):
(define (cycle-lexical-min c [< <] [= =]) (define (cycle-< c1 c2) (or (< (cycle-head c1) (cycle-head c2)) (and (= (cycle-head c1) (cycle-head 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-lengthandcycle-take, plus a final additional O(max(m, n)) for theequal?. 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 reworkcycle-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-minto loop a maximum of one time around either cycle and madecycle-lengthamortized 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) becausecycle-<will run through the entire list, but the average should still be O(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)
two_list = [input("list %s: " % i) for i in range(1, 3)]; valid = False; for a in range(0, len(two_list[0])): var = two_list[0][a:]+two_list[0][:a]; if var == two_list[1]: valid = True; break; print(valid);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 FalseHere’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[…] 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 }