Check if a number only exist as positive or negated in List<List<int>> efficiently

Question

I have a List<List<int>> set of data, with string representation like this (to give the idea!):

 {{1,3},{-1,-3},{2,5},{-2,-5},{-3,4},{-5,4},{3,5,-4},{6,-8},{7,-8},{-6,-7,8},{7,9},{-7,-9},{3,8,-10},{-3,-8,-10},{-3,8,10},{3,-8,10},{4,9,-11},{-4,-9,-11},{-4,9,11},{4,-9,11},{10,11},{-1,6},{1,-6},{-2,7},{2,-7}}

I want to check if ,in all present numbers, exist a number or set of numbers which only are in positive form. I mean if in the whole data, there is 3 and -3 I should return false, otherwise I have to add 3 as a number which only is present as positive 3, in to another list. (Same thing for only negated number)

Here is how I am trying to do it:

First, generate a unique set of numbers and remove negatives:

private void GenerateCurrentExistingVariables()
{
    _uid = new List<int>();
    var all = _cnf.Data.SelectMany(list => list).ToList();
    _uid = all.Distinct().ToList(); //make list unique
    _uid.Sort(); //sort numbers
    _uid.Reverse(); //reverse so highest numbers would evalaute first!
    _uid = _uid.Where(i => i >= 0).ToList(); //remove negative numbers
}

Then I do something like this:

in a method, I call the code below:

    for (var i = 0; i < _uid.Count; i++)
    {
        if (ExistOnlyInNegatedForm(_uid[i]))
        {
            onlyNegatedList.Add(_uid[i]);
        }

        //perhaps continue

        if (ExistOnlyInPositiveForm(_uid[i]))
        {

            onlyPositiveList.Add(_uid[i]);
        }
    }

Which in turns calls the methods below:

private bool ExistOnlyInPositiveForm(int id)
{
    for (var i = 0; i < _cnf.Data.Count; i++)
    {
        for (var j = 0; j < _cnf.Data[i].Count; j++)
        {
            if (_cnf.Data[i][j] == id)
            {
                return false;
            }
        }
    }

    return true;
}

private bool ExistOnlyInNegatedForm(int id)
{
    var toCheck = -id;
    for (var i = 0; i < _cnf.Data.Count; i++)
    {
        for (var j = 0; j < _cnf.Data[i].Count; j++)
        {
            if (_cnf.Data[i][j] == -toCheck)
            {
                return false;
            }
        }
    }

    return true;
}

This is too much code for this simple task and I feel that this is getting slower and slower when data grows larger...please let me know how can I improve this. Also I would like this to be done using LINQ at least for the sake of less lines of code!

I would love to see a C++ solution as well, so I am tagging c++ in my question (not doing language spam!)

Answer 1

I've been playing with this idea, which so far seems to work. Of course I had to modify your data set slightly because as it was, no number was passing the test of being only either positive or negative.

So, here goes:

  //Setting up the mock data
  List<List<int>> data = new List<List<int>>();
  data.Add(new List<int>(new[] { 1, 3 }));
  data.Add(new List<int>(new[] { -1, -3 }));
  data.Add(new List<int>(new[] { 2, 5 }));
  data.Add(new List<int>(new[] { -2, -5 }));
  data.Add(new List<int>(new[] { -3, 4 }));
  data.Add(new List<int>(new[] { -5, 4 }));
  data.Add(new List<int>(new[] { 3, 5, -4 }));
  data.Add(new List<int>(new[] { 6, -8 }));
  data.Add(new List<int>(new[] { 7, -8 }));
  data.Add(new List<int>(new[] { -6, -7, 8 }));
  data.Add(new List<int>(new[] { 7, 9 }));
  data.Add(new List<int>(new[] { -7, -9 }));
  data.Add(new List<int>(new[] { 3, 8, -10 }));
  data.Add(new List<int>(new[] { -3, -8, -10 }));
  data.Add(new List<int>(new[] { -3, 8, 10 }));
  data.Add(new List<int>(new[] { 3, -8, 10 }));
  data.Add(new List<int>(new[] { 4, 9, -11 }));
  data.Add(new List<int>(new[] { -4, -9, -11 }));
  data.Add(new List<int>(new[] { -4, 9, 11 }));
  data.Add(new List<int>(new[] { 4, -9, 11 }));
  data.Add(new List<int>(new[] { 10, 11 }));
  data.Add(new List<int>(new[] { -1, 6 }));
  data.Add(new List<int>(new[] { 1, -6 }));
  data.Add(new List<int>(new[] { -2, 7 }));
  data.Add(new List<int>(new[] { 2, 39 }));

  //Actual solution code
  var all = data.SelectMany(l => l); //flatten
  var grouped = all.GroupBy(g => Math.Abs(g)); //Group

  //Look for groups where the Sum is equal Key * Count, 
  //which means only either all positives, or all negatives
  var good = grouped.Where(i => i.Key * i.Count() == Math.Abs(i.Sum())); 

  var result = good.Select(g => g.First()); //Get rid of groups
  var allPos = result.Where(i => i > 0); //Self explanatory
  var allNeg = result.Where(i => i < 0);

