1 Тема від olehov

  • olehov
  • Новий користувач
  • Поза форумом
  • Дата реєстрації: 29.11.2019
  • Повідомлень: 6
    • Репутація: 0

Тема: Масив унікальних випадкових чисел

Як задати масив рандомними числами але щоб вонине повторювалися?

2 Відповідь від P.Y. Востаннє редагувалося P.Y. (26.03.2020 15:45:56)

  • P.Y.
  • P.Y.
  • Replace Team
  • Поза форумом
  • Дата реєстрації: 19.02.2013
  • Повідомлень: 7 623
    • Репутація: 4965

Re: Масив унікальних випадкових чисел

Заповнити масив випадково згенерованими числами.
Після чого порівняти кожне число масиву з усіма іншими. Якщо виявлено збіг, замінити одне з чисел новим випадково згенерованим.
Продовжувати, поки після повного проходження масиву не залишиться жодного збігу.

Можна зробити й більш оптимально: порівнювати кожен елемент масиву лише з тими елементами, що йдуть після нього (і в разі збігу замінювати новим значенням той елемент, що ближче до кінця масиву). (Незовсім так — див. нижче)

Подякували: olehov1

3 Відповідь від koala

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 15 602
    • Репутація: 13310

Re: Масив унікальних випадкових чисел

Якимось чином відстежувати, щоб вони не повторювалися (Козак Окобака).
Загалом залежить від того, які саме числа треба отримувати. Якщо масив більший за діапазон випадкових чисел і вони цілі, то за принципом Діріхле такі числа згенерувати, вочевидь, неможливо.

Подякували: olehov1

koala вебсайт

4 Відповідь від P.Y.

  • P.Y.
  • P.Y.
  • Replace Team
  • Поза форумом
  • Дата реєстрації: 19.02.2013
  • Повідомлень: 7 623
    • Репутація: 4965

Re: Масив унікальних випадкових чисел

А втім, ні: в другому «оптимізованому» варіанті може виявитись так, що згенероване нове значення дасть збіг з якимось із елементів, що йдуть перед тим, з яким його порівнювали — отже, згенерувавши випадкове число, його все одно доведеться порівнювати з усіма елементами від першого до того, з яким цей елемент перед цим дав збіг.

Подякували: olehov1

5 Відповідь від koala

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 15 602
    • Репутація: 13310

Re: Масив унікальних випадкових чисел

Мені не подобаються алгоритми, що покладаються на випадковість у складності.
Придумав алгоритм з O(n), але там числа будуть дещо невипадково розкидані. Кажу ж - питання в тому, наскільки числа мають бути випадкові. Якщо довжина інтервалу випадкових чисел (a;b) суттєво більша за їхню кількість n, то:

  1. генеруємо n+1 число від 0 додаванням випадкового числа від 1 до (b-a)/n до попереднього в проміжний масив t (0 в масив не записуємо);

  2. перші n чисел перетворюємо t[i] = t[i]*(b-a)/t[n]+a;

  3. тасуємо перші n чисел; найпростіше це зробити, витягаючи випадкове за номером число в масив-результат, а на його місце пересуваючи останнє.

А якщо різниця несуттєва, то створюємо масив з усіх можливих варіантів і виконуємо лише п. 3.

Подякували: plusxx, P.Y.2

koala вебсайт