Здравствуйте, frogkiller, Вы писали:
F>Здравствуйте, andrey.desman, Вы писали:
AD>>Вот такую задачку получил недавно на собеседовании: AD>>Есть неинициализированный массив из 100 чисел. Дана функция rand(n), которая генерирует случайное число в диапазоне [0, n].
AD>>Заполнить массив числами [0, 99] в случайном порядке так, чтобы числа не повторялись.
AD>>Как это можно сделать?
F>Посмотри, как работает типичная реализация std::random_shuffle. И мы точно знаем, что на i-м месте будет стоять число i, поэтому перемешивание можно совместить с инициализацией. Получится как-то так:
F>
for (int i = 1; i < n - 1; ++i ) {
F> int j = rand(i);
F> a[i] = a[j];
F> a[j] = i;
F>}
Дело в том, что необязательно на i-ом месте будет стоять число i после свопов. Поэтому не настолько просто получается.
F>ЗЫ. твоё решение с 50-ти индексами, кстати, не будет обладать свойством равномерности распределения
Здравствуйте, andrey.desman, Вы писали:
AD>Здравствуйте, _DAle_, Вы писали:
F>>>
for (int i = 1; i < n - 1; ++i ) {
F>>> int j = rand(i);
F>>> a[i] = a[j];
F>>> a[j] = i;
F>>>}
_DA>>Дело в том, что необязательно на i-ом месте будет стоять число i после свопов. Поэтому не настолько просто получается.
AD>rand(i) генерирует число от 0 до i, так что будет.
Да, я одной особенности в коде не заметил ). Интересно, а при такой реализации равномерное распределение будет?
Здравствуйте, _DAle_, Вы писали:
_DA>Здравствуйте, andrey.desman, Вы писали:
AD>>Здравствуйте, _DAle_, Вы писали:
F>>>>
for (int i = 1; i < n - 1; ++i ) {
F>>>> int j = rand(i);
F>>>> a[i] = a[j];
F>>>> a[j] = i;
F>>>>}
_DA>>>Дело в том, что необязательно на i-ом месте будет стоять число i после свопов. Поэтому не настолько просто получается.
AD>>rand(i) генерирует число от 0 до i, так что будет.
_DA>Да, я одной особенности в коде не заметил ). Интересно, а при такой реализации равномерное распределение будет?
нет
если rand(i) => [0,i)
как минимум, шанс a[n-1] (с нуля) быть не на своём месте 100%
если rand(i) => [0,i]
то шанс a[i] (с нуля) быть на своём месте:
1/(i+1) + i/(i+1) * (i+1)/(i+2) * (i+2)/(i+3) * ... * (n-1)/(n) = 1/(i+1) + i/n
Здравствуйте, andrey.desman, Вы писали:
AD>Есть неинициализированный массив из 100 чисел. Дана функция rand(n), которая генерирует случайное число в диапазоне [0, n].
Моя rand(n) даёт результат в диапазоне [0, n) == [0, n-1]
Прибавь 1 для преобразования.
AD>Как это можно сделать?
вариант 1:
for (int i = 0; i < n; ++i) a[i] = i;
for (int i = 0; i < n-1; ++i)
{
int j = rand(n-i) + i;
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
вариант 2:
memset(a, -1, sizeof(int)*n);
for (int i = 0; i < n-1; ++i)
{
int j = rand(n-i) + i;
if (a[j] == -1) a[j] = j;
int temp = a[i];
if (temp == -1) temp = i;
a[i] = a[j];
a[j] = temp;
}
for (int i = 1; i < n - 1; ++i ) {
F>>>>> int j = rand(i);
F>>>>> a[i] = a[j];
F>>>>> a[j] = i;
F>>>>>}
_DA>>>>Дело в том, что необязательно на i-ом месте будет стоять число i после свопов. Поэтому не настолько просто получается.
AD>>>rand(i) генерирует число от 0 до i, так что будет.
_DA>>Да, я одной особенности в коде не заметил ). Интересно, а при такой реализации равномерное распределение будет?
C>нет
C>если rand(i) => [0,i) C>как минимум, шанс a[n-1] (с нуля) быть не на своём месте 100%
C>если rand(i) => [0,i] C>то шанс a[i] (с нуля) быть на своём месте: C>1/(i+1) + i/(i+1) * (i+1)/(i+2) * (i+2)/(i+3) * ... * (n-1)/(n) = 1/(i+1) + i/n
C>
Что-то ты путаешь, по-моему. У тебя для (n-1)-го (т.е. последнего) вероятность остаться будет равна 1
Если рассуждать по индукции: для n=1 и n=2 — алгоритм очевидно работает.
Дальше, пусть на k-ом шаге итерации на [0 .. k-1] всё распределено равномерно. k-ая перестановка (если rand(k) выдаёт равномерное число на [0 .. k]) приведёт к тому, что число k с вероятностью 1/(k+1) может оказаться на любой позиции из [0 .. k]. Аналогично, на k-ом месте может оказаться любое число из [0 .. k] с той же вероятностью. Т.е. на каждой итерации поддерживаетяс равномерность распределения на [0 .. k].
Здравствуйте, andrey.desman, Вы писали:
AD>Всем привет!
AD>Вот такую задачку получил недавно на собеседовании: AD>Есть неинициализированный массив из 100 чисел. Дана функция rand(n), которая генерирует случайное число в диапазоне [0, n].
AD>Заполнить массив числами [0, 99] в случайном порядке так, чтобы числа не повторялись.
AD>Мое решение: AD>Заполнить массив числами в порядке возрастания: a[i] = i, 0 <= i <= 99. AD>В цикле на 50 повторений сгенерировать два случайных индекса и поменять значения по этим индексам местами. AD>Уникальность и случайность есть, работает.
AD>Но экзаменатор ( ) утверждал, что можно сделать это за один проход. То есть каким-то образом сделать так, чтобы сразу получить последовательность уникальных чисел, при том, что rand в общем случае таких чисел не генерирует. AD>Как это можно сделать?
По-моему, все вообще элементарно.
Берем число 1 и определяем его номер в массиве вызовом rand(99). Перенумеровываем СВОБОДНЫЕ позиции массива от 0 до 98.
Берем число 2 и определяем его номер в массиве вызовом rand(98). Перенумеровываем СВОБОДНЫЕ позиции массива от 0 до 97.
........................................................................................................................
Берем число n и определяем его номер в массиве вызовом rand(100-n). Перенумеровываем СВОБОДНЫЕ позиции массива от 0 до 100-n-1.
................................................................................................................................
Здравствуйте, Sinus, Вы писали:
S>По-моему, все вообще элементарно. S>Берем число 1 и определяем его номер в массиве вызовом rand(99). Перенумеровываем СВОБОДНЫЕ позиции массива от 0 до 98. S>Берем число 2 и определяем его номер в массиве вызовом rand(98). Перенумеровываем СВОБОДНЫЕ позиции массива от 0 до 97. S>........................................................................................................................ S>Берем число n и определяем его номер в массиве вызовом rand(100-n). Перенумеровываем СВОБОДНЫЕ позиции массива от 0 до 100-n-1. S>................................................................................................................................
И получаем квадратичную сложность
Курица — это инструмент, с помощью которого одно яйцо производит другие.
Здравствуйте, vdimas, Вы писали:
_DA>>Да, я одной особенности в коде не заметил ). Интересно, а при такой реализации равномерное распределение будет?
V>Нет.
Будет. Доказательство см. выше.
Курица — это инструмент, с помощью которого одно яйцо производит другие.
Ну вообще да, если rand(i) вернет от 0 до i включительно, то согласен (посмотрел внимательней разъяснения, из кода этого вовсе не следовало). Просто обычно rand(i) возвращает число от 0-ля до i-1, в этом случае для каждого нового числа с порядковым номером k вероятность перестановки была бы 1, а не 1-(1/k). Хотя, для достаточно большого массива распределение было бы близко к равномерному даже в этом случае.
Здравствуйте, andrey.desman, Вы писали:
AD>Всем привет!
AD>Вот такую задачку получил недавно на собеседовании: AD>Есть неинициализированный массив из 100 чисел. Дана функция rand(n), которая генерирует случайное число в диапазоне [0, n].
AD>Заполнить массив числами [0, 99] в случайном порядке так, чтобы числа не повторялись.
AD>Мое решение: AD>Заполнить массив числами в порядке возрастания: a[i] = i, 0 <= i <= 99. AD>В цикле на 50 повторений сгенерировать два случайных индекса и поменять значения по этим индексам местами. AD>Уникальность и случайность есть, работает.
AD>Но экзаменатор ( ) утверждал, что можно сделать это за один проход. То есть каким-то образом сделать так, чтобы сразу получить последовательность уникальных чисел, при том, что rand в общем случае таких чисел не генерирует. AD>Как это можно сделать?
m = 100;
for (int i = 0; i < 100; ++i)
{
a[rand(m - 1)] = i ;
m = m - 1;
}
Тут не совсем случайно, но вы сможете используя этот метод, слегка оптимизировав его, и получите случайный расклад.
PS предполагаю что rand(m — 1) вернёт целое число от 0 до m-1. Если нет, просто приводить к целому
_>m = 100;
_>for (int i = 0; i < 100; ++i)
_>{
_>a[rand(m - 1)] = i ;
_>m = m - 1;
_>}
_>
_>Тут не совсем случайно, но вы сможете используя этот метод, слегка оптимизировав его, и получите случайный расклад. _>PS предполагаю что rand(m — 1) вернёт целое число от 0 до m-1. Если нет, просто приводить к целому
А какими значениями запольнять "дырки"?
допустим на 1 итерации rand(m — 1) вернет нам значение не равное m-1 что нам записывать в a[m-1] ведь в эту ячейку мы никогда больше не попадем?
Здравствуйте, frogkiller, Вы писали:
F>Здравствуйте, andrey.desman, Вы писали:
AD>>Вот такую задачку получил недавно на собеседовании: AD>>Есть неинициализированный массив из 100 чисел. Дана функция rand(n), которая генерирует случайное число в диапазоне [0, n].
AD>>Заполнить массив числами [0, 99] в случайном порядке так, чтобы числа не повторялись.
AD>>Как это можно сделать?
F>Посмотри, как работает типичная реализация std::random_shuffle. И мы точно знаем, что на i-м месте будет стоять число i, поэтому перемешивание можно совместить с инициализацией. Получится как-то так:
F>
for (int i = 1; i < n - 1; ++i ) {
F> int j = rand(i);
F> a[i] = a[j];
F> a[j] = i;
F>}
Ну а где инициализация-то? Может так:
S = 0;
S += rand(n/99);
a[0] = S;
for (int i = 1; i < 100; ++i ) {
int j = rand(i); //случайный порядок
a[i] = a[j];
S += rand(n/99); // случайные уникальные значения от 0 до n,
//S += (100-S)*(-ln(rand(n)/n)) //можно как-то сместить вероятность чтобы получить честное равномерное распределерние
a[j] = S;
}
Формально один проход. Хотя можно раскидать на два — инициализация уникальными-случайными-упорядочеными и перестановка.
Здравствуйте, Mazay, Вы писали:
F>>Посмотри, как работает типичная реализация std::random_shuffle. И мы точно знаем, что на i-м месте будет стоять число i, поэтому перемешивание можно совместить с инициализацией. Получится как-то так:
M>Ну а где инициализация-то?
F>>
for (int i = 1; i < n - 1; ++i ) {
F>> int j = rand(i);
F>> a[i] = a[j];
F>> a[j] = i; // <--- А вот же она!
F>>}
Тут просто совмещена инициализация числами по порядку от 0 до n и последующая random_shuffle — чтобы получился один проход.
Может так: M>
M>S = 0;
M>S += rand(n/99);
M>a[0] = S;
M>for (int i = 1; i < 100; ++i ) {
M> int j = rand(i); //случайный порядок
M> a[i] = a[j];
M> S += rand(n/99); // случайные уникальные значения от 0 до n,
M> //S += (100-S)*(-ln(rand(n)/n)) //можно как-то сместить вероятность чтобы получить честное равномерное распределерние
M> a[j] = S;
M>}
M>
M>Формально один проход. Хотя можно раскидать на два — инициализация уникальными-случайными-упорядочеными и перестановка.
Курица — это инструмент, с помощью которого одно яйцо производит другие.
) утверждал, что можно сделать это за один проход. То есть каким-то образом сделать так, чтобы сразу получить последовательность уникальных чисел, при том, что rand в общем случае таких чисел не генерирует.
Перекуём баги на фичи!
