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

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。

如果需要排除一堆值，则应调用函数 excludeValues（注意末尾的 s）。在这种情况下，复杂度为 O（N x 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("nnn");
  printAllRandomArray(&myAr);
  printf("n");
  int vals[] = { 102, 105, 104  };
  excludeValues(&myAr, vals, sizeof(vals) / sizeof(vals[0]));
  printAllRandomArray(&myAr);
  destroyRandomArray(&myAr);
}

Answer 2

这是在Arduino论坛上问到的，但我在这里也看到了。我的答案是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("nnn"));
  delay(1000);
}