samedi 14 décembre 2019

Finding random numbers in a range that have different minimal distances between each other

I'm writing a simulation program "Core War". I need to generate random positions for x amount of programs in a given range of memory. They will always fit in the memory.

The programs have some amount of lines. I need to randomly place them in the memory, so that they don't overlap with each other. I'm looking for the starting line position:

Example - for the inputs:

memorySize = 50;
programCount = 3;
programLengths = [3, 7, 4]

The function would have to output 3 positions for the 3 program lengths, which:

  • are from 0 to 49
  • cannot in any way overlap with another program, for example if the output would be [0, 2, 20], the first and the second program would overlap, because the length of the first program is 3 lines, which means that the last line would be on index 2. The second program would overlap the first.

I tried making a function that does that for 2 programs, but it was too complicated and I just set the first one to zero and randomly picked the other one:

void setStartingPositions()
{
    posFirst = 0;

    std::mt19937 mt_rand(time(0));
    posSecond = mt_rand() % (MEMORY_SIZE - secondProgram.size - firstProgram.size);
    posSecond += first.size;
};

These are the available variables:

std::vector<Program> programs; // program[0].size() returns the length of the first program
size_t memorySize;

If possible, a mersenne twister answer would be best.

Thank you in advance.




Aucun commentaire:

Enregistrer un commentaire