list intersection algorithm implementation only using python lists (not sets)
Question: I've been trying to write down a list intersection algorithm in python that
takes care of repetitions. I'm a newbie to python and programming so forgive
me if this sounds inefficient, but I couldn't come up with anything else.
Here, L1 and L2 are the two lists in question, and L is the intersection set.

  1. Iterate through L1
  2. Iterate through L2
  3. If element is in L1 and in L2
  4. add it to L
  5. remove it from L1 and L2
  6. iterate through L
  7. add elements back to L1 and L2

I'm 100% sure this is not the algorithm used within Mathematica to evaluate
list intersection, but I can't really come up with anything more efficient. I
don't want to modify L1 and L2 in the process, hence me adding back the
intersection to both lists. Any ideas? I don't want to make use of any built
in functions/data types other than lists, so no import sets or anything like
that. This is an algorithmic and implementation exercise, not a programming
one, as far as I'm concerned.


Answer: How about:

  1. Iterate though L1
  2. Iterate though L2
  3. If (in L1 and L2) and not in L -> add to L

Not particularly efficient, but in code it would look something like this
(with repetitions to make the point):

    
    
    >>> L1 = [1,2,3,3,4]
    >>> L2 = [2,3,4,4,5]
    >>> L = list()
    >>> for v1 in L1:
            for v2 in L2:
                if v1 == v2 and v1 not in L:
                    L.append(v1)
    >>> L
    [2,3,4]
    

You avoid deleting from L1 and L2 simply by checking if the element is already
in L and adding to L if it is not. Then it doesn't matter if there are
repetitions in L1 and L2.

