Описание тега randomized-algorithm
0
ответов
Алгоритм поиска случайных ближайших пар точек [закрыто]
Order the points in a random sequence p1, p2,..., pn Let δ denote the minimum distance found so far Initialize δ = d(p1, p2) Invoke MakeDictionary for storing subsquares of side length δ/2 For i = 1, 2, . . . , n: Determine the subsquare Sst contai…
06 мар '21 в 12:38
3
ответа
Структура данных для случайного удаления и вставки, где элементы взвешиваются в [a,b]
Я хотел бы разработать структуру данных и алгоритм таким образом, чтобы, учитывая массив элементов, где каждый элемент имеет вес в соответствии с [a,b], я мог добиться постоянного времени вставки и удаления. Удаление выполняется случайным образом, п…
08 мар '21 в 22:10
0
ответов
Вычисление медианы (или приблизительной медианы) 1 триллиона удвоений
Это был вопрос для интервью, размещенный на Glassdoor. Рассмотрим файл с 1 триллионом двойников. Как вы можете найти медиану или приблизительную медиану? Ваш компьютер не может прочитать 1 триллион двойников. Допускается распараллеливание алгоритма.…
14 мар '21 в 22:10
1
ответ
Случайное присвоение значений строкам в python
У меня есть следующая таблица ввода (y): n = 9 TGn = round(len(y)/n) idx = set(y.index // TGn) y = y.apply(lambda x: x.sample(frac=1,random_state=1234)).reset_index(drop=True) treatment_groups = [f"A{i}" for i in range(1, n+1)] y['groupAfterRandomiz…
23 мар '21 в 15:53
3
ответа
Блокировать рандомизацию с помощью Python?
У меня есть следующая таблица ввода (df): Произвольно выбранные строки так, чтобы в каждой группе были все блоки (равномерно распределенные). Что я пробовал до сих пор? df = df.groupby('blocks').apply(lambda x: x.sample(frac=1,random_state=1234)).re…
23 мар '21 в 11:28
1
ответ
двудольная сеть. Сохраняющая степень рандомизация с ограничениями.
Я работаю над выборкой данных, содержащей несколько статей, темы, к которым они относятся, и годы публикации этих статей, это выглядит так: Я пытаюсь перетасовать годы публикации этих статей (оставьте количество статей по каждой теме и публикуемых в…
04 апр '21 в 15:45
0
ответов
Как на самом деле узел выбирается в качестве следующего создателя блока в случайном выборе блока?
При случайном выборе блока с каждым блоком связано поле подписи генерации. Каждый узел подписывает этот параметр своим открытым ключом, и он вычисляет его хэш (используя SHA-256). Первые 8 байтов результирующего хэша обозначаются как «попадание» узл…
15 апр '21 в 20:32
2
ответа
Почему рандомизированная быстрая сортировка лучше стандартной быстрой сортировки?
По словам самого Кормена: «Разница в том, что с детерминированным алгоритмом конкретный входной сигнал может вызвать это наихудшее поведение. Однако с рандомизированным алгоритмом никакой вход не всегда может вызвать наихудшее поведение». Как добавл…
04 май '21 в 21:58
0
ответов
В цепочке выбираются соответствующие обновления после события Math.random()
Я переношу свой любимый проект Excel на HTML и javascript. Мне нужно, чтобы дочерние выборки оставались ограниченными родительским выбором во время перетасовки. В настоящее время связанные выборки прекрасно работают при ручном выборе, но когда я пер…
08 май '21 в 04:47
1
ответ
Заменить запятые пробелами? Рандомизация Фишера-Йейтса
Спасибо B4ndy за помощь в рандомизации Фишера Йейтса, он помог мне здесь преобразовать число в слова: Поскольку функции перемешивания перемешивают индексы массивов, вы можете просто перемешать массив так же, как вы это делали, но добавить строки име…
09 июн '21 в 00:14
0
ответов
Рандомизированные алгоритмы, Алгоритмы аппроксимации
Вопрос взят из «Проекта алгоритмов» Джона Келинберга и Евы Тардос: У меня проблемы с этим вопросом, я до сих пор думаю подождать, пока закончится половина заявок, и дождаться одной ставки, которая будет больше, чем все те, которые я видел
16 июн '21 в 16:15
0
ответов
Алгоритм варианта набора вершин обратной связи
В наборе вершин почти обратной связи нам дан неориентированный граф G и целое число k, и цель состоит в том, чтобы решить, существует ли подмножество 𝑆⊆𝑉(𝐺) размера не более k такое, что каждая связная компонента в 𝐺− либо дерево или цикл Цель состо…
11 июл '21 в 10:35
1
ответ
Можем ли мы оптимизировать рандомизированную быструю сортировку с помощью хвостовой рекурсии?
Я знаю, что мы можем оптимизировать быструю сортировку, используя хвостовую рекурсию, удалив более одного вызова рекурсии и сократив его до однократного одного вызова рекурсии: - void quickSort(int arr[], int low, int high) { if (low < high) { in…
22 июл '21 в 14:29
0
ответов
Сетевой анализ - создание случайной нулевой сети из существующей сети.
Я создал сеть, используя следующий код, который я использовал для расчета сетевых показателей, таких как степень и сила графа. dat <- node_dat %>% filter(code == "25537") %>% filter(monthyear =="2015/03") #create network data AID = dat$code…
28 июл '21 в 11:28
2
ответа
Нужен пример рандомизации сетки с символами, которые имеют разное количество
Я хотел бы увидеть примеры того, как можно рандомизировать сетку с разными значениями. это оригинальная доска string[,] board = new string[4, 4]; for (int y = 0; y < 4; y++) { for (int x = 0; x < 4; x++) { board[x, y] = "."; } } Я пытаюсь прид…
26 авг '21 в 17:35
0
ответов
Дисперсия количества сравнений в быстрой сортировке Лас-Вегаса
Итак, у меня есть задание по алгоритмам Лас-Вегаса. В частности, мне нужно реализовать рандомизированную быструю сортировку и запустить ее для 10^5 в последовательности из 10^4 элементов. И хотя среднее значение, которое я получаю в результате вычис…
28 авг '21 в 18:32
0
ответов
Создание алгоритма стратифицированной блочной рандомизации в R с неравной вероятностью распределения [закрыто]
Я пытаюсь создать алгоритм стратифицированной блокированной рандомизации для размера выборки 250. Условия следующие: размер блока = 9 должны быть стратифицированы по полу (женский / мужской) вероятность попадания в экспериментальную группу составляе…
28 сен '21 в 05:51
0
ответов
Как убедиться, что рандомизированные координаты не попадут в конкретные координаты в 2D-массиве? Язык - C
Я создаю игру на C, и я хочу случайным образом разместить блоки и продукты внутри 2d-массива. Я произвольно распределил координаты x и y блоков и еды в 1d-массивы, то есть foodCol [] и foodRow []; blockCol [] и blockRow []. Однако есть вероятность, …
07 дек '21 в 09:10
0
ответов
Алгоритм решения CLRS нуждается в более подробном обсуждении
Докажите, что индикаторная случайная величина Xk и значение T(max(k - 1, n - k)) независимы. Ответ Вероятность того, что X_k равно 1, не меняется, когда мы знаем максимальное значение k-1 и nk. Другими словами, Pr{X_k =a| max(k-1, nk)=m} = Pr{X_k=a}…
16 фев '22 в 05:03
1
ответ
Как вставить случайный элемент на карту Anki?
В Anki на лицевой стороне карточки написано « X+Y? », а на обороте — « Z ». Например, спереди « 4+7? », а сзади « 11 ». Но я хочу, чтобы в следующий раз, когда я увижу эту карту, числа были другими, рандомизируя элементы X, Y и Z. Я думаю, это может…
22 фев '22 в 00:56