Trying to "crossover" two arrays using subset of first array and maintaining order of second array where possible

user_610406 0
Viewed 367

I am trying to generate a new child array from two parent arrays (crossover) using the following process.

parentArr1 = [0,1,2,3,4,5,6,7,8,9]
parentArr2 = [9,8,7,6,5,4,3,2,1,0]
parent1Subset = [2,3,4,5]
childArr   = [9,8,2,3,4,5,7,6,1,0]

The crossover rules I'm defining are:

  1. Extract a contiguous subset from parentArr1 and insert it into a new childArr at the same position it was extracted from.
  2. Fill the remaining positions in the childArr with elements from parentArr2 and maintain the order of elements in parentArr2 around the subset.
  3. There should be no duplicates.

Here's another example:

parentArr1 = [0,1,2,3,4,5,6,7,8,9]
parentArr2 = [9,8,7,6,5,4,3,2,1,0]
parent1Subset = [7,8,9]
childArr   = [6,5,4,3,2,1,0,7,8,9]

I've had numerous failed attempts to do this. Here's the attempt that came the closest.

const parentArr1 = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
const parentArr2 = [9, 8, 7, 6, 5, 4, 3, 2, 1, 0];
let parent1Subset = [2, 3, 4, 5];
let childArr = crossOver(parentArr1, parentArr2, parent1Subset);
// Expected ouput: 9, 8, 2, 3, 4, 5, 7, 6, 1, 0

function crossOver(pArr1, pArr2, pArr1Subset) {
    let _childArr = pArr1Subset.slice(); // suggestion from @r3wt
    for (let i = 0; i < pArr1.length; i++) {
        for (let j = 0; j < (pArr1.length - _childArr.length); j++) {
            if (!_childArr.includes(pArr2[i])) {
                _childArr.splice(i, 0, pArr2[i]);
            }
        }
    }
    return _childArr;
}
console.log("childArr: " + childArr);
// childArr: 9, 8, 7, 6, 2, 3, 4, 5, 1, 0
crossover genetic-algorithm arrays javascript
2 Answers

You could use another indexer for array 2 and check if the actual value is in the crossover array.

function crossover(p1, p2, sub) {
    var j = 0;
    return p1.map(i => {
        if (sub.includes(i)) {
            return i;
        }
        while (sub.includes(p2[j])) ++j;
        return p2[j++];
    });
}

console.log(crossover([0, 1, 2, 3, 4, 5, 6, 7, 8, 9], [9, 8, 7, 6, 5, 4, 3, 2, 1, 0], [2, 3, 4, 5]).join(' '));
console.log(crossover([0, 1, 2, 3, 4, 5, 6, 7, 8, 9], [9, 8, 7, 6, 5, 4, 3, 2, 1, 0], [7, 8, 9]).join(' '));

user_14476750

Hopefully this should be easy enough to follow:

    const parentArr1 = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
    const parentArr2 = [9, 8, 7, 6, 5, 4, 3, 2, 1, 0];
    let parent1Subset = [2, 3, 4, 5];
    
    // First get the start index
    const startIndex = parentArr1.indexOf(parent1Subset[0]);
    
    // Get the start of the childArr
    const childArr = parentArr2.filter(n => parent1Subset.indexOf(n) < 0);
    
    // Splice in the subset
    childArr.splice(startIndex, 0, ...parent1Subset);
    
    console.log(childArr); // [9, 8, 2, 3, 4, 5, 7, 6, 1, 0]

user_37572320
Related