Способы определения случайной генерации в вызовах

16

Примечание : согласно консенсусу по Meta , вопросы по находятся здесь по теме.

В свете этой «вещи, которую следует избегать при написании задач» , я начал думать о проблемах, связанных со случайным генерированием определенных видов объектов.

Иногда случается так, что я хочу опубликовать задачу по которая включает случайную генерацию foo, где

  1. очень легко проверить, является ли данная вещь foo, и
  2. немного сложнее быстро создать «качественную» случайную фу.

В качестве примера, foo может быть двоичной матрицей, в которой нет сегментов из 4 равных битов в любом направлении. Легко проверить, является ли данная двоичная матрица foo, но генерация случайного foo с хорошо распределенным распределением, кажется, требует алгоритма обратного отслеживания или чего-то подобного.

В любом случае, теперь мне нужно объективно указать, что можно считать случайным foo, и я бы хотел, чтобы оно было «непредсказуемым» в интуитивном смысле, что, когда я запускаю программу несколько раз, результаты всегда выглядят по-разному. Наиболее ограничительный подход - требовать, чтобы выходные данные были равномерно случайными: все действительные foos имеют одинаковую вероятность генерации. Это обычно слишком ограничительно, потому что я понятия не имею, как это сделать, за исключением генерации всех допустимых foo, удаления дубликатов и выбора одного, что скучно и медленно.

Моя следующая идея - потребовать, чтобы все действительные foo имели положительную вероятность возникновения. Однако это означает, что следующий подход верен: генерировать случайную вещь, похожую на foo (в нашем примере - случайную двоичную матрицу), если это foo, затем возвращать ее, в противном случае возвращать жестко закодированный foo (скажем, единичную матрицу) ). Это также несколько скучно, так как в основном это просто распознаватель foos, привязанный к генератору случайных матриц.

Может ли быть хорошее общее определение непредсказуемо случайного foo?

TL; DR

Есть ли хороший способ указать «непредсказуемый» случайным образом сгенерированный объект, который не исправляет распределение, но препятствует жесткому кодированию?

Zgarb
источник
У нас есть стандартное определение для random на meta, которое запретило бы жесткое кодирование, но не ограничивало бы его настолько, чтобы оно было абсолютно однородным.
Geobits
5
Отличный вопрос В прошлом я обнаружил, что указывать случайность сложно . Специально для сценария, который вы описываете, существует также проблема, заключающаяся в том, что вы можете просто сгенерировать случайных кандидатов и повторить, если они недействительны. Это даже дает вам равномерное распределение, но недетерминированное время выполнения. При определении равномерного распределения также существует проблема, заключающаяся в том, что реальные решения никогда не бывают абсолютно одинаковыми. Это очень тонкий вопрос. +1
Мартин Эндер
@ MartinEnder Правильно, я забыл этот подход. Я могу запретить его и другой медленный алгоритм с временными границами, но они все еще допускают решение «один жестко запрограммированный foo».
Згарб
похоже, что вы могли бы указать K3 / K4 CPRNG, большинство языков будет иметь библиотеку en.wikipedia.org/wiki/Pseudorandom_number_generator
Ewan
1
@Zgarb большая проблема с запретом «Сгенерировать и повторить» состоит в том, что большинство библиотек RNG языка делают именно это.
Натан Меррилл

Ответы:

5

Вернуть тысячу разных фо

Это делает невозможным возвращать жестко закодированные значения и иметь наполовину приличный гольф. Однако у легального генератора foo есть небольшой шанс вывести дубликаты foo, если он не проверяет их. Чтобы снять бремя проверки, эмпирически протестированная частота отказов, скажем, 10%, может быть указана как приемлемая.

Имейте в виду парадокс дня рождения , что вероятность дубликатов может быть выше, чем вы думаете. Если существует только миллион возможных foos, то тысяча случайных foo будет иметь вероятность около 0,6, что где-то есть дубликат, и это предполагает, что генерация foo является полностью однородной. Если это может быть проблемой, потребуйте, скажем, 900 уникальных foos для каждых 1000 генерируемых, что гораздо более щедро для подлинного генератора foo, но все же непрактично для жесткого кодирования.

Это также позволяет вам многократно генерировать похожие на foo вещи и проверять глупость, пока вы не получите foos. Я думаю, что это правильное решение сам, но если вам не нравится:

Сделай это быстро

Вероятность того, что foo-подобная вещь будет foo-подобной, вероятно, весьма мала, поэтому указание ограничения по времени может привести к подлинной попытке генерации foo.

Чтобы учесть разницу в скорости между разными языками, вы можете установить разные временные ограничения в зависимости от языка, например Hackerrank: https://www.hackerrank.com/environment . Однако, если вы укажете достаточно большие foo, вероятность того, что foo-подобные вещи будут foo, может быть очень низкой, поэтому может быть достаточно правила «до тепловой смерти Вселенной».

