How to find contradiction in order of items in multiple sequences Suppose you have several sequences:

  A: 1  2  3  4  5
  B: 2  4  5
  C: 2  1  3  4  5
  D: 3  2  


Here, some pairs of list contradicts each other, because they don't expose the same order for their similar elements: (A,C) (A,D) (C, D)

What is an algorithm or a linq statements to find such pairs? Or just to say if my sequences have such a contradiction or not! I store these sequences in a list of lists of strings

 List&lt;List&lt;String&gt;&gt; Sequences;


This is my code for the problem:

    private bool HasContradiction(List&lt;List&lt;String&gt;&gt; Sequences)
    {
        Cont = new List&lt;Tuple&lt;string, string&gt;&gt;();
        bool f = false;
        foreach (List&lt;String&gt; item1 in Sequences)
        {

            foreach (string elem1 in item1)
            {
                foreach (string elem2 in item1)
                {
                    int o1 = GetIndexOrder(item1, elem1, elem2);
                    foreach (List&lt;String&gt; item2 in Sequences)
                    {
                        int o2 = GetIndexOrder(item2, elem1, elem2);
                        if (o2 != 0 &amp;&amp; o2 != o1)
                        {
                            Cont.Add(new Tuple&lt;string, string&gt;(String.Join(" ", item1), String.Join(" ", item2)));
                            f = true;
                        }
                    }
                }
            }
        }
        return f;
    }
    // this list stores contradicted pairs
    List&lt;Tuple&lt;string, string&gt;&gt; Cont = new List&lt;Tuple&lt;string, string&gt;&gt;();
    private int GetIndexOrder(List&lt;string&gt; item, string elem1, string elem2)
    {
        int i = item.FindIndex(x =&gt; x == elem1);
        int j = item.FindIndex(x =&gt; x == elem2);
        if (i &lt; 0 || j &lt; 0)
        {
            return 0;
        }
        if (i &lt;= j)
        {
            return 1;
        }

        return 2;

    }


To test it:

    List&lt;List&lt;String&gt;&gt; seqs = new List&lt;List&lt;String&gt;&gt;{
    new List&lt;String&gt;{
        "1", "2", "3", "4", "5"
    },
    new List&lt;String&gt;{
         "2", "4", "5"
    },
    new List&lt;String&gt;{
        "2", "1","3","4","5"
    },
    new List&lt;String&gt;{
        "3", "2"
    },

};


        HasContradiction(seqs);
        foreach (var item in Cont.Distinct())
        {
            string tt = item.Item1 + "   AND  " + item.Item2;

            listView2.Items.Add(tt);
        } 


Result:
Consider the case

A: 1 2 3 2 4 5
B: 1 2 2 4 5
C: 3 2 
D: 2 3
E: 2 2
F: 1 2 3 4 5


You report back:

1 2 3 2 4 5 contradicts 3 2 
1 2 3 2 4 5 contradicts 3 2
1 2 3 2 4 5 contradicts 3 2
1 2 3 2 4 5 contradicts 3 2 
3 2 contradicts 1 2 3 2 4 5
3 2 contradicts 2 3
3 2 contradicts 1 2 3 4 5 
3 2 contradicts 1 2 3 2 4 5
3 2 contradicts 2 3
3 2 contradicts 1 2 3 4 5
2 3 contradicts 3 2      
2 3 contradicts 3 2      
1 2 3 4 5 contradicts 3 2
1 2 3 4 5 contradicts 3 2


I used this code to test: ( http://goo.gl/QOEBao or http://www.tutorialspoint.com/compile_csharp_online.php?PID=0Bw_CjBb95KQMZGNRVXQ2Y0JlOU0 )

static void Main()
{
    List&lt;List&lt;String&gt;&gt; seqs = new List&lt;List&lt;String&gt;&gt;{
        new List&lt;String&gt;{
            "1", "2", "3", "2", "4", "5"
        },
        new List&lt;String&gt;{
            "1", "2", "2", "4", "5"
        },
        new List&lt;String&gt;{
            "3", "2"
        },
        new List&lt;String&gt;{
            "2", "3"
        },
        new List&lt;String&gt;{
            "2", "2"
        },
        new List&lt;String&gt;{
            "1", "2", "3", "4", "5"
        }
    };
    if (HasContradiction(seqs))
    {
        Console.WriteLine("yep");
        foreach(Tuple&lt;string, string&gt; x in Cont)
        {
            Console.WriteLine(x.Item1 + " contradicts "+ x.Item2);
        }
    } else {
        Console.WriteLine("nope");
    }
}


There's a few that are not correct - if I label them...

X 1 2 3 2 4 5 contradicts 3 2 
X 1 2 3 2 4 5 contradicts 3 2
X 1 2 3 2 4 5 contradicts 3 2
X 1 2 3 2 4 5 contradicts 3 2 
X 3 2 contradicts 1 2 3 2 4 5
Y 3 2 contradicts 2 3
Y 3 2 contradicts 1 2 3 4 5 
X 3 2 contradicts 1 2 3 2 4 5
Y 3 2 contradicts 2 3
Y 3 2 contradicts 1 2 3 4 5
Y 2 3 contradicts 3 2      
Y 2 3 contradicts 3 2      
Y 1 2 3 4 5 contradicts 3 2
Y 1 2 3 4 5 contradicts 3 2


Then these are wrong:

X 1 2 3 2 4 5 contradicts 3 2 
X 1 2 3 2 4 5 contradicts 3 2
X 1 2 3 2 4 5 contradicts 3 2
X 1 2 3 2 4 5 contradicts 3 2 
X 3 2 contradicts 1 2 3 2 4 5
X 3 2 contradicts 1 2 3 2 4 5


Basically, what you don't do is check for duplicates.

Now, there's two things this could mean:

First option, you don't actually support duplicates. It's logically impossible for there to be duplicates. In that case, you should take an ordered, unique collection as input (a sorted set, as it were). A weaker alternative might be checking if you have duplicates and throwing errors for that, if altering the signature is not possible.

Second option, you do support duplicates. In that case, you should alter your code to support duplicates.