Заполнить массив случайными, не повторяющимися числами

Здравствуйте!
Подскажите, пожалуйста, как заполнить массив случайными, не повторяющимися числами?

Я делаю так:
1. Для i=1..N : a[i] = i;
2. Для i=1..N : a[i] обмен с a[random(N)].

Я бы только сделал так:
2. Для i=1..N-1 : a[i] обмен с a[i + 1 + random(N - i)].

Сообщение отредактировано: Profi - 27.01.22, 17:08

Увы, но так нельзя, Profi!
Ибо:
а) на первое место никогда не будет поставлен элемент №1 - потеря равномерности/независимости (частное высказывание);
б) (общее) на первых местах чаще будут элементы с большими номерами - потеря равномерности/независимости.

Цитата Славян @ 27.01.22, 18:00

Увы, но так нельзя, Profi!
Ибо:
а) на первое место никогда не будет поставлен элемент №1 - потеря равномерности/независимости (частное высказывание);
б) (общее) на первых местах чаще будут элементы с большими номерами - потеря равномерности/независимости.

a) А это ли не цель?
б) Неа. Конечно очень мало вероятна, но может быть ситуация когда последний элемент встанет на первое место, а остальные просто сдвинуться на шаг вперед.
Если интересно, почитай про Knuth shuffle.

Цитата Profi @ 28.01.22, 10:22

a) А это ли не цель?

Непонятен вопрос. Весьма размыт. Но вариант когда на первом месте никогда не будет элемента №1 внушает сомнение в случайности.

Цитата Славян @ 28.01.22, 14:05

Цитата Profi @ 28.01.22, 10:22

a) А это ли не цель?

Непонятен вопрос. Весьма размыт. Но вариант когда на первом месте никогда не будет элемента №1 внушает сомнение в случайности.

Ну, в целом согласен.
С другой стороны, есть вероятность (хоть и опять же минимальная), что Random будет каждый раз выдавать значение i и в результате будет обычный массив с элементами по индексу.

Сбацал маленький тест (пардон, что на Си, но не суть, думается):

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
 
#define n 1000
 
int main(int,char**)
{
    //std::cout << "Hello World!\n";
    int *a = new int[n];
    double itog[2]={0,0};
    for( int r=0; r<1000; r++)
    {
      srand(r);
      for( int i=0; i<n; i++) a[i] = i;
      for( int i=0; i<n; i++) std::swap( a[i], a[rand()%n]); // Славян
      //for( int i=0; i<n-1; i++) std::swap( a[i], a[i+1+(rand()%(n-1-i))]); // Profi
      long long l1 = 0, l2 = 0;
      for( int i=0; i<n/2; i++) l1 += a[i], l2 += a[i+n/2];
      printf("1) %g\t2)%g\n", l1*0.002, l2*0.002);
      itog[0] += l1*0.002, itog[1] += l2*0.002;
    }
    printf("A) %g\tB)%g\n", itog[0]*0.001, itog[1]*0.001);
    return 0;
}

Вывод:

Славян: A) 484.941 B) 514.059
Profi:  A) 498.919 B) 500.081

Ничего не понимаю , но метод Profi однозначно лучше! Надо думать...

Хотелось бы уточнить условие, оно противоречиво - случайные числа на то и случайны, что могут и повториться, "случайными, не повторяющимися" - в некотором роде противоречие.
Не указан диапазон значений чисел, их тип.
Известен ли заранее размер массива?

Просто, возможны варианты, например, если заранее известен размер массива N, и это степень двойки, а "случайные" числа - целые от 0 до N-1, то возможен совсем простой и эффективный вариант:
1. Генерируем всего одно случайное число C в пределах от 0 до N-1.
2. Заполняем массив числами i Xor C, где i - индекс в массиве.

По классике это делается через запись цифр от 0 до N-1 по очереди, в случайное свободное поле, где случайное число является смещением от последнего заполненного.

Ну что-то наподобие вот такого

program MakeRandArray;
 
{$APPTYPE CONSOLE}
 
{$R *.res}
 
function MakeArray(ACount: Integer): TArray<Integer>;
var
  I, CurPos, RandOffset: Integer;
begin
  // инициализация
  SetLength(Result, ACount);
  for I := 0 to ACount - 1 do
    Result[I] := -1;
 
  CurPos := -1;
 
  // бежим по массиву пока есть не заполненые элементы
  while ACount > 0 do
  begin
 
    // генерируем случайное смещение
    RandOffset := Random(ACount) + 1;
 
    // сдвигаемся вправо от текущей позиции на RandOffset НЕЗАПОЛННЕНЫХ элементов массива
    while RandOffset > 0 do
    begin
      Inc(CurPos);
      if CurPos = Length(Result) then
        CurPos := 0;  // контролируем выход за диапазон
      if Result[CurPos] < 0 then
        Dec(RandOffset);
    end;
 
    // заполняем выбранную позицию
    Result[CurPos] := ACount - 1;
    Dec(ACount);
  end;
