Check if item exists in array before pushing to array

Question

I have this loop:

for (let i = 0; i < vertices.length; i++) {
    let ranVert1 = floor(random(1, vertices.length - 1)) + 1;
    let ranVert2 = floor(random(1, vertices.length - 1)) + 1;

    let found = lines.filter((line, index, array) => {
        console.log(`Line ${index}:`);
        console.log(line.v1);
    });
    if(found.length > 0){
        continue;
    }
    lines.push(new Line(ranVert1, ranVert2));
}

It loops through each vertex in a vertices array, and creates a line between any 2 vertices. But I want to remove duplicates.

So if we have vertices 0, 1, 2, 3, 4. Then it generates line [2, 4]. I don't want it to generate another line that is either [2, 4] or [4, 2].

What's the best way to do this? (Preferably without using a for loop)

Thanks in advance.

Edit:

A vertex looks like this:

{
   x: 300,
   y: 500
}

A line looks like this:

{
   v1: 5,
   v2: 6
}

Put this as an answer so i can accept it please @trincot – Bebet May 29 '21 at 14:32 — Bebet, May 29 '21 at 14:32

trincot · Accepted Answer · 2021-05-29T14:53:15.297

Create a matrix of zeroes, where rows and columns correspond to the indices of the first and second vertex. Put a 1 in that matrix when you have output the pair. If there is already a 1, don't output it.

I assume you also want to avoid pairs like [2, 2] -- creating a line to the same vertex.

So something like this:

let matrix = vertices.map(() => Array(vertices.length).fill(0));

for (let i = 0; i < vertices.length; i++) {
    let ranVert1 = floor(random(1, vertices.length - 1)) + 1;
    let ranVert2 = floor(random(1, vertices.length - 1)) + 1;

    let found = matrix[ranVert1][ranVert2] || ranVert1 == ranVert2;
    if (found) {
        continue;
    }
    matrix[ranVert1][ranVert2] = 1;
    matrix[ranVert2][ranVert1] = 1; // To avoid the other direction as well
    lines.push(new Line(ranVert1, ranVert2));
}

Alternatively, you can create an array with all possible pairs, shuffle that array, and then take a slice from that array.

Something like this:

let lines = vertices.flatMap((v1, i) => 
    vertices.slice(i+1).map(v2 => new Line(v1, v2))
);
shuffle(lines); // see link for implementation of shuffle
lines.splice(vertices.length); // keep only first few elements

Note: In your code you generate vertices.length lines, but you also write "...creates a line between any 2 vertices". It does not create a line between any 2 vertices, since there are more such lines possible than vertices.length: actually there are vertices.length*(vertices.length-1)/2 such lines possible. If you really want all of those, then definitely go for the second solution, as the first one may need some time to randomly generate the only one left when it reaches the end of the generation process. The shuffle algorithm does not have this problem, and you can then leave out the splice.

Check if item exists in array before pushing to array

1 Answers1