動態排除隨機生成序列中的一些數字

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); 
}