end;
 
procedure PrintArray(Value: TArray<Integer>);
var
  I: Integer;
begin
  Write(Value[0]);
  for I := 1 to Length(Value) - 1 do
    Write(', ', Value[I]);
  Writeln;
end;
 
var
  AArray: TArray<Integer>;
begin
  Randomize;
  AArray := MakeArray(10);
  PrintArray(AArray);
  Readln;
end.

Добавлено 06.02.22, 08:05
Ну а саму генерацию массива можно немного модифицировать используя усилитель рандома через сложение для генерации гарантированно уникального числа

function MakeArray(ACount: Integer): TArray<Integer>;
const
  MaxRandStep = 30;
var
  I, CurPos, RandOffset, RandValue: Integer;
begin
  // инициализация
  RandValue := Random(MaxRandStep);
  SetLength(Result, ACount);
  for I := 0 to ACount - 1 do
    Result[I] := -1;
 
  CurPos := -1;
 
  // бежим по массиву пока есть не заполненые элементы
  while ACount > 0 do
  begin
 
    // генерируем случайное смещение
    RandOffset := Random(ACount) + 1;
 
    // сдвигаемся вправо от текущей позиции на RandOffset НЕЗАПОЛННЕНЫХ элементов массива
    while RandOffset > 0 do
    begin
      Inc(CurPos);
      if CurPos = Length(Result) then
        CurPos := 0;  // контролируем выход за диапазон
      if Result[CurPos] < 0 then
        Dec(RandOffset);
    end;
 
    // генерируем гарантированно случайное число
    Inc(RandValue, Random(MaxRandStep) + 1);
 
    // заполняем выбранную позицию
    Result[CurPos] := RandValue;
    Dec(ACount);
  end;
end;

Цитата Rouse_ @ 06.02.22, 07:56

По классике это делается через запись цифр от 0 до N-1 по очереди, в случайное свободное поле, где случайное число является смещением от последнего заполненного.

То, что я написал, на порядок производительнее, и даёт тот же результат.

Цитата Mikle @ 06.02.22, 08:46

То, что я написал, на порядок производительнее, и даёт тот же результат.

С таким же успехом можно было бы заполнить массив Arr[I] := I
Это не случайные числа, это возрастающие последовательности от опорного
Допустим на рандоме 100 это будет ряд 100, 101, 102, 103 etc...
Ну а с учетом что диапазон рандома указан в пределах 0..N-1, то при рандомном нуле будет вообще красиво

Ну мой вариант это решение из Кнута насколько я помню, классика ж говорю, только там помоему не сдвиг был а просто выбор случайного в диапазон (0..количество не заполненных) было
Конечно это не O(N) но рандом нормальный выйдет

Цитата Rouse_ @ 06.02.22, 12:35

это будет ряд 100, 101, 102, 103 etc...

а "etc..." будет "96, 97, 98, 99, 108, 109..."
Естественно, не очень то рэндом получается.
Я же написал: "Хотелось бы уточнить условие".
А мой пример был не совсем удачной демонстрацией, что такую задачу можно выполнить за O(N).
Если подумать, как задачу "заполнить массив, каждый раз подставляя случайное по порядку из оставшихся неиспользованными чисел" выполнить за O(N), то получится:
N чисел в случайном порядке можно расставить N! способами (это не нужно пояснять?). Тогда генерируем одно случайное число от 0 до N!-1 - оно будет однозначно идентифицировать порядок расстановки всех чисел. Осталось найти способ из числа восстановить эту последовательность - вот это будет красивое решение задачи. Правда, для небольших последовательностей - факториал быстро растёт.
И, да, существует вероятность выпадения нуля, но эта вероятность будет равна вероятности выпадения последовательно "0, 1, 2,.. N-1" при "классическом" решении.

Добавлено 07.02.22, 06:54

Цитата Rouse_ @ 07.02.22, 06:52

Конечно это не O(N) но рандом нормальный выйдет

По качеству - да, всё в порядке.
Я там выше написал с ошибкой, и, почему-то, не получалось отредактировать своё сообщение. Я удалил и написал новое.

Цитата Rouse_ @ 06.02.22, 12:35

Ну а с учетом что диапазон рандома указан в пределах 0..N-1

Где он указан?

Цитата DDim1000 @ 24.01.22, 07:29

Подскажите, пожалуйста, как заполнить массив случайными, не повторяющимися числами?

Вы решаете не ту задачу как по мне.

Сообщение отредактировано: cppasm - 07.02.22, 11:35