2
\$\begingroup\$

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<List<String>> Sequences;

This is my code for the problem:

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

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

        return 2;

    }

To test it:

    List<List<String>> seqs = new List<List<String>>{
    new List<String>{
        "1", "2", "3", "4", "5"
    },
    new List<String>{
         "2", "4", "5"
    },
    new List<String>{
        "2", "1","3","4","5"
    },
    new List<String>{
        "3", "2"
    },

};


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

            listView2.Items.Add(tt);
        } 

Result:

enter image description here

\$\endgroup\$
  • \$\begingroup\$ Does your code produce the expected results ? \$\endgroup\$ – Heslacher Feb 11 '16 at 10:03
  • \$\begingroup\$ @Heslacher yes, I see the contradiction in the resulted pairs, however I am not sure they are all the pairs possible. \$\endgroup\$ – Ahmad Feb 11 '16 at 10:09
  • \$\begingroup\$ I think it is flawed. I tested it and I never got (B,C) nor (B,D) which if I understand the problem should be found as well. \$\endgroup\$ – Heslacher Feb 11 '16 at 10:25
  • \$\begingroup\$ @Heslacher as I tested it, it works, please check the update \$\endgroup\$ – Ahmad Feb 11 '16 at 10:52
  • \$\begingroup\$ So should (B,C) and (B,D) be found ? \$\endgroup\$ – Heslacher Feb 11 '16 at 10:52
1
\$\begingroup\$

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<List<String>> seqs = new List<List<String>>{
        new List<String>{
            "1", "2", "3", "2", "4", "5"
        },
        new List<String>{
            "1", "2", "2", "4", "5"
        },
        new List<String>{
            "3", "2"
        },
        new List<String>{
            "2", "3"
        },
        new List<String>{
            "2", "2"
        },
        new List<String>{
            "1", "2", "3", "4", "5"
        }
    };
    if (HasContradiction(seqs))
    {
        Console.WriteLine("yep");
        foreach(Tuple<string, string> 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.

\$\endgroup\$
  • \$\begingroup\$ Why wrong? they contradicts each other, for example in 1 2 3 2 4 5, 3 follows 2 but in 3 2, 2 follows 3. However it seems using two 2 makes the first list contradict itself. \$\endgroup\$ – Ahmad Feb 11 '16 at 10:54
  • \$\begingroup\$ Because lets say this is music, "hit the notes like A B C B D E" and you ask "does it contain a C and then a B" the answer should be "yes it does" and you say "no, because there is a B in front of the C" \$\endgroup\$ – Pimgd Feb 11 '16 at 10:57
  • \$\begingroup\$ Now I got what you say, I think I don't support duplicates and I count those listed above as contradictions. \$\endgroup\$ – Ahmad Feb 11 '16 at 11:38
  • \$\begingroup\$ @Ahmad Then first option it is; you shouldn't take list, but some other collection instead that cannot contain duplicates, but does have an order. Like SortedSet. \$\endgroup\$ – Pimgd Feb 11 '16 at 11:40
0
\$\begingroup\$

This CodeReview Question hints at an answer.

I.E. Create a RegEx of one string, matching to the others in turn. A non-empty MatchCollection of course means there is no "contradiction". And Match.Index tells you where a match is made.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.