How can I iterate over all unique pairs of entries in an object?

Question

I currently have an array data structure that I iterate over like this, calling foo on each unique pair of elements.

for(var i = 0; i < arr.length; i++) {
    for(var j = i + 1; j < arr.length; j++) {
        foo(arr[i], arr[j]);
    }
}

However, I've realized that I'd rather use an object instead of an array, since I can then add and remove elements by name very easily.

However, I can't see an obvious way to iterate over such an object. The closest I can get is:

for(i in obj) {
    for(j in obj) {
        foo(obj[i], obj[j]);
    }
}

Obviously, this will do each pair twice, and even produce a pair of identical elements. Is there an easy way to iterate over an object in the same way as I do in the array in my first code sample?

Update:

Performance testing the solutions on jsperf.

If you want to iterate objects inside objects I guess the best option is to create a recursive function, there are some other example here in SO. — elclanrs, May 08 '12 at 19:40
How about adding an `if (i < j)` condition in the inner loop? It's not the fastest solution, but I believe it could work. — Simon Forsberg, May 08 '12 at 19:43
@elclanrs: I'm not iterating recursively - I'm iterating over every possible combination of entries in an object/array. Eg, in the array `[1, 2, 3]`, I want to call `foo(1, 2)`, `foo(1, 3)`, and `foo(2, 3)`. — Eric, May 08 '12 at 19:43
@SimonAndréForsberg; Yeah, that'd work! I just came up with that myself, but if you post it as an answer and I'll accept it. — Eric, May 08 '12 at 19:46
@SimonAndréForsberg that won't work in each case because the keys of an object don't have to be sorted and they don't have to be of the same data type as well. — Johannes Egger, May 08 '12 at 19:46
@Jasd: They don't need to be sorted for that to work. All it does make sure that `foo(obj[a], obj[b])` and `foo(obj[b], obj[a])` are not both called (for constant `a`, `b`), since one must violate the condition `i < j`. And object keys are _always_ strings, so the comparison never fails. — Eric, May 08 '12 at 19:47
@Eric you are right. But strings (object keys) are compared differently to integers (array keys) (e.g. "10" < "2" and 10 < 2 leads to a different result). — Johannes Egger, May 08 '12 at 19:50
@Jasd: Nope, array keys are strings as well. Try doing a `for ... in` loop with an array. The keys you get are not integers, but strings. — Eric, May 08 '12 at 20:00
No, what I'm trying to say is that @SimonAndréForsberg 's solution could behave differently. Imagine you have the keys "10" and "2". Iterating over an object with those keys would execute `foo("10","2")`. If you have an array with the keys from 0 to 10 `foo(10,2)` wouldn't be called but `foo(2,10)`. Depending on the implementation of foo this could be something different. — Johannes Egger, May 08 '12 at 20:02
Ah, ok. I should have pointed out that `foo` is symmetrical, and does not care which order its arguments come in. Hence the requirement for unique pairs, not all pairs. — Eric, May 08 '12 at 20:03
Ohh stupid me. I didn't know that array keys are also stored as strings. That makes my whole argument invalid. — Johannes Egger, May 08 '12 at 20:34

Simon Forsberg · Accepted Answer · 2012-05-08T20:50:16.063

5

My solution that was at first written as a comment:

Add an if (i < j) condition in the inner loop. It might not be the best solution, but it would work as long as the foo function does the same thing for foo(2, 10) and foo(10, 2):

for(i in obj) {
    for(j in obj) {
        if (i < j) {
            foo(obj[i], obj[j]);
        }
    }
}

edited May 08 '12 at 20:50

answered May 08 '12 at 20:29

Simon Forsberg

13,086
10
64
108

Are you sure it's not the fastest? Does a string comparison cost more or less than a property lookup? – Eric May 08 '12 at 20:31
Honestly I'm not sure at all if it is the fastest solution or not :) Edited that part. It might be both the easiest, most neat and fastest solution (in your case at least). – Simon Forsberg May 08 '12 at 20:35
tbh, speed is not a great issue, since `foo` is orders of magnitude more expensive that the string comparison. Nevertheless, doing some performance tests at http://jsperf.com/adjacent-pair-iteration – Eric May 08 '12 at 20:40
This was more performant than looping all results. 2x faster in fact and it's cognitively easier to understand than some of the other responses. – Oscar Godson Oct 28 '18 at 06:02

score 2 · Answer 2 · answered May 08 '12 at 19:44

Assuming I understand your question... maybe check to see if the value has already been visited by the outer loop?

var visited = {}
for(i in obj) {
    visited[i] = true;
    for(j in obj) {
        if(j in visited){ continue; }
        foo(obj[i], obj[j]);
    }
}

score 2 · Answer 3 · answered May 08 '12 at 19:50

2

Use Object.keys() to get the list of keys out as an array:

keys = Object.keys();
for(i=0;i<keys.length;i++) {
    for(j=i+1;j<keys.length;j++) {
        foo(obj[keys[i]], obj[keys[j]]);
    }
}

answered May 08 '12 at 19:50

Gort the Robot

2,329
16
21

2

Probably better to store `Object.keys()` in a variable rather than evaluating it `n + 3*n*n` times – Eric May 08 '12 at 19:51
Why was my edit refused? Your code doesn't work like you put it. I have fixed it. – d_inevitable May 11 '12 at 14:08

score 2 · Answer 4 · edited May 23 '17 at 12:21

2

Maybe You can try unset used objects:

for(i in obj) {
    var a = obj[i];
    delete obj[i];
    for(j in obj) {
        foo(a, obj[j]);
    }
}

http://jsfiddle.net/bXcvb/

If you need to original obj in tact see: How do I correctly clone a JavaScript object?

edited May 23 '17 at 12:21

Community

1
1

answered May 08 '12 at 19:55

d_inevitable

4,381
2
29
48

1

**+1** for an interesting approach, but I'd rather not pull my object apart every time I iterate over it! – Eric May 08 '12 at 19:56
I am not sure if you can have performance and the neatness. It's either or... But thanks for the +1 :) – d_inevitable May 08 '12 at 19:58
1

Yeah, but when you need to clone it, then its not so nice anymore: http://jsperf.com/adjacent-pair-iteration/2 – d_inevitable May 08 '12 at 21:34
Still, this could be good to know whenever you need to do a fast iteration over an object that's going to be deleted anyways... just gotta wait for that moment. I'm surprised to see that when copying the speed is about the same as my solution. – Simon Forsberg May 08 '12 at 22:15
1

I think its the key assignment on objects (`obj[key] = ...`) that's so brutally expensive. If there was a deep memcopy in js, this could be improved a lot. – d_inevitable May 08 '12 at 22:18

score 1 · Answer 5 · answered May 08 '12 at 19:47

1

You can push the object keys into an array:

var obj_keys = [];
for (i in obj) {
  obj_keys.push(i);
}

for(i = 0; i < obj_keys.length; ++i) {
    for(j = i + 1; j < obj_keys.length; ++j) {
        foo(obj[obj_keys[i]], obj[obj_keys[j]]);
    }
}

answered May 08 '12 at 19:47

Sam Dufel

17,560
3
48
51

How can I iterate over all unique pairs of entries in an object?

Update:

5 Answers5

Linked