Last active
November 20, 2018 22:48
-
-
Save cdwfs/810e1339fa02042b341def6ccfc012d7 to your computer and use it in GitHub Desktop.
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)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 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; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment