-3
function randomKey(obj) {
    var ret;
    var c = 0;
    for (var key in obj)
        if (Math.random() < 1/++c)
           ret = key;
    return ret;
}

Can someone please explain how this code fairly picks a random key from the object?

deceze
  • 510,633
  • 85
  • 743
  • 889
John Anisere
  • 513
  • 1
  • 3
  • 13
  • We are probably passing a hash in randomKey function as obj, then we initialize two variables then a loop begins which will check whether a random num generated is smaller than 1/++c and then finally function returns the ret – Ankush Malik Sep 14 '17 at 13:11
  • never trust code that labels variables "ret" and "c" – jenson-button-event Sep 14 '17 at 13:14
  • @deceze You'd have a 1/20 chance of picking the 20th key (or any key) in a collection of 20 objects. – Bill the Lizard Sep 14 '17 at 13:17
  • @Bill Yes, I realise that, still wondering the same as James whether the way this is iterated won't favour earlier keys. Probably just our intuition betraying us. – deceze Sep 14 '17 at 13:19
  • @deceze Yes, it definitely looks off. I had to step through it to be sure, but all the probabilities add up, so it has a sort of leveling effect. – Bill the Lizard Sep 14 '17 at 13:20
  • actually yes I'm still inclined to think it's weighted - you only get the pick the first key once. Then there's keys.length-1 chances of picking another, even if the chances of doing so are "balanced" – James Thorpe Sep 14 '17 at 13:21
  • 1
    I'm inclined to post this on https://stats.stackexchange.com, but I'm scared and I won't understand the answers anyway. ;) – deceze Sep 14 '17 at 13:22
  • @deceze Yeah the thought had crossed my mind too :) – James Thorpe Sep 14 '17 at 13:23
  • @JamesThorpe But there's a 100% chance that you pick that first key the first time, and all the other probabilities never add up to 1, so there will always be a chance that you just leave your first pick alone. – Bill the Lizard Sep 14 '17 at 13:23
  • @BilltheLizard Right. I never liked probabilities... – James Thorpe Sep 14 '17 at 13:24

1 Answers1

5

Say you have three keys in obj. On the first iteration of the loop, 1/++c will be 1, so ret will always be set to the first key. In the second iteration, 1/++c will equal 0.5, so there's a 1/2 probability that the random number generated will be less than that, so a 50% chance that you'll change ret to the second key. On the third iteration 1/++c will be 0.333..., so there will be a 1/3 probability that ret will change to the third key.

For any size collection in obj, you should end up with an even distribution of keys.

Bill the Lizard
  • 398,270
  • 210
  • 566
  • 880
  • 1
    @JamesThorpe This code looks like it might have come from an obfuscation competition. – Bill the Lizard Sep 14 '17 at 13:19
  • Yeah, i agree it results in an even distribution. Strange way to do it though. I would just do a random int between 0 and Object.keys(obj).length -1 (assuming you only want own properties) – Nicholas Tower Sep 14 '17 at 13:19
  • @NicholasTower This might be someone's job security. ;) – Bill the Lizard Sep 14 '17 at 13:25
  • @Bill the Lizard what is the simplest and more efficient way to get random keys from an object? – John Anisere Sep 14 '17 at 13:34
  • @JohnAnisere The method Nicholas mentioned would be more straightforward than using a loop. There are several implementations on [Pick random property from a Javascript object](https://stackoverflow.com/q/2532218/1288), including the one you give in the question here. The second answer there is a simpler approach. – Bill the Lizard Sep 14 '17 at 13:47
  • @BilltheLizard what does this `[keys.length * Math.random() << 0]` do? I'm confused with use of the left shift bitwise operator – John Anisere Sep 14 '17 at 14:26
  • @JohnAnisere `keys.length * Math.random()` results in a float. Shifting 0 bits just converts it to an integer. JavaScript... ¯\\_(ツ)_/¯ – Bill the Lizard Sep 14 '17 at 14:53