I have split each step, but one could easily rewrite the linq stuff as one long query.

Cheers

Answer 2

Just create your own IEquality comparer this way:

 class OnlyPositiveInt : IEqualityComparer<int>
    {
        public bool Equals(List<int> some)
        {
            if ( some.First() > 0 && some.Last() > 0)   { return true; }
            return false;
        }
        public int GetHashCode(int x)
        {
            return x.GetHashCode();
        }
    }
 List<List<int>> onlyPositive = new List<List<int>>(generatedList.Distinct(OnlyPositiveInt));

Answer 3

Since you mentioned you might want a c++ answer, I wrote one up. It uses a hash table to store key-value pairs of the absolute value of an integer, and an object which stores the history of that particular absolute value.

The history tracking object is defined below:

int sign(int a){return ((a > 0) - (a < 0));}
int absolute(int a){return a * sign(a);}

struct SignRecord{
    SignRecord() : value_{NEITHER}{}
    enum SignGrouping{
        NEITHER, NEGATIVE, POSITIVE, BOTH
    } value_;

    SignGrouping& modify(int modifier){
        auto intToGrouping = [](int a)->SignGrouping {return a < 0 ? NEGATIVE : POSITIVE;};
        if(value_ == NEITHER){value_ = intToGrouping(modifier);}
        else if(value_ == BOTH){return value_;}
        else if(value_ == intToGrouping(modifier)){return value_;}
        else{
            return value_ = BOTH;
        }
        return value_;
    }
};

Since the hash table requires default construction of the object for referencing elements in the table by key, which is how I chose to insert and modify elements in the hash table, there is a default constructor with a state storing an indicator that neither positive nor negative values have been found. However, this state will only persist as long as there has been no call to 'modify' the value. I immediately call the modify member function, so it won't show up in the final output.

The modify function turns a NEITHER value into either a NEGATIVE or a POSITIVE one depending on the sign of the input integer. Those two states, respectively, will only change into the BOTH state if the call to modify is with an integer of the opposite sign.

The best part of this is you need to iterate through the set of lists only once, and then you have all your groupings of integers.

This can be neatly accomplished with the ranged-for syntax available in c++14:

std::unordered_map<int, SignRecord>
    intOrganizer;

for(auto &&subList : myInts){
    for(auto &&entry : subList){
        intOrganizer[absolute(entry)].modify(entry);
    }
}

A coliru demo is located here. Do note, I modified your given input lists a bit because every input integer seemed to be represented with both signs in the list of lists.

Answer 4

For positive number:

var uids = _uid.SelectMany(q => q).ToArray();

var positive = uids.Where(p => p >= 0).Distinct()
    .Except(uids.Where(p => p < 0).Select(p => -p))
    .ToList();
return positive.Any();

For negative number:

var negative = uids.Where(p => p < 0).Distinct()
    .Except(uids.Where(p => p >= 0).Select(p => -p))
    .ToList();
return negative.Any();

Answer 5

why don't you write a simple method that will take a list of ints, a boolean to say if you want positive and negative, and it will simply return true false ?
This way , you can just iterate through the outer list, calling it for each element inside it, and if you get what you want, continue from there:

public int AllSameSign(IEnumerable<int> theInputList, bool positive = true)
{
     if (positive)
         return theInputList.All(i=>i >= 0);
     else
         return theInputList.All(i=>i < 0);
}

(this is from the top of my head, you could change the bool to a simple enum to make it more readable as well ... )