/*
 * Choose M distinct numbers out of a range of N of them.
 * Partial Fisher-Yates shuffle random number selection algorithm due
 * to Nick Johnson, but he used a hash:
 * <http://stackoverflow.com/questions/6947612/generating-m-distinct-random-numbers-in-the-range-0-n-1/6978109#6978109>
 * Set representation is from the folklore; a good introduction is Russ Cox’s:
 * <http://research.swtch.com/2008/03/using-uninitialized-memory-for-fun-and.html>
 *
 * On my machine, this takes about 13-15 μs per integer chosen from
 * among the largest sets it can handle:
 * kragen@inexorable:~/devel/inexorable-misc$ time ./choosemofn 100000 245000000 > tmp.out
 * real 0m1.464s
 * but only 0.7 μs each choosing from a smaller set:
 * time ./choosemofn 100000 100000 > tmp.out
 * real 0m0.070s
 * 
 */

#define _BSD_SOURCE
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef int bool;

/* Error-checking malloc wrapper. */
void *xmalloc(size_t s) 
{
     void *rv = malloc(s);
     if (!rv) abort();
     return rv;
}

/* Set representation with constant-time initialization. */
struct intset {
     int n;                        /* current number of elements */
     /* sparse[i] < n && dense[sparse[i]] == i iff i is in the set. */
     int *sparse;
     int *dense;                  
};

void init_intset(struct intset *set, int maxsiz)
{
     set->n = 0;
     set->sparse = xmalloc(maxsiz * sizeof(set->sparse[0]));
     set->dense = xmalloc(maxsiz * sizeof(set->dense[0]));
}

void add_to_intset(struct intset *set, int i)
{
     set->sparse[i] = set->n;
     set->dense[set->n] = i;
     set->n++;
}

bool is_in_intset(struct intset *set, int i)
{
     int j = set->sparse[i];
     return j < set->n && set->dense[j] == i;
}

/* Array initially containing all elements equal to their indices,
 * initialized in constant time. */
struct mutable_iota {
     struct intset set;
     int *val;
};

void init_mutable_iota(struct mutable_iota *iota, int maxsiz)
{
     init_intset(&iota->set, maxsiz);
     iota->val = xmalloc(maxsiz * sizeof(*iota->val));
}

void set_mutable_iota(struct mutable_iota *iota, int index, int value)
{
     add_to_intset(&iota->set, index);
     iota->val[index] = value;
}

int get_mutable_iota(struct mutable_iota *iota, int index)
{
     if (is_in_intset(&iota->set, index)) {
          return iota->val[index];
     } else {
          return index;
     }
}

void choose_m_of_n(int m, int n, void (*yield)(int)) 
{
     struct mutable_iota iota;
     int i;
          
     if (m > n) {
          abort();
     }

     init_mutable_iota(&iota, n);

     for (i = 0; i < m; i++) {
          int j = i + random() % (n - i);
          yield(get_mutable_iota(&iota, j));
          set_mutable_iota(&iota, j, get_mutable_iota(&iota, i));
     }
}

void usage(char *argv0) 
{
     fprintf(stderr, "%s: usage: %s m n, where m and n are numbers and m < n\n",
             argv0, argv0);
     exit(1);
}

void putint(int i) 
{
     printf("%d ", i);
}

int main(int argc, char **argv) 
{
     if (argc != 3) {
          usage(argv[0]);
     }

     srandom(time(NULL));
     choose_m_of_n(atoi(argv[1]), atoi(argv[2]), putint);
     printf("\n");

     return 0;
}