Существует ли алгоритм, который при заданном упорядоченном списке символов {a1, a2, a3, ..., ak} генерирует за O (n) время новый список тех же символов в случайном порядке без смещения?«Без смещения» означает вероятность того, что любой символ s окажется в какой-то позиции p в списке 1 / k.
Предположим, что возможно генерироватьнепредвзятое целое число от 1-k включительно за O (1) время.Также предположим, что O (1) элемент доступа / мутации возможен, и что можно создать новый список размера k за O (k) времени.
В частности, я был бы заинтересован в 'генеративный алгоритм.То есть меня будет интересовать алгоритм, который имеет O (1) начальные издержки, а затем создает новый элемент для каждого слота в списке, занимая O (1) время на слот.
Если нет решениясуществует проблема, как описано, я все еще хотел бы знать о решениях, которые не соответствуют моим ограничениям одним или несколькими из следующих способов (и / или другими способами, если необходимо):
- theвременная сложность хуже, чем O (n).
- алгоритм смещен относительно конечных положений символов.
- алгоритм не является генеративным.
Я должен добавить, что эта проблема похожа на проблему случайной сортировки целых чисел из 1-k, поскольку мы можем отсортировать список целых чисел из 1-k, а затем для каждого целого числа i вВ новом списке мы можем получить символ ai.