How to loop through all possible pairs of JSON object keys exactly once?

Question

Say that I have a data structure of n elements and a function check(element1, element2) which performs some kind of checkup on two elements. I need to check exactly all possible pairs of elements. Using combinatorics it is easy to deduce that we need to perform exactly 'n choose 2' binomial coefficient iterations ( n*(n-1)/2 iterations)

So if my data structure is an array, the following nested loops would work:

for(let i = 0; i < elements.length; i++) {
    for(let j = i + 1; j < elements.length; j++) {
        check(elements[i], elements[j]);
    }
}

This way we check the first element with all the others, the second element with elements 3 to n (since we already checked it with the first one), the third with elements 4 to n and so on and so forth. However if 'elements' was a JSON where the key to each element is not an integer, how can we achieve this effect? Obviously we can ensure that we perform all checkups with the following code:

for(var key1 in elements) {
    for(var key2 in elements) {
        if(key1 != key2) {
            check(elements[key1], elements[key2]);
        }
    }
}

However obviously we are doing a lot of checkups more than once resulting in n^2 iterations.

What method can I use to achieve the same result as in the example with the array?

If it's not a string it's _not_ [JSON](http://json.org). [What is the difference between JSON and Object Literal Notation?](https://stackoverflow.com/questions/2904131/what-is-the-difference-between-json-and-object-literal-notation) — Andreas, Sep 03 '19 at 12:17
shouldn't `check(elements[key1], elements[key1]);` be `check(elements[key1], elements[key2]);` (note the `key2`) — Nick Parsons, Sep 03 '19 at 12:20

score 1 · Answer 1 · answered Sep 03 '19 at 12:21

1

If you put all the keys you're going to be looping into an array using Object.keys() then you can use your standard for loop to "skip" over previously seen keys like so:

const keys = Object.keys(elements);
for(let i = 0; i < keys.length; i++) {
  const key1 = keys[i]; 
  for(let j = i + 1; j < keys.length; j++) {
    const key2 = keys[j];
    check(elements[key1], elements[key2]);
  }
}

answered Sep 03 '19 at 12:21

Nick Parsons

45,728
6
46
64

I did consider such a solution, however I as am not familiar at all with low-level javascript it makes me wonder: exactly how much more efficient is this approach? Especially when working with a very large number of elements, how much more feasible is it to allocate a whole new array of the same length compared to iterating roughly twice as much? – user10433783 Sep 03 '19 at 12:25
@user10433783 its a question of memory effiency vs computational effiency. afaik, allocating a whole new array should be less efficient, but I can't tell for sure. – Gibor Sep 03 '19 at 12:28
1

@user10433783 in terms of computing the keys, that's going to take roughly `O(n)` where `n` is the number of keys in your elements object. This is only done once and outside of the loops, and so with large sets of data ur computational time complexity will still be O(n^2). However, overall, I would say it would save time when looking at large pieces of data, as your inner loop doesn't need to run `n` times each time (especially near the end of the loop when it may have to run 1 or twice only compared to `n` times). If ur concerned about space efficiencies, then your original approach is better – Nick Parsons Sep 03 '19 at 12:33

score 0 · Answer 2 · edited Sep 03 '19 at 12:26

0

Perhaps you could get the list of keys in an array:

let elements = { a: 1, b: 2, c: 3 };
let keys = Object.keys(elements).sort(); // Sorts the keys array alphabetically, and thus simulating the numbers example and be sure you're not repeating "lower" order key after passing it
for(let i = 0; i < keys.length; i++) {
    for(let j = i + 1; j < keys.length; j++) {
        // check(elements[keys[i]], elements[keys[j]]);
        console.log(elements[keys[i]], elements[keys[j]])
    }
}

output:

1 2
1 3
2 3

edited Sep 03 '19 at 12:26

Gibor

1,695
6
20

answered Sep 03 '19 at 12:20

Matt

364
4
10

1

In your example, the "keys" are sorted alphabetically, which is the same as integers are sorted from lowest to highest so you can be sure you're not hitting the same key twice. But in most cases they wouldn't be sorted. what you CAN do, is simply sort the keys before iterating over the arrays :) I'll edit you answer to reflect that/ – Gibor Sep 03 '19 at 12:23

How to loop through all possible pairs of JSON object keys exactly once?

2 Answers2