Generate a permutation of 1..P values from a set of N (N>=P) using O(N) space, but with strict O(1) initialization and O(1) cost per selected element (not amortized)

permute.cpp

// g++ -std=c++11 -o permute permute.cpp
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

const int kElemCount = 1024*1024;
const int kOutElemCount = kElemCount;
static_assert(kOutElemCount <= kElemCount, "can't output more than input");
static_assert(kElemCount >= 0, "no negative counts");
static_assert(kOutElemCount >= 0, "no negative count");

static int randRange(int minR, int maxPlusOneR) {
  int rangeSize = maxPlusOneR - minR;
  return minR + (lrand48() % rangeSize);
}

static int getArrVal(int i, int iOut, int arr[], int remap[]) {
  int arrVal = arr[i];
  if (arrVal >= 0 && arrVal < iOut && arr[arrVal] == i) {
    // This element has been remapped.
    return remap[arrVal];
  } else {
    // This element has not been remapped; arr[i] is implicitly i.
    return i;
  }
}

int main(int argc, char *argv[]) {
  int *arr = new int[kElemCount];
  int *remap = new int [kOutElemCount];
  int *out = new int[kOutElemCount];

  unsigned int seed = (unsigned int)time(nullptr);
  printf("seed = 0x%08X\n", seed);
  srand48(seed);

  // Initialize all arrays to random values. This is specifically the step this algorithm is
  // trying to avoid, but it's useful for testing purposes (otherwise, arrays may be auto-filled
  // with zeroes in debug mode).
#if 1
  for(int i=0; i<kElemCount; ++i) {
    arr[i] = lrand48();
  }
  for(int i=0; i<kOutElemCount; ++i) {
    remap[i] = lrand48();
    out[i] = lrand48();
  }
#endif

  for(int iOut=0; iOut<kOutElemCount; ++iOut) {
    // Select an element from arr to output
    int iArr = randRange(iOut, kElemCount);

    // Figure out which value arr[iArr] corresponds to.
    // This will be the output element for this iteration.
    int outputVal = getArrVal(iArr, iOut, arr, remap);

    // Figure out what value arr[iOut] corresponds to.
    // It will be remapped to arr[iArr].
    int remapVal = getArrVal(iOut, iOut, arr, remap);

    arr[iOut] = iArr;
    arr[iArr] = iOut;
    remap[iOut] = remapVal;
    out[iOut] = outputVal;
  }

  // TEST: verify uniqueness
  int *found = new int[kElemCount];
  memset(found, 0xFF, kElemCount*sizeof(int));
  for(int iOut=0; iOut<kOutElemCount; ++iOut) {
    int val = out[iOut];
    if (val < 0 || val >= kElemCount) {
      fprintf(stderr, "out[%d] = %d (out of range!)\n", iOut, val);
    }
    if (found[val] >= 0) {
      int iPrev = found[val];
      assert(iPrev >= 0 && iPrev < kOutElemCount);
      assert(out[iPrev] == val);
      fprintf(stderr, "out[%d] = %d (already found at out[%d]\n",
              iOut, val, iPrev);
    }
    found[val] = iOut;
  }
  delete [] found;

  // Print the output array
#if 0
  for(int iOut=0; iOut<kOutElemCount; ++iOut) {
    printf("%d ", out[iOut]);
  }
  printf("\n");
#endif

  delete [] arr;
  delete [] remap;
  delete [] out;
}