Extract samples without replacement using TypeScript.

getSamplesWithoutReplacement.ts

/**
* Extract n samples from list without replacement in O(|list|)
* @param {Object[]} list - array containing elements
* @param {number} n - size of the extraction
* @returns {Object[]} new array contains extracted elements
*/
function getSamplesWithoutReplacement<T>(list: T[], n: number): T[] {
    if (n <= 0) return []
    
    list = [...list]
    if (n >= list.length) return list
    
    for (let k = 0; k < n; ++k) {
        const target = Math.floor(Math.random() * (list.length - k)) + k;
        [list[k], list[target]] = [list[target], list[k]]
    }
    list.length = n
    return list
}

The method of sample extraction without replacement is not trivial. One may implement like below, but it may run redundant retrial depend on what is selected. Theoretically, there is a chance of inifinite loop (although that probability is almost 0).

function getSamplesWithoutReplacement(list, n):
  result := []
  for k := 1, 2, ..., n
    do
      x := randomly select from list
    while x is in result
    add x to result
  return result

My implementation guarantees a single loop.

Note that possibilities of every elements being selected are same, regardless of order of selections.

Proof

Let m be the total number of elements.
Let x, y be arbitrary different elements in the list, and X, Y be the event of which each x, y is selected.

P(X) = 1 / m
P(Y | X) = 1 / (m - 1)
P(Y | X) = P(X ∩ Y) / P(X)
P(X ∩ Y) = P(Y | X) * P(X)
         = 1 / (m * (m - 1))        ... (1)

I want to show that P(Y) is only dependent on the size m.
Using law of total probability,

P(Y) = P(X ∩ Y) + P(X^c ∩ Y)        ... (2)

Similar to (1), P(X^c ∩ Y) can be shown as another conditional probability.

P(X^c ∩ Y) = P(X^c | Y) * P(Y)
           = P(Y) * (m - 2) / (m - 1)        ... (3)

By (1), (2), (3),

P(Y) = 1 / (m * (m - 1)) + P(Y) * (m - 2) / (m - 1)
P(Y) * (1 - (m - 2) / (m - 1)) = 1 / (m * (m - 1))

∴ P(Y) = 1 / m

Also you can use this function for permutating list. It's special case of n = list.length.

function permutateList<T>(list: T[]): T[] {
    list = [...list];

    for (let k = 0; k < list.length; ++k) {
        const target = Math.floor(Math.random() * (list.length - k)) + k;
        [list[k], list[target]] = [list[target], list[k]];
    }
    return list;
}