Генерация случайных перестановок фиксированной длины строки

Question

Допустим, мой алфавит содержит X букв, а мой язык поддерживает только Y букв (Y

например. Алфавит = а, б, в, г, д, е, ж Y = 3

Так что слова будут: ааа ааЪ ААС аба .. БББ ссс .. (выше должно быть сгенерировано в случайном порядке)

Тривиальный способ сделать это - сгенерировать слова и затем рандомизировать список. Я не хочу этого делать. Я хочу генерировать слова в случайном порядке.

rondom (n) = letter [x] .random (n-1) не будет работать, потому что тогда у вас будет список слов, начинающийся с буквы [x] .., который сделает список не таким случайным. 1009 *

Любой код / ​​псевдокод приветствуется.

Answer 1

Как и предполагалось в других ответах, есть два основных подхода: 1) отслеживать то, что вы уже сгенерировали (предлагаемые решения в этой категории страдают от возможного прекращения работы), или 2) отслеживать, какие перестановки еще предстоит произвести (что подразумевает, что перестановки должны быть предварительно сгенерированы, что было специально запрещено в требованиях). Вот еще одно решение, которое гарантированно прекращает работу и не требует предварительной генерации, но может не соответствовать вашим требованиям к рандомизации (которые являются неопределенными на данный момент).

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

Без белой доски, чтобы представить это, я надеюсь, что это описание достаточно хорошо, чтобы описать то, что я имею в виду: создать «узел», который имеет ссылки на другие узлы для каждой буквы в алфавите. Это может быть реализовано с использованием общей карты букв алфавита в узлы или, если ваш алфавит фиксирован, вы можете создать конкретные ссылки. Узел представляет доступные буквы в алфавите, которые могут быть «произведены» далее для генерации перестановки. Начните генерировать перестановки, посетив корневой узел, выбрав случайную букву из доступных букв в этом узле, а затем пройдя эту ссылку до следующего узла. При каждом обходе создается письмо для перестановки. Когда достигается лист (то есть перестановка полностью построена), вы должны вернуться к дереву, чтобы увидеть, есть ли у оставшихся родительских узлов доступные перестановки; если нет, родительский узел может быть сокращен.

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

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

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

Answer 2

Итак, я понимаю, что вы хотите создать перестановку множества, используя как можно меньше памяти.

Во-первых, это невозможно сделать без использования памяти. Для вашей первой строки вам нужна функция, которая может генерировать любые строки с равной вероятностью. Скажем, эта функция называется nextString (). Если вы снова вызовете nextString (), не меняя ничего в состоянии, конечно, он снова сможет генерировать любую из строк.

Так что вам нужно что-то хранить. Вопрос в том, что нужно хранить и сколько места займет?

Строки можно увидеть как числа 0 - X ^ Y. (aaa = 0, aab = 1, aac = 2 ... aba = X ...) Таким образом, чтобы сохранить одну строку максимально эффективно, вам понадобятся биты lg (X ^ Y). Допустим, X = 16 и Y = 2. Тогда вам понадобится 1 байт памяти для уникального указания строки.

Конечно, самый наивный алгоритм состоит в том, чтобы пометить каждую строку в том виде, в каком она была получена, что занимает X ^ Y бит, что в моем примере составляет 256 бит (32 байта). Это то, что вы сказали, что не хотите делать. Вы можете использовать алгоритм перемешивания, как описано в этом вопросе: Создание случайного упорядоченного списка из упорядоченного списка (вам не нужно хранить строки, поскольку вы создаете их с помощью алгоритма перемешивания, но вам все еще нужно пометить их).

Хорошо, теперь вопрос в том, можем ли мы добиться большего успеха, чем это? Сколько нам нужно хранить, всего?

Ну, при первом звонке нам не нужно никакого хранилища. Во время второго звонка нам нужно знать, какой был произведен раньше. При последнем звонке нам нужно только знать, какой из них последний оставшийся. Так что худший случай - это когда мы на полпути. Когда мы на полпути, было произведено 128 строк, и осталось 128. Нам нужно знать, что осталось производить. Предполагая, что процесс действительно случайный, возможен любой раскол. Есть (256 выбрать 128) возможностей. Чтобы потенциально иметь возможность хранить что-либо из этого, нам нужно lg (256 выбирать 128) битов, который согласно калькулятору Google равен 251.67. Поэтому, если вы действительно умны, вы можете сжать информацию на 4 бита меньше, чем наивный алгоритм. Наверное, не стоит.

Если вы хотите, чтобы он выглядел случайным образом с очень небольшим объемом памяти, посмотрите этот вопрос: Ищете алгоритм для выделения последовательности чисел в (псевдо) случайном порядке

Answer 3

Я думаю, что вы можете сделать что-то довольно простое, сгенерировав случайный массив символов на основе вашего алфавита (в c #):

        char[] alphabet = {'a', 'b', 'c', 'd'};
        int wordLength = 3;

        Random rand = new Random();

        for (int i = 0; i < 5; i++)
        {
            char[] word = new char[wordLength];
            for (int j = 0; j < wordLength; j++)
            {
                word[j] = alphabet[rand.Next(alphabet.Length)];
            }
            Console.WriteLine(new string(word));
        }

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