5 Replies - 7170 Views - Last Post: 26 June 2009 - 01:06 PM Rate Topic: -----

#1 killnine  Icon User is offline

  • D.I.C Head

Reputation: 19
  • View blog
  • Posts: 161
  • Joined: 12-February 07

Determining if two unsorted List<T> contain the same elements

Posted 26 June 2009 - 11:37 AM

Hi,

I am writing an application where I have two objects that contain properties that are generic Lists (List<T>). I want to compare the two properties and make sure they contain the same elements (but not necessarily in the same order). For example:

List1:
item1
item2
item3


List2:
item2
item1
item3



This should result in them being considered "the same". But this can also happen

List1:
item1
item2
item2
item3

List2:
item2
item2
item3
item1



This should also be the same! Crazy, eh?

I know I could probably just brute-force it with a lot of foreach's but I was hoping there was a better way.

Is This A Good Question/Topic? 0
  • +

Replies To: Determining if two unsorted List<T> contain the same elements

#2 jacobjordan  Icon User is offline

  • class Me : Perfection
  • member icon

Reputation: 113
  • View blog
  • Posts: 1,499
  • Joined: 11-June 08

Re: Determining if two unsorted List<T> contain the same elements

Posted 26 June 2009 - 12:06 PM

You could easily accomplish this with one for loop.
        public bool AreSame(System.Collections.Generic.List<object> List1, System.Collections.Generic.List<object> List2)
        {
            // If they're not equal in size, then you know they're not equal
            if (List1.Count != List2.Count) { return false; }

            for (int i = 0; i < List1.Count; i++)
            {
                if (!List2.Contains(List1[i]) | !List1.Contains(List2[i]))
                {
                    return false;
                }
            }
            return true;
        }


It's pretty simple logic, so it shouldn't need much explanation.
Was This Post Helpful? 0
  • +
  • -

#3 killnine  Icon User is offline

  • D.I.C Head

Reputation: 19
  • View blog
  • Posts: 161
  • Joined: 12-February 07

Re: Determining if two unsorted List<T> contain the same elements

Posted 26 June 2009 - 12:14 PM

View Postjacobjordan, on 26 Jun, 2009 - 11:06 AM, said:

You could easily accomplish this with one for loop.
        public bool AreSame(System.Collections.Generic.List<object> List1, System.Collections.Generic.List<object> List2)
        {
            // If they're not equal in size, then you know they're not equal
            if (List1.Count != List2.Count) { return false; }

            for (int i = 0; i < List1.Count; i++)
            {
                if (!List2.Contains(List1[i]) | !List1.Contains(List2[i]))
                {
                    return false;
                }
            }
            return true;
        }


It's pretty simple logic, so it shouldn't need much explanation.



See, I thought the exact same thing. However, there is a case where that logic will fail, right? I mean, knowing count and that an object exists within both lists isn't quite enough. For example:

List 1:
Obj 1
Obj 2
Obj 2


List 2: 
Obj 1
Obj 2
Obj 1



They have the same count and will fulfill the Contains logic, yet aren't the same.
Was This Post Helpful? 0
  • +
  • -

#4 jacobjordan  Icon User is offline

  • class Me : Perfection
  • member icon

Reputation: 113
  • View blog
  • Posts: 1,499
  • Joined: 11-June 08

Re: Determining if two unsorted List<T> contain the same elements

Posted 26 June 2009 - 12:36 PM

Well, try this
        public bool AreSame(System.Collections.Generic.List<object> List1, System.Collections.Generic.List<object> List2)
        {
            // If they're not equal in size, then you know they're not equal
            if (List1.Count != List2.Count) { return false; }
            System.Collections.Generic.List<object> SearchedObjects = new List<object>();
            for (int i = 0; i < List1.Count; i++)
            {
                if (!SearchedObjects.Contains(List1[i]))
                {
                    if (Count(List1, List1[i]) != Count(List2, List1[i]))
                    {
                        return false;
                    }
                    else
                    {
                        SearchedObjects.Add(List1[i]);
                    }
                }

                if (!SearchedObjects.Contains(List2[i]))
                {
                    if (Count(List1, List2[i]) != Count(List2, List2[i]))
                    {
                        return false;
                    }
                    else
                    {
                        SearchedObjects.Add(List2[i]);
                    }
                }
            }
            return true;
        }

        public int Count(System.Collections.Generic.List<object> List, object CompareItem)
        {
            int count = 0;
            foreach (object Item in List)
            {
                if (Item == CompareItem)
                {
                    count++;
                }
            }
            return count;
        }


That uses two for loops, which i know you probably wouldn't have preferred, but using the SearchedObjects list to store the objects that have already been searched and checked really cuts back on the number of alliterations needed.
Was This Post Helpful? 0
  • +
  • -

#5 killnine  Icon User is offline

  • D.I.C Head

Reputation: 19
  • View blog
  • Posts: 161
  • Joined: 12-February 07

Re: Determining if two unsorted List<T> contain the same elements

Posted 26 June 2009 - 12:39 PM

EDIT: jacob, thanks so much. I will give both a try and see how they work out.


Ah ha. I figured out a solution.

There is no way any of you could know this, but each object in the list contains a key ID, lets just say List[i].Key. Therefore, I will use a predicate to find compare them:


//Pretend some list1 and list2 were populated
foreach(Object tempObj in List2)
{
	 List<int> listOfKeys = new List<int>();
	 foreach(Object tempObjKeySearch in List2)
	 {
		 //find each unique tempObjKeySearch.Key
	  }

	  foreach(int key in listOfKeys)
	  {
		  if(List1.FindAll(PredicateThatFindsAllByKey(key)).Count != List2.FindAll(PredicateThatFindsAllByKey(key)).Count)
		  {
			  return false; //not the same, return false
		   }
	  }
	  return true;
}



This is assuming I write a method called FindAll() that takes a Predicate that searches for all the elements that have the same key. I had to transpose this as not to release any IP from my company, so hopefully not much got lost in translation...

This post has been edited by killnine: 26 June 2009 - 12:39 PM

Was This Post Helpful? 0
  • +
  • -

#6 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 5776
  • View blog
  • Posts: 12,587
  • Joined: 16-October 07

Re: Determining if two unsorted List<T> contain the same elements

Posted 26 June 2009 - 01:06 PM

View Postkillnine, on 26 Jun, 2009 - 01:39 PM, said:

Ah ha. I figured out a solution.


Nice. I would prefer the count method, if you're going that way. Also, a dictionary should help here too.

public bool Equals(List<object> listA, List<object> listB) {
	if (listA.Count != listB.Count) { return false; }
	
	// first list and count
	Dictionary<object,int> dict = new Dictionary<object,int>();
	
	foreach(object item in listA) {
		dict[item] = dict.ContainsKey(item) ? dict[item] + 1 : 1;
	}
	
	foreach (KeyValuePair<object,int> pair in dict) {
		int bCount = listB.Count(delegate(object key) { return key==pair.Key; });
		if (pair.Value!=bCount) { return false; }
	}
	
	return true;
}


This post has been edited by baavgai: 26 June 2009 - 01:07 PM

Was This Post Helpful? 0
  • +
  • -

Page 1 of 1