Answers.Body: <p>First, store the two parent chromosomes into a sorted dictionary (in terms of implementation, <code>std::map</code> in C++ might be a good option) where the key is the letter and the value is a pair of <code>int</code>s (the second gene element). When you populate the map, add all the letters from each chromosome as keys and take <code>0</code> (or a negative number) to indicate that a gene with the corresponding letter does <em>not</em> exist in one of the parents. </p>
  
  <p>Next, create a second map, this time with the number as a key. Iterate over the first map. If both parent chromosomes contain a gene with the same letter, the value field in the map would contain two positive numbers - pick one at random and insert the {number, letter} combination into the second map <em>only if the number doesn't exist as a key</em>. If the gene exists only in one parent, either pick the gene as is or choose to skip that gene altogether.</p>
  
  <p>This would guarantee that 1) your genomes contain a {letter, number} gene only once and 2) the genes in the offspring's chromosomes would be automatically sorted by letter. If you don't need the genes to be sorted but still need them to be unique, you can use an unordered map (a hash table).</p>
  
  <p>In your example, the map would look like this:</p>
  
  <pre><code>Mapped parent chromosomes
  {a: (1,2)}
  {b: (0,1)}
  {c: (2,4)}
  {d: (0,3)}
  {e: (3,0)}
  {g: (4,0)}
  
  Offspring chromosome (OC)
  {}
  </code></pre>
  
  <p>Where <code>0</code> indicates that the corresponding gene does not exist in that parent. Iterating over this table from top to bottom, you might end up doing the following:</p>
  
  <ol>
  <li>Key <code>a</code>: pick <code>1</code>; <code>1</code> is not a key in OC, so insert <code>{1,a}</code></li>
  <li>Key <code>b</code>: pick <code>1</code>; <code>1</code> is a key in OC, so skip letter <code>b</code></li>
  <li>Key <code>c</code>: pick <code>4</code>; <code>4</code> is not a key in OC, so insert <code>{4,c}</code></li>
  <li>Key <code>d</code>: choose to skip</li>
  <li>Key <code>e</code>: pick <code>3</code>; <code>3</code> is not a key in OC, so insert <code>{3,e}</code></li>
  <li>Key <code>g</code>: pick <code>4</code>; <code>4</code> is a key in OC, so skip letter <code>g</code></li>
  </ol>
  
  <p>Final offspring chromosome:</p>
  
  <pre><code>{a,1}{c,4}{e,3} 
  </code></pre>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-12-27T13:27:53.400Z
Answers.Text: Thanks for the reply I really appreciate it. However, the offspring you created is invalid because the number 4 exists twice in the offspring and that would be invalid in my solution.
Answers.UserDisplayName: Coder Guy
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-12-27T13:51:41.080Z
Answers.Text: I see - I have updated the answer to take into account this clarification.
Answers.UserDisplayName: cantordust
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-12-27T13:10:32.383Z
Answers.LastActivityDate: 2018-12-27T13:50:08.420Z
Answers.LastEditDate: 2018-12-27T13:50:08.420Z
Answers.UserDisplayName: cantordust
Body: <p>Each chromosome contains an array of genes, each gene contains a letter and a number, both letter and number can only exist once in each chromosome.</p>
  
  <pre><code>Parent A = {a,1}{c,2}{e,3}{g,4}
  Parent B = {a,2}{b,1}{c,4}{d,3}
  </code></pre>
  
  <p>What would be the best crossover operator to create a child that doesn't break the rule described above?</p>
  
Tags: <genetic-algorithms><crossover-operators>
Title: How to crossover chromosomes composed of genes that are tuples such that the elements of the tuples do not appear twice in the chromosome?
UserDisplayName: Coder Guy
ThreadText: # How to crossover chromosomes composed of genes that are tuples such that the elements of the tuples do not appear twice in the chromosome?
  
  (Asked by: username_0 on 2018-12-26)
  
  Each chromosome contains an array of genes, each gene contains a letter and a number, both letter and number can only exist once in each chromosome.
  Parent A = {a,1}{c,2}{e,3}{g,4}
  Parent B = {a,2}{b,1}{c,4}{d,3}
  
  What would be the best crossover operator to create a child that doesn't break the rule described above?
  
  **Tags:** genetic-algorithms, crossover-operators
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2018-12-27. Score: 1
  
  First, store the two parent chromosomes into a sorted dictionary (in terms of implementation, std::map in C++ might be a good option) where the key is the letter and the value is a pair of ints (the second gene element). When you populate the map, add all the letters from each chromosome as keys and take 0 (or a negative number) to indicate that a gene with the corresponding letter does not exist in one of the parents. 
  Next, create a second map, this time with the number as a key. Iterate over the first map. If both parent chromosomes contain a gene with the same letter, the value field in the map would contain two positive numbers - pick one at random and insert the {number, letter} combination into the second map only if the number doesn't exist as a key. If the gene exists only in one parent, either pick the gene as is or choose to skip that gene altogether.
  This would guarantee that 1) your genomes contain a {letter, number} gene only once and 2) the genes in the offspring's chromosomes would be automatically sorted by letter. If you don't need the genes to be sorted but still need them to be unique, you can use an unordered map (a hash table).
  In your example, the map would look like this:
  Mapped parent chromosomes
  {a: (1,2)}
  {b: (0,1)}
  {c: (2,4)}
  {d: (0,3)}
  {e: (3,0)}
  {g: (4,0)}
  
  Offspring chromosome (OC)
  {}
  
  Where 0 indicates that the corresponding gene does not exist in that parent. Iterating over this table from top to bottom, you might end up doing the following:
  
  Key a: pick 1; 1 is not a key in OC, so insert {1,a}
  Key b: pick 1; 1 is a key in OC, so skip letter b
  Key c: pick 4; 4 is not a key in OC, so insert {4,c}
  Key d: choose to skip
  Key e: pick 3; 3 is not a key in OC, so insert {3,e}
  Key g: pick 4; 4 is a key in OC, so skip letter g
  
  Final offspring chromosome:
  {a,1}{c,4}{e,3}
  
  > **Comments:**
  > **username_0**: Thanks for the reply I really appreciate it. However, the offspring you created is invalid because the number 4 exists twice in the offspring and that would be invalid in my solution.  
  > **username_1**: I see - I have updated the answer to take into account this clarification.  
  
  ---
  
  