1

Тема: Вибрати випадковий елемент послідовності

Недавно на одному блозі знайшов цікавий алгоритм, вирішив спочатку описати задачкою, може комусь буде цікаво подумати, бо задача з тих які можуть питати на співбесіді у всякі Googl-ли й Фейсбуки.

Є послідовність довжиною від 0 до гугол (я не знаю скільки це але дофіга, на пам'ять не сподівайтесь). Вам послідовно передають її елементи. Задача - вивести випадковий елемент цієї послідовності, при чому так, що ймовірність кожного елемента бути вибраним була однакова (рівномірний розподіл).

2

Re: Вибрати випадковий елемент послідовності

А чим можна користуватись?

3

Re: Вибрати випадковий елемент послідовності

Теорією ймовірностей, матлогікою, дискреткою, та чим завгодно... Якщо щодо мови опису алгоритму - беріть будь-яку, хоч нормальні алгоритми Маркова, різниці немає...

4 Востаннє редагувалося HetmanNet (15.12.2012 02:13:07)

Re: Вибрати випадковий елемент послідовності

Такі задачки в компаніях як гугле часто завершуються досить неочікуваними результатами, наприклад ця завершиться тим, що немає повної випадковості, є псевдовипадкові події, тож висновок - лохів які спробують вирішити цю задачу до біса і жоден не скаже цього, відповідно роботи їм не очікувати.

5 Востаннє редагувалося bunyk (15.12.2012 14:39:10)

Re: Вибрати випадковий елемент послідовності

Нініні, все чесно. Можна вважати що функція random чесно кидає кубик, і повертає насправді випадкове дійсне число на проміжку [0, 1],

6 Востаннє редагувалося Torbins (15.12.2012 14:50:20)

Re: Вибрати випадковий елемент послідовності

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

7 Востаннє редагувалося bunyk (15.12.2012 14:51:03)

Re: Вибрати випадковий елемент послідовності

Torbins написав:

Якщо кількість елементів відома з самого початку, то користуємося будь-яким генератором випадкових чисел, отримуємо номер необхідного елемента, і починаємо чекати його прибуття.

Невідома, інакше задачка занадто проста.

Torbins написав:

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

Не можна в масив, у вас не вистачить пам'яті. Та й взагалі, так задачка занадто проста.

Хоча якщо ви будете брати не всі елементи, то хм, ви ніби на правильному шляху. Тепер залишилось уточнити як саме вибирати елементи в масив.

8 Востаннє редагувалося Torbins (15.12.2012 14:54:40)

Re: Вибрати випадковий елемент послідовності

Якщо пам'яті у нас зовсім мало, то можна утворити ієрархію з кількох внутрішніх масивів A, B, C... Коли масив A переповнюється, він віддає випадковий елемент масиву В, а сам очищується для нових елементів. Те саме робить масив В, і так далі.
Десять-п'тнадцять таких масивів, і гугол уже не видасться великим числом.
Обирати можна або через випадкові проміжки часу, або взагалі не обирати, а пхати у А все підряд.

9

Re: Вибрати випадковий елемент послідовності

Давайте думати по індукції. Для порожньої множини ми повертаємо None. Для одного елемента - точно цей елемент. Для двох елементів - 50/50 перший або другий. Для трьох ймовірність кожного - 1/3.

Давайте запам'ятаємо наш елемент в змінну х. Запишемо туди None. Коли ми отримуємо перший елемент, то з ймовірністю 1 замінюємо його на перший. Коли отримуємо другий - то з ймовірністю 0.5 замінюємо його на другий. Коли отримуємо третій - з ймовірністю 1/3 замінюємо на третій.

Мушу бігти, крок індукції розповім потім.

10

Re: Вибрати випадковий елемент послідовності

а може хтось в коді реалізувати власну функцію генерації випадкових чисел?

11

Re: Вибрати випадковий елемент послідовності

Мене вчили лінійний конгруентний метод генерації псевдовипадкових чисел, але це не стосується теми. :)

12

Re: Вибрати випадковий елемент послідовності

я не знаю що таке рівномірний розподіл і мене це в принципі не дуже турбує. спочатку подумав що це мається на увазі генерація випадкових чисел.

13

Re: Вибрати випадковий елемент послідовності

Patron написав:

а може хтось в коді реалізувати власну функцію генерації випадкових чисел?

А для чого майструвати велосипед? Все одно числа будуть псевдо-випадкові за природою.

14

Re: Вибрати випадковий елемент послідовності

bunyk написав:

Давайте запам'ятаємо наш елемент в змінну х. Запишемо туди None. Коли ми отримуємо перший елемент, то з ймовірністю 1 замінюємо його на перший. Коли отримуємо другий - то з ймовірністю 0.5 замінюємо його на другий. Коли отримуємо третій - з ймовірністю 1/3 замінюємо на третій.

Коли отримуємо n-тий - з ймовірністю 1/n замінюємо на n-тий...
Проблема в тому, n на практиці - обмежене. Нехай max(n) - максимальне число для типу n і нехай ми можемо генерувати рівномірно розподілене ціле число від 0 до max(n)-1.
При n=max(n) можна ввести нову змінну x2 і спочатку привласнити їй значення  max(n)+1-го елементу, потім з ймовірністю 1/2  max(n)+2-го і т.д.
Коли дійдемо до  2*max(n)-го елементу, привласнимо х з ймовірністю 1/2 значення x2, і привласнимо х2 значення 2*max(n)+1-го елементу...
Коли дійдемо до  n2*max(n)-го елементу, привласнимо х з ймовірністю 1/n2 значення x2 і т.д.
Таким чином, зможемо охопити max(n)^2 елементів.
Далі можна брати x3, привласнювати йому max(n)^2+1 значення...
Можна створити масив з x, x2, x3, ..., інший - з лічильниками n, n2, n3, ... Для гугола шести елеменів в масиві достатньо (якщо брати тип System.Int64 в .NET).
P.S. Оремо треба прописувати процедуру, коли отримуємо останнє число послідовності.
Тому, можливо, для коректних розрахунків замість max(n) краще взяти max(n)/2.

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

15

Re: Вибрати випадковий елемент послідовності

yooll написав:

Коли отримуємо n-тий - з ймовірністю 1/n замінюємо на n-тий...

Це все, супер. Я забув що хтось може захотіти ще реалізувати довгу арифметику. :)

Власне що я хотів почути: Нехай на n-тому кроці у нас є випадково вибраний з n-1 елементів елемент x. Якщо ми його замінюємо на n-тий з ймовірністю 1/n то залишаємо з ймовірністю P(A) = 1 - 1/n = (n-1)/n. Це з ймовірністю P(B) = 1 / (n-1) перший елемент. Так як ми його можемо й не залишити, то ймовірність того що це й далі перший елемент - P(A) * P(B) = (n-1) / n * 1 / (n-1) = 1/n. Крок індукції доведено.

16

Re: Вибрати випадковий елемент послідовності

Алгоритм корисний наприклад якщо ми хочемо вивести випадковий рядок файлу, і не хочемо читати ввесь файл щоб дізнатись скільки там рядків. Ну і в інших подібних ситуаціях.

17

Re: Вибрати випадковий елемент послідовності

bunyk читати весь файл нам усе одно доведеться. Інакше останній рядок файлу не матиме шансу бути виведеним на екран.

18

Re: Вибрати випадковий елемент послідовності

Читати, звичайно, доведеться, але один раз, а не два.

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