I iterate a loop within another loop, based on the same array, what's the best way to ignore duplicates?

Question

I want to save all combinations of an array. So for [a, b, c] I want to save [ab, ac, ba, bc, ca, cb]

I currently use this method:

for (coordinate in coordinates){
    for (coordinate2 in coordinates){
        if (coordinate != coordinate2){
            newposts.push([fbposts[fbpost].id, coordinates[coordinate], coordinates[coordinate2]]);
        }
    }
}

but it generates a bunch of duplicates. What's the smoothest way to solve this?

If `coordinates` is an array, don't use `for in`. – Inkbug Jul 15 '12 at 11:35 — Inkbug, Jul 15 '12 at 11:35

score 1 · Answer 1 · answered Jul 15 '12 at 11:33

1

Add a check before adding to your new array either by custom function or perhaps

array.indexOf(...)

Custom function similar to how jQuery does it:

function inArray(needle, haystack) {
    var length = haystack.length;
    for(var i = 0; i < length; i++) {
        if(haystack[i] == needle) return true;
    }
    return false;
}

So as you are building your new array of permutations/combinations (been 13+ years since my last stats class), perform a quick check and don't add if true, otherwise add. I believe if you perform an array merge it'll do similar so same performance.

answered Jul 15 '12 at 11:33

Mike S.

4,806
1
33
35

This link may be useful for you too: http://www.tutorialspoint.com/javascript/array_indexof.htm – Mike S. Jul 15 '12 at 11:33
if you have jquery use $.inArray(value, array) – indiPy Jul 15 '12 at 11:36

gion_13 · Accepted Answer · 2012-07-15T11:48:39.830

You could use a modified bubble sort algorithm:

var result = [],
arr = 'abc'.split('');

// begin the bubble sort loop
for(var i=0,l=arr.length;i<l-1;i++)
    for(var j=i+1;j<l;j++)
        {
            result.push(arr[i]+arr[j]);
            result.push(arr[j]+arr[i]);
        }
console.log(result); //["ab", "ba", "ac", "ca", "bc", "cb"]

By looping over the array in this way, you do not even need to check if the result is a duplicate, because it doesn't generate any. Btw, don't use the for..in synthax for looping over arrays because it may have unexpected results.

score 1 · Answer 3 · edited May 23 '17 at 11:48

You could take advantage of the fact that you can define a property only once and have something like this:

$(function() {
    var arr = ["a","b","c"];
    var permutations ={};
    $.each(arr, function(index1, val1) 
    {
        $.each(arr, function(index2, val2) 
        {
            permutations[val1+val2] = 0;
        });      

    });
    for(var prop in permutations)
    {
        //in prop you will have your elements: aa,ab...

    }        

});

permutations would play the role of a dictionary in this case

The logic of generating the combinations is sub optimal as the run time is n square - see this questions for algorithms of generating combinations of k elements out of an n elements array

I iterate a loop within another loop, based on the same array, what's the best way to ignore duplicates?

3 Answers3