-3

This is a question from List Data Model by Ullman

  • If L and M are Linked List , under what conditions is LM = ML ?

i was reading Foundation of Computer Science book .The question is from http://i.stanford.edu/~ullman/focs/ch06.pdf 6.3.2

aked
  • 5,625
  • 2
  • 28
  • 33
  • 3
    You'd first have to define what list equality meant, and what catenating the names of two lists meant. But using the (to me) intuitive definitions, I'd say "when they're the same" (including when they're both empty). – Ernest Friedman-Hill Mar 16 '13 at 03:24
  • i have added the link from where i got the question. Hope that helps. – aked Mar 16 '13 at 03:30
  • OK, I stand by my comment then: LM = ML when L = M. – Ernest Friedman-Hill Mar 16 '13 at 03:33
  • @Ernest perfect. I am just thinking if the list is circular in that case L , M=Reverse(L) will also make LM=ML right ? – aked Mar 16 '13 at 03:38
  • 1
    This would be a good question if you could state your question clearly instead of copying from somewhere without any context or simply placing a link to the original posting. – Terry Li Mar 16 '13 at 04:11
  • Let L=[1,2,3] and M=[3,2,1] then LM != ML, but M=reverse(L) – alzaimar Mar 16 '13 at 09:24

3 Answers3

3

I can think of two conditions right off the top of my head:

One of the lists is empty. 

{}+{1,2,3} = {1,2,3}+{} = {1,2,3}

One list is the concatenation of multiple instances of the other list.

{1,2,3}+{1,2,3,1,2,3} = {1,2,3,1,2,3}+{1,2,3} = {1,2,3,1,2,3,1,2,3}

Two side notes: 1)In the first condition, the empty list {} is the identity of the concatenation operation. 2)The condition M=L is actually a special case of condition two.

Edit: Thanks to @jwpat7, here's another condition:

{2,3,2,3}+{2,3,2,3,2,3} = {2,3,2,3,2,3}+{2,3,2,3}

Both lists are concatenations of multiple instances of the same list, which is {2,3} in the example above.

Terry Li
  • 16,870
  • 30
  • 89
  • 134
3

Without loss of generality, we can assume |L| <= |M|. (Otherwise just reverse the assignment of labels L and M.) Then we have LM = ML = LAL where M = LA = AL. Note that we now have a new version of the same problem with LA replacing LM. This says that we can give a recursive condition:

LM = ML if and only if M = AL = LA for some list A
Gene
  • 46,253
  • 4
  • 58
  • 96
2

There is a little known theorem (which was recently put to use here: Detect whether sequence is a multiple of a subsequence in Python)

According to that theorem, Suppose x and y are strings. Then xy = yx if an only if x and y are both powers of a certain string z, i.e. both are concatenations of the same string z, i.e. x= z.z.z...z (k times) and y = z.z...z (l times).

Talking in terms of 'plain old' linked lists is essentially the same.

I believe a proof by induction on the length of one of the strings works.

(Unfortunately, I used to remember the name of this theorem, but I have forgotten and so cannot find you a reference).

Community
  • 1
  • 1
Knoothe
  • 1,218
  • 8
  • 14
  • Looks like it's called Lyndon's theorem. – Eric Bainville Mar 16 '13 at 06:28
  • @EricBainville: Great! I did try searching using that (when answering the other question), but was lost in the myriad of other theorems of the same name. Can you please give a reference? Thanks! – Knoothe Mar 16 '13 at 06:30
  • Handbook of Formal Languages: Volume 1. Word, Language, Grammar. Chapter 1 theorem 2.2. – Eric Bainville Mar 16 '13 at 17:21
  • Indeed the proof by induction follows directly in one little step from my answer. I did not write the last step to encourage the OP to think a bit instead of memorizing someone else's solution. – Gene Mar 16 '13 at 21:19
  • @Gene: I see. Perhaps if you had mentioned that it was just a hint. Because to me, it is not very obvious, even with that hint. You are right though, it will essentially follow from what you wrote (and induction). +1 to your answer. – Knoothe Mar 17 '13 at 06:30