How to eliminate duplicates

Question

4.00/5 (2 votes)

See more:

I was writing my thesis and got to a problem that i can't solve. I am writing about Genetic Algorithms with steady-state selection.
The problem is that after some iteration duplicates shows up; my question is how to remove these duplicates.
How can i compare some specific elements from an object? I tried with the function Equals() but didn't figured out how to set her up.

Example: i want that this repeats until the new object isn't the same as existing objects in class population:

public void permutationRecombination(Chromosome parent1, Chromosome parent2, Chromosome child1, Chromosome child2)
  {
  int cLen = parent1.genes.Length;


  do
     {
     int recomPoint = ga.rng.Next(cLen - 1);
     int poc1 = 0, poc2 = 0;
     bool nadjen;

     // first part (copying genes)
     for (int i = 0; i <= recomPoint; i++)
        {
        child1.genes[i] = parent1.genes[i].Clone();
        child2.genes[i] = parent2.genes[i].Clone();
        }
     // second (inserting missing genes from other parent)
     for (int i = recomPoint + 1; i < cLen; i++)
        {
        // first child
        nadjen = false;
        for (int j = poc1; j < cLen; j++)  // search for other genes in other parent
           {
           for (int k = recomPoint + 1; k < cLen; k++)
              {
              if (parent2.genes[j].ToInteger() == parent1.genes[k].ToInteger()) //trazi
                 {
                 child1.genes[i] = parent2.genes[j].Clone();
                 poc1 = j + 1;
                 nadjen = true;
                 }
              }
           if (nadjen) break;
           }
       //second child;
       nadjen = false;
       for (int j = poc2; j < cLen; j++)  //search for missing genes in each other
          {
          for (int k = recomPoint + 1; k < cLen; k++)
             {
             if (parent1.genes[j].ToInteger() == parent2.genes[k].ToInteger()) //trazi
                {
                child2.genes[i] = parent1.genes[j].Clone();
                poc2 = j + 1;
                nadjen = true;
                }
             }
          if (nadjen) break;
          }
       }
    if (child1.genes==parent1.genes) MessageBox.Show("postoje jednaki");
    } while (child1.Equals(parent1) || child2.Equals(parent2) || child1.Equals(parent2) || child2.Equals(parent1));
  }

[edit]Code formatting changed from flat to indented - OriginalGriff[/edit]

Posted 20-Mar-11 5:41am

supermito

Updated 20-Mar-11 6:36am

v3

Add a Solution

Comments

Sergey Alexandrovich Kryukov 20-Mar-11 15:47pm

OP commented:

@SAKryukov and AlbinAbel--- do i need that cannt i just make it easelly
i.e. this picture shows the structure of my classes... and the genes are value int so if these values are the same for two chromosomes; it should generate again new childs:
i meen if child.genes = { 123456789} and parent parent.genes={12345678}---> they have the same order of numbers so i need to avoid this

http://img843.imageshack.us/i/capturezo.png/[^]

thank you guys for sharing your time by helping me!!!

Sergey Alexandrovich Kryukov 20-Mar-11 15:49pm

What we offered is already very easy; anything else will not help.
Will you please formally accept our Answers? (Press "Accept" buttons...)
If not, ask a follow-up Question (please, don't post as an Answer!)
--SA

4 solutions

Solution 4

i added this code to my class Chromosome and it works some kind, not perfect but it works :)

C#

public override bool Equals(object obj)
{
      //Check for null and compare run-time types.
      if (obj == null || GetType() != obj.GetType()) return false;
      Chromosome c = (Chromosome)obj;
      for(int i = 0; i < c.genes.Length; i++)
      {
         // if any pair of corresponding genes are unequal, the chromosomes are unequal
         if (this.genes[i].ToInteger() != c.genes[i].ToInteger()) return false;
      }
      return true; // all corresponding genes equal
   }
}
public override int GetHashCode()
{
    int hash = genes[0].ToInteger();
    for(int i = 1; i < this.genes.Length; i++)
    {
         hash ^= this.genes[i].ToInteger();
    }
    return hash;
}

Posted 20-Mar-11 14:44pm

supermito

Comments

Sergey Alexandrovich Kryukov 20-Mar-11 23:25pm

What is the problem? What's "not perfect"?
--SA

Sergey Alexandrovich Kryukov 20-Mar-11 23:32pm

I found a big potential bug!

When you override identity, you generally should not use "==" and "!=", for referential comparison, because you can change the meaning of operators (which is even recommended). So, in first place, please fix it.
You have one "==" and two "!=". Replace them both with "object.ReferenceEquals". For example
"object.ReferenceEquals(null, obj)", "!object.ReferenceEquals(GetType() != obj.GetType())".

--SA

supermito 21-Mar-11 10:24am

but i did not override "==" and "!=" (didnt changed the meaning of these operators).
i have sended the code to my teacher, hope he accepts it the way it is... but will also try your advices!!

Sergey Alexandrovich Kryukov 21-Mar-11 23:15pm

