Skip to content

Instantly share code, notes, and snippets.

@Phryxia
Last active January 17, 2024 07:28
Show Gist options
  • Save Phryxia/bff4ccecde26d303e48e9cf55339c676 to your computer and use it in GitHub Desktop.
Save Phryxia/bff4ccecde26d303e48e9cf55339c676 to your computer and use it in GitHub Desktop.
Extract samples without replacement using TypeScript.
/**
* 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
}
@Phryxia
Copy link
Author

Phryxia commented Mar 27, 2022

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

@Phryxia
Copy link
Author

Phryxia commented Jul 15, 2023

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;
}

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment