Pick N distinct random numbers in the range 0..M-1, in C

distinct_randoms.c

/*
 * Any copyright is dedicated to the Public Domain.
 * https://creativecommons.org/publicdomain/zero/1.0/
 */

/*
 * Picks N distinct random numbers in the range {0..M-1}
 * Specify N as first command-line argument and M as second argument.
 *
 * Interestingly, the complexity of this program scales with respect to M and
 * not N.
 */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>


int main(int argc, char const *argv[]) {
    // check arguments
    if (argc < 3) {
        fprintf(
            stderr,
            "Wrong number of arguments given, expected 2, got: %d\n",
            argc - 1
        );
        return -1;
    }
    // try and interpret arguments
    unsigned long n = strtoul(argv[1], NULL, 0);
    unsigned long m = strtoul(argv[2], NULL, 0);
    int return_code = 0;
    if (n == 0) {
        fprintf(stderr, "Invalid argument '%s' for n\n", argv[1]);
        return_code = -1;
    }
    if (m == 0) {
        fprintf(stderr, "Invalid argument '%s' for m\n", argv[2]);
        return_code = -1;
    }
    // one final sanity check
    if (return_code == 0 && m < n) {
        fprintf(
            stderr,
            "Can't pick generate fewer numbers than there are choices!\n"
        );
        return_code = -1;
    }
    if (return_code != 0) {
        return return_code;
    }
    // NOTE: all error-handling is now out of the way
    // seed the mediocre random number generator with the time
    srand((unsigned int)time(NULL));
    printf("Generating %lu random integers in the range {0..%lu-1}:\n", n, m);
    // track number that have been chosen to verify
    size_t chosen = 0;
    // show the start of the 'array'
    printf("[");
    // iterate up to M, with the appropriate chance of choosing with respect to n
    for (size_t i = 0; i < m; i++) {
        /*
         * the probability of displaying each number starts at N/M, but changes
         * depending on how many left we need to pick and how many we have left
         * to pick from --it is this property which gaurantees we will pick
         * exactly the right number of integers.
         */
        long double chance = (long double)(n - chosen) / (m - i);
        long double coin_flip = (long double)rand() / RAND_MAX;
        if (coin_flip <= chance) {
            // this number has been chosen!
            printf("%lu,", i);
            chosen++;
        }
        // quit early if we've already chosen all the numbers we need
        if (chosen == m) {
            break;
        }
    }
    // show the end of the 'array'
    printf("]\n");
    // show number that were chosen
    printf("Chosen: %zu\n", chosen);
    return 0;
}