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.

About these ads

Pages: 1 2

23 Responses to “Cyclic Equality”

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

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

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

  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[0])):
        var = two_list[0][a:]+two_list[0][:a];
        if var == two_list[1]:
            valid = True;
            break;
    print(valid);
    
  13. Johan said

    This should be O(n) tops, no?

    def cyclic(A, B):
        """ http://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

    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

  17. 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[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

  18. 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[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
    
  19. [...] 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 [...]

  20. Alcriss said

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

  21. jaysonsoi said

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 629 other followers

%d bloggers like this: