Merge two enumerables whilst keeping the order defined by either source

Question

I need to merge two enumerables while keeping the relative order of items as defined in the source enumerables. For example, if enumerable1 contains "foxtrot", "uniform" and "kilo" and enumerable2 contains "uniform", "charlie" and "kilo", the resulting enumerable should contain "foxtrot", "uniform", "charlie", "kilo".

Explanation: we know from enumerable1 that "foxtrot" appears before "uniform", and we know from enumerable2 that "uniform" appears before "charlie". Therefore we can assume that "foxtrot" appears before "uniform" appears before "charlie". Also, we know from enumerable1 that "uniform" appears before "kilo", and we know from enumerable2 that "charlie" appears after "uniform" and before "kilo". Combining all that, we can tell the final order of "foxtrot", "uniform", "charlie" and "kilo".

There are cases however where this will not work, because no order can be determined or both source enumerables contradict each other. For example, if enumerable3 contains "foxtrot" and "charlie" and enumerable4 contains "uniform" and "kilo", these cannot be merged, because one cannot tell any order. Or, if enumerable5 contains "foxtrot" and "uniform" and enumerable6 contains "uniform" and "foxtrot", these cannot be merged and an empty enumerable should be returned.

Whilst this is easy to imagine in my head, I'm having a hard time turning this into code. C# preferrably. In this very concrete case, the maximum number of items per enumerable is 4, but I think it wouldn't hurt to have code that works independent of that.

Any ideas anyone?

Answer 1

I've edited my answer to check for duplicates and contradictions. It should now work in all cases. The check for each was to make sure neither the source lists nor the returned list contained duplicates. (If there was a contradiction, then the sorted returned list would have duplicates)

class Program {
    static void Main(string[] args) {
        IEnumerable<string> l1 = new List<string> { "uniform", "charlie", "kilo" };
        IEnumerable<string> l2 = new List<string> { "kilo", "uniform", "charlie" };
        try {
            IEnumerable<string> result = Merge(l1, l2);
            foreach (string s in result) {
                Console.WriteLine(s);
            }
        }
        catch (InvalidOperationException e) {
            Console.WriteLine(e.Message);
        }
        Console.ReadKey();
    }

    public static IEnumerable<T> Merge<T> (IEnumerable<T> list1, IEnumerable<T> list2) {
        if ((list1.Distinct().Count() != list1.Count()) || (list2.Distinct().Count() != list2.Count()) ) {
            throw new InvalidOperationException("Couldn't merge.  One or both lists contained duplicates.");
        }
        
        if ((list1.Count() == 0)) {
            return list2;
        }
        if ((list2.Count() == 0)) {
            return list1;
        }
        List<T> newList = new List<T>();       
        bool matchfound = false;
        for(int i = 0; i< list1.Count(); i++) {
            for (int j = 0; j < list2.Count(); j++) {
                if (list1.ElementAt(i).Equals(list2.ElementAt(j))) {
                    matchfound = true;
                    newList.AddRange(Merge(list1.Take(i), list2.Take(j)));
                    newList.Add(list1.ElementAt(i));
                    newList.AddRange(Merge(list1.Skip(i + 1), list2.Skip(j + 1)));
                    break;
                }
            }
            if (matchfound) {
                break;
            }
        }
        if (!matchfound) {
            throw new InvalidOperationException("Could not merge");
        }
        if (newList.Distinct().Count() != newList.Count()) {
            throw new InvalidOperationException("Couldn't merge.  Contradiction in lists.");

        }
        return newList;
    }

}