3

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
Heretic Monkey
  • 11,687
  • 7
  • 53
  • 122
sspboyd
  • 369
  • 4
  • 15
  • 1
    are the arrays data, or indices and is `parent1Subset` an array of indices? what is the question about? – Nina Scholz Oct 26 '18 at 13:31
  • The arrays are indices and yes, parent1Subset is an array of indices. I'm trying out different algorithms to find solutions to the travelling salesperson problem. – sspboyd Oct 26 '18 at 13:33
  • @sspbody i think you are mutating `parent1Subset` in your loop. arrays are passed by reference in javascript. – r3wt Oct 26 '18 at 13:34
  • @r3wt, thanks, I'll try it by making a new array and update the code in the question. – sspboyd Oct 26 '18 at 13:36
  • 1
    @r3wt Unfortunately no different. I'm hoping I didn't misunderstand your suggestion. – sspboyd Oct 26 '18 at 13:41
  • Thank you so much. Both answer from @NinaScholz and jared-smith work really well. I've learned a lot trying to understand how they work. I'll be curious to find out which approach is faster since I'm going to be running this function upwards of 10M times. – sspboyd Oct 26 '18 at 15:26
  • @sspboyd if you're doing it that many times it may be faster to use hashmaps rather than arrays (testing for inclusion is just the constant cost of the hashing function rather than traversing an array over and over), and depending on what your performance requirements are you may want to think about a different language than JavaScript. – Jared Smith Oct 26 '18 at 16:51
  • 1
    @JaredSmith I completely agree that JavaScript is not the best language for doing this quickly. I am using JavaScript because it will run in the browser. This code is going to be used to demonstrate different ways of trying to solve the the Travelling Salesperson problem. I'll look at trying to use Map or Set as a way of doing this. Thanks again for the help. – sspboyd Oct 26 '18 at 17:01

2 Answers2

3

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(' '));
Nina Scholz
  • 376,160
  • 25
  • 347
  • 392
2

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]
Jared Smith
  • 19,721
  • 5
  • 45
  • 83
  • What is the purpose of the "..." in the following line? childArr.splice(startIndex, 0, ...parent1Subset); – sspboyd Oct 26 '18 at 17:19
  • @sspboyd it's the spread operator: `sum(...[1,2,3]) === sum(1, 2, 3) === 6`. In other words, turns an array into positional elements. You can also construct arrays with it `[...[1, 2], ...[3, 4]]` expands to `[1,2,3,4]`. – Jared Smith Oct 26 '18 at 17:47