mardi 12 janvier 2016

Pick m integers randomly from an array of size n in JS

Problem (from Cracking the Coding Interview): Write a method to randomly generate a set of m integers from an array of size n. Each element must have equal probability of being chosen.

I'm implementing my answer in JS. For the recursive function, the code sometimes returns undefined as one of the elements in the array.

My JS Code

var pickMRecursively = function(A, m, i) {
    if (i === undefined) return pickMRecursively(A, m, A.length);
    if (i+1 === m) return A.slice(0, m);

    if (i + m > m) {
        var subset = pickMRecursively(A, m, i-1);
        var k = rand(0, i);
        if (k < m) subset[k] = A[i];

        return subset;
    }

    return null;
};

Given Java Solution

int[] pickMRecursively(int[] original, int m,int i) {
    if (i +1==m){// Basecase
     /* return first m elements of original */
    } elseif(i+m>m){
        int[] subset = pickMRecursively(original, m, i - 1); 
        int k = random value between 0 and i, inclusive
        if(k<m){
            subset[k] = original[i]j
        }
        return subset;
    }
    return null;
}




Aucun commentaire:

Enregistrer un commentaire