Генерация случайных чисел без повторений

#cpp #алгоритм #случайные_числа

Сижу, ломаю голову - и все никак не получается. Нужно создать массив из случайных
чисел в диапозоне от 1 до 7 и чтобы там не было повторений. Я знаю, что есть много
вариантов решения, но я выбрал следующий: при генерации числа заносить его в массив,
а при генерации следующего пробегаться по массиву в поисках совпадения. Если найдено,
то генерировать заново. Написал код, вроде бы все легко, но в ответе все равно проскальзывают
повторения. Подскажите, где косяк?

#include "pch.h"
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include  

using namespace std;

int main()
{
setlocale(LC_ALL, "Russian");
SetConsoleCP(1251);
SetConsoleOutputCP(1251);

srand(time(0));

int a[7] = {0,0,0,0,0,0,0}; //создаю массив и заполняю нулями
int random; //переменная для случайных чисел

for (int i = 0; i < 7; i++) { //цикл создания случайных чисел
             random = 1 + rand() % 7; //создание случайного числа
             for (int j = 0; j < 7; j++) { //цикл проверки массива на совпадение
                 if (random == a[j]) { //условие совпадения
                     while (random == a[j]) { //цикл для создания нового случайного
числа, пока оно не будет повторяться
                         random = 1 + rand() % 7;
                     }
                 }
                 else {
                     continue; //если повтора нет, переходим к следующей итерации
                 }
            }
             a[i] = random; // присваивание рандомного числа элементу массива
        } 

for (int k = 0; k < 7; k++) { //вывод массива на экран
            cout << a[k];
        }

cout << "Для выхода из консоли нажмите любую клавишу";
    _getch();
    return 0;
}

    

Ответы

Ответ 1

Для такого малого количества просто возьмите массив {1,2,3,4,5,6,7} и случайным образом
его перетасуйте (например, с помощью shuffle). Будет быстрее и проще.

А ваша проблема в том, что, проверив число на равенство одному a[j] и откорректировав,
вы тут же об этом забываете при проверке на следующее значение j. Т.е. ваш цикл должен
выглядеть примерно как

for (int i = 0; i < 7; i++)
{
    for(;;)
    {
        bool good = true;
        random = 1 + rand() % 7;
        for (int j = 0; j < 7; j++)
        {
            if (random == a[j]) { good = false; break; }
        }
        if (good) break;
    }
    a[i] = random; // присваивание рандомного числа элементу массива
}


Ответ 2

Если размер вашего массива совпадает (или близок) к размеру домена, из которого производится
выборка, то ваш подход будет работать катастрофически неэффективно, даже если реализовать
его правильно. 

Для решения этой задачи есть простейший алгоритм Фишера-Йетса, который сразу за один
проход генерирует случайно перемешанную последовательность без необходимости каких-то
проверок

int main()
{
  int a[7] = { 0 };

  for (unsigned i = 0; i < 7; ++i)
  {
    unsigned j = rand() % (i + 1);
    a[i] = a[j];
    a[j] = i + 1;
  }

  for (int i : a)
    cout << i << " ";

  cout << endl;
}


Ответ 3

Так как std::unordered_map  хранит пары с уникальным ключом:

const int r = 7;
int a[r] = {0};
unordered_map m;
for (int i = 0; i < r; ++i)
    while (!(m.emplace(make_pair(1 + rand()%r, i))).second);
//вводим пару, пока попытка ввода не будет удачной
for (auto p : m)
    a[p.second] = p.first;


Так быстрее (границы случайных чисел могут быть любыми).

Но конкретно для вашего случая, когда элементы массива принимают значения по каким
то критериям(например от 1 по r), то можно просто:

for (int i = 0; i < r; ++i)
        a[i] = i + 1;
std::random_shuffle(a, a + r);