I understand. Using "==" and "!=" making your code *potentially* unstable, as I say.
When and if you decide to do so, will you remember. This is like bad variable names. Today it works, but tomorrow you will need to understand what they do. Same thing here. You should understand that your the artifact of your code is not executable file which "just works". You need code source code which you can support, etc. Using ReferenceEquals is a good rule of thumb when you override methods of System.Object.
--SA

Sergey Alexandrovich Kryukov 20-Mar-11 23:44pm

Also, "Chromosome c = (Chromosome)obj;" is redundant. Combine type check and type case with one dynamic cast "as". Anyway, look at my improvement of this code and questions in my variant.
Why would not you finally formally accept my Answers?
How put forward the idea of this container, after all? :-)
--SA

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Albin Abel · Accepted Answer · 2011-03-20T07:32:00

Let us assume your gene sequence are an array of int (not a binary string) then equals or == mean that both operands has same genes then.

C#

public class Parent
{
    public int[] genes = new int[5];
    public static bool operator ==(Parent p, Child c)
    {
        int geneCount = p.genes.Count();
        for (int i = 0; i <= geneCount; i++)
        {
            if (p.genes[i] != c.genes[i])
            {
                return false;
            }
        }
        return true;
    }
    public static bool operator !=(Parent p, Child c)
    {
        if (p == c == true)
        {
            return false;
        }
        else { return true; }
    }

    public override bool Equals(object obj)
    {
        if (obj.GetType() == typeof(Child))
        {
            Child c = (Child)obj;
            return this == c;
        }
        else
        {
            return false;
        }
    }
}
public class Child
{
    public int[] genes = new int[5];
    public static bool operator ==(Child c, Parent p)
    {
        int geneCount = c.genes.Count();
        for (int i = 0; i <= geneCount; i++)
        {
            if (c.genes[i] != p.genes[i])
            {
                return false;
            }
        }
        return true;
    }
    public static bool operator !=( Child c,Parent p)
    {
        if (c == p == true)
        {
            return false;
        }
        else { return true; }
    }
    public override bool Equals(object obj)
    {
        if (obj.GetType() == typeof(Parent))
        {
            Parent p = (Parent)obj;
            return this == p;
        }
        else
        {
            return false;
        }
    }
}

This can be used like

C#

Parent p = new Parent();
p.genes[0] = 1;
p.genes[1] = 2;
p.genes[2] = 3;
p.genes[3] = 4;
p.genes[4] = 5;

Child c = new Child();
c.genes[0] = 1;
c.genes[1] = 2;
c.genes[2] = 3;
c.genes[3] = 4;
c.genes[4] = 6;
MessageBox.Show((p == c).ToString());
MessageBox.Show((p != c).ToString());
MessageBox.Show((p.Equals(c)).ToString());

Sergey Alexandrovich Kryukov · Accepted Answer · 2011-03-20T07:43:00

Unfortunately, you did not provide a definition of Chromosome and did not explain what's is duplicated. I thing, this is a chromosome.

You need to keep all instances of the Chromosome in the container which guarantee uniqueness. It can be Dictionary (where a set of dictionary keys is unique)or HashSet. It the only feature you need is uniqueness, use System.Collections.Generic.HashSet<Chromosome>, see http://msdn.microsoft.com/en-us/library/bb359438.aspx[^].

To make you Chromosome class (I hope this is class, not structure, otherwise you should have used passing parameters by ref in the code you show) to be able to became an element of collection, you should make sure that its uniqueness is defined by its comparison operation. For this purpose, override Equals(object) and GetHashCode. Is's also good to define "==" and "!=" operators accordingly. Hash Code is the key to dictionaries and hash sets. Is does not have to be unique (it is not always possible) but "characteristic enough". On simple way of creating an acceptable hash function for a class or structure is this: calculate hash functions for all components and XOR them together.

[EDIT] Please see my other Answer in response to OP's new piece of code — corrections and notes.

—SA

Sergey Alexandrovich Kryukov · Accepted Answer · 2011-03-20T17:52:00

This is my improvement of the code posted by OP:

C#

public override bool Equals(object obj)
{
      if (object.ReferenceEquals(obj, null) return false;
      Chromosome chromosome = obj as Chromosome;
      if (object.ReferenceEquals(chromosome, null)) return false;
      for(int index = 0; index < chromosome.genes.Length; index++)
      {
         // why genes[index] is not integer type?
         // even if it is not, why converting ToInteger?
         // direct comparison could work
         // != is valid here
         if (this.genes[index].ToInteger() != chromosome.genes[index].ToInteger()) return false;
      }
      return true; // all corresponding genes equal
   }
}

I used object.ReferenceEquals which is always better if you modify identity rules, and improved naming (one-character or non-semantic names are always bad). Also, look at my questions in code and see if you really choose correct presentation for genes.

—SA

How to eliminate duplicates

4 solutions

Solution 1

Solution 2

Solution 5

Solution 4

Add your solution here

Preview 0