Джеймс Холлис
источник
Я думаю, что вы на что-то здесь. «Запуск программы N раз не даст дубликатов, по крайней мере, в 90% случаев», является конкретным и довольно простым для тестирования, и его можно комбинировать с ограничением по времени, чтобы предотвратить грубое форсирование и простую выборку отбраковки.
Згарб
2

Я не претендую на окончательное решение проблемы (или на то, что этот список является исчерпывающим), но я хочу обрисовать некоторые возможные подходы, которые приходят на ум и почему они будут работать или не будут работать. Я также не буду касаться таких вопросов, как то, является ли использование текущей временной метки в качестве источника случайности достаточно «непредсказуемым», и как применять определенные свойства распределения вероятностей - я просто сосредоточусь на том, чтобы избегать решений, использующих жесткое кодирование.

Не решение: явное запрещение жесткого кодирования

Это плохая идея. Это ненаблюдаемое требование (что означает, что вы не можете определить, удовлетворено ли оно, просто запустив программу), что настоятельно не рекомендуется в PPCG и может быть совершенно невозможно при запуске программы на любой другой платформе, где представления проверяются в автоматизированный способ Проблема с таким требованием заключается в том, что вам нужно начать с нахождения объективного определения «жесткого кодирования». В общем, если вы попробуете это, вы только ухудшите положение.

Сделать жесткое кодирование невозможным

Если вы не можете полностью запретить это, но не хотите, чтобы люди его использовали, тогда вы можете попытаться спроектировать проблему так, чтобы жесткое кодирование просто не было конкурентным подходом. Это возможно, если объекты, которые должны быть сгенерированы, являются достаточно большими и несжимаемыми, что для размещения одного примера в коде потребуется намного больше байтов, чем для написания алгоритма, который генерирует правильные решения случайным образом. В вашем конкретном примере это, конечно, не так, потому что матрицы идентичности допустимы и, как правило, их легко генерировать, но для других проблем это может быть не так. Если целевые объекты достаточно нерегулярны, просто потребуйте, чтобы они были большого размера, что, вероятно, не повлияет на количество байтов реального алгоритма, но взорвет жестко-закодированную часть.

Параметризация выхода

Часто эти проблемы связаны с одним или несколькими естественными параметрами, такими как размер матрицы в вашем примере. Если это так, сделать этот параметр входным может быть достаточно, чтобы сделать жесткое кодирование невозможным или, по крайней мере, нецелесообразным. В некоторых случаях может быть легко жестко закодировать одно конкретное решение для заданного значения параметра, которое было найдено вручную или с помощью расширенного поиска, но, возможно, не существует простой закрытой формы для экземпляра этого решения в целом, так что это не так Можно легко сгенерировать значение по умолчанию для произвольных входов. Опять же, это не относится к примеру, который вы упомянули, потому что единичная матрица работает с любым размером, но является оптимальным решением для этой связанной проблемы.обычно очень нерегулярный, поэтому невозможно иметь значение по умолчанию без активного поиска допустимых значений в любом случае. Вы можете объединить это с ограничением по времени, чтобы избежать грубого поиска значения по умолчанию.

Положить некоторые ограничение на распределение вероятностей

Если вы готовы отказаться от абсолютно неограниченного распределения вероятностей, вы можете наложить на него некоторые ограничения, которые все же дают ответчикам большую свободу в выборе их распределения, но которые затрудняют или делают невозможным жесткое кодирование:

  • Самое простое ограничение, которое приходит на ум, - это требовать, чтобы разница между минимальной и максимальной вероятностью для любого возможного выхода была ниже определенного порога. Жестко закодированный подход, вероятно, будет иметь почти нулевые вероятности для почти всех выходов и вероятность, близкую к 1 для значения по умолчанию. Если вам требуется, чтобы максимальная разница была, например, ниже 0,1, то для обеспечения возможности захода на посадку потребуется 10 (случайно выбранных) значений по умолчанию. Точно так же вы могли бы просто потребовать минимальную вероятность для каждого возможного выхода, например, 1 / (2 * N *), где N - количество возможных выходов.
  • В качестве альтернативы вы можете потребовать, чтобы в распределении не было (вероятностных) пробелов, чтобы не было интервала размера δ (выбранного вами) , так чтобы существовали как более высокие, так и более низкие вероятности. Это означает, что не может быть никаких отклонений с точки зрения вероятности, которые, вероятно, генерируются жестким кодированием.

Основная проблема этих подходов заключается в том, что о них гораздо сложнее рассуждать, доказать правильность ответов сложно, а экспериментальная проверка правильности может быть невозможна для больших выходных пространств. Тем не менее, они обеспечивают принципиально наблюдаемое требование для программы, которое может сделать невозможным жесткое кодирование.

Этим подходам может также потребоваться ограничение по времени, поскольку одним из способов увеличения вероятности значений, отличных от значений по умолчанию, будет попытка найти случайное foo несколько раз, прежде чем вернуться к значению по умолчанию.

Мартин Эндер
источник