动态排除随机生成序列中的一些数字

Question

我想生成一个范围内的随机数字序列，例如100 to 200。

过了一段时间，根据一些事件，我想在同一范围（100到200）之间产生一个新的序列，但这次我想排除一些数字。例如，我不想要[150,165,170]。

下一次，这些排除的数字可能包括或不包括在序列中。

一个可行的方法可以是数字像这样的数组：

int rndm[] {100,101,102,103,...}; 

，并使用数组的索引每次生成一个随机数：

random(rndm[0-99]); 

但我需要尽可能少地使用指令/数据结构以实现性能。

我使用C代码，我使用random()或randomSeed(seed)，我想知道处理这个问题最有效的方法是，在数据结构方面应该用于速度和内存。

Answer 1

此解决方案在排除函数为二次的情况下在生命周期中排除的次数不多的情况下非常有效。

存在一个名为的结构RandomArray，其中包含指向大小为N的数组的指针.N是序列的所需大小。时间和空间复杂度对于创建函数是线性的O（N）。

当一个事件发生，如果期望排除一堆值应当调用函数excludeValue，具有O（N）时间复杂度和空间的1

复杂性，功能排除值（注意最后的s）应该被调用。在这种情况下，复杂度为O（N×K），空间复杂度为1. K是应排除的值的数量。

#include <stdio.h> 
#include <stdlib.h> 

struct RandomArray { 
    int *pData; 
    size_t dataLen; 
    int excludedIdx; 
}; 
struct RandomArray *excludeValue(struct RandomArray *pAr, int val) { 
    size_t i; 
    for (i = 0; i < pAr->excludedIdx; ++i) { 
    if (pAr->pData[i] == val) { 
     pAr->excludedIdx--; 
     int tmp = pAr->pData[i]; 
     pAr->pData[i] = pAr->pData[pAr->excludedIdx]; 
     pAr->pData[pAr->excludedIdx] = tmp; 
     // Do test again the position 
     --i; 
    } 
    } return pAr; 
} 

struct RandomArray *excludeValues(struct RandomArray *pAr, int *pVals, size_t len) { 
    size_t i; 
    for (i = 0; i < len; ++i) 
    excludeValue(pAr, pVals[i]); 
} 

struct RandomArray *destroyRandomArray(struct RandomArray *pAr) { 
    if (pAr) { 
    if (pAr->pData) 
     free(pAr->pData); 
    pAr->dataLen = 0; 
    } 
    return pAr; 
} 

struct RandomArray *createRandomArray(
struct RandomArray *pAr, 
size_t dataLen, 
int lowLimit, int highLimit) { 
    int i; 
    int range = (highLimit - lowLimit); 
    pAr->pData = (int*)malloc(sizeof(int) * dataLen); 
    pAr->dataLen = dataLen; 
    srand(time(NULL)); 
    for (i = 0; i < dataLen; ++i) { 
    pAr->pData[i] = rand() % (range + 1) + lowLimit; 
    } 
    // Clear excluded indexs 
    pAr->excludedIdx = pAr->dataLen; return pAr; 
} 

void printRandomArray(struct RandomArray *pAr) { 
    size_t i; 
    printf("Random Array (len = %d): ", pAr->dataLen); 
    for (i =0; i < pAr->dataLen; ++i) { 
    printf(" %d", pAr->pData[i]); 
    } 
    printf("\n"); 
} 

void printValidRandomArray(struct RandomArray *pAr) { 
    size_t i; 
    printf("Valid Random Array (len = %d): ", pAr->excludedIdx); 
    for (i =0; i < pAr->excludedIdx; ++i) { 
    printf(" %d", pAr->pData[i]); 
    } 
    printf("\n"); 
} 

void printExcludedRandomArray(struct RandomArray *pAr) { 
    size_t i; 
    printf("Excluded Random Array (len = %d): ", pAr->dataLen - pAr->excludedIdx); 
    for (i = pAr->excludedIdx; i < pAr->dataLen; ++i) { 
    printf(" %d", pAr->pData[i]); 
    } 
    printf("\n"); 
} 

void printAllRandomArray(struct RandomArray *pAr) { 
    printRandomArray(pAr); 
    printValidRandomArray(pAr); 
    printExcludedRandomArray(pAr); 
} 

int main() { 
    int lowLimit = 100; 
    int highLimit = 105; 
    int arrayLen = 10; 
    struct RandomArray myAr; 
    createRandomArray(&myAr, arrayLen, lowLimit, highLimit); 
    printAllRandomArray(&myAr); 
    printf("\n"); 
    excludeValue(&myAr, 100); 
    printAllRandomArray(&myAr); 
    printf("\n"); 
    excludeValue(&myAr, 101); 
    printAllRandomArray(&myAr); 
    printf("\n"); 
    excludeValue(&myAr, 102); 
    printAllRandomArray(&myAr); 
    printf("\n"); 
    excludeValue(&myAr, 103); 
    printAllRandomArray(&myAr); 
    printf("\n"); 
    excludeValue(&myAr, 104); 
    printAllRandomArray(&myAr); 
    printf("\n"); 
    excludeValue(&myAr, 105); 
    printAllRandomArray(&myAr); 
    destroyRandomArray(&myAr); 
    createRandomArray(&myAr, arrayLen, lowLimit, highLimit); 
    printf("\n\n\n"); 
    printAllRandomArray(&myAr); 
    printf("\n"); 
    int vals[] = { 102, 105, 104 }; 
    excludeValues(&myAr, vals, sizeof(vals)/sizeof(vals[0])); 
    printAllRandomArray(&myAr); 
    destroyRandomArray(&myAr); 
} 

Answer 2

这是问here on the Arduino forum，但我也在这里看到它。我的回答是在Arduino的C++风格发布后...

当然，性能随着排除的数字集相对于用来创建“新序列”的数字集增加而变化。

void setup() { 
    Serial.begin(115200); 
    randomSeed(analogRead(A0)); 
} 
void loop() { 
    // create an arbitray sized array to be filled with unique values to exclude from desired array 
    const int arraySize = 5; 
    int exclusions[arraySize]; 
    for (int i = 0; i < arraySize; i++) { 
    // fill the array with unique values... 
    int val; 
    do { 
     val = random(100, 200); 
    } while([&]() { 
     for (auto j : exclusions) { 
     if (val == j) { 
      return true; 
     } 
     } 
     return false; 
    }()); 
    exclusions[i] = val; 
    } 
    Serial.print(F("Exclusion Array: ")); 
    for (int i = 0; i < arraySize; i++) { 
    Serial.print(exclusions[i]); 
    if (i < arraySize - 1) 
    Serial.print(F(", ")); 
    } 
    Serial.println(); 
    // create a new array of arbitrary length of unique random numbers in >>>the same<<< range as above (but not necessary) 
    Serial.print(F("Starting...\n")); 
    uint32_t start = millis(); 
    const int listSize = 32; 
    int list[listSize]; 
    for (int i = 0; i < listSize; i++) { 
    // fill the array with unique values that will exclude exclusions[] 
    int val; 
    do { 
     val = random(100, 200); 
    } while([&]() { 
     for (auto j : list) { 
     if (val == j) { 
      return true; 
     } 
     for (auto k : exclusions) { 
      if (val == k) { 
      return true; 
      } 
     } 
     } 
     return false; 
    }()); 
    list[i] = val; 
    } 
    uint32_t end = millis(); 
    Serial.println(end - start); 
    // OPTIONAL -> lets sort the final arry to make spotting the duplicates easier: 
    for (int i = 0; i < listSize; i++) { 
    for (int j = i + 1; j < listSize; j++) { 
     if (list[j] < list[i]) { 
     int temp = list[i]; 
     list[i] = list[j]; 
     list[j] = temp; 
     } 
    } 
    } 

    // output the final array 
    Serial.print(F("Final Array: ")); 
    for (int i = 0; i < listSize; i++) { 
    Serial.print(list[i]); 
    if (i < listSize - 1) 
    Serial.print(F(", ")); 
    } 
    Serial.print(F("\n\n\n")); 
    delay(1000); 
}