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

Допустим, мой алфавит содержит X букв, а мой язык поддерживает только Y букв (Y <X ofcourse). Мне нужно сгенерировать все возможные слова в случайном порядке.

Например, алфавит = a, b, c, d, e, f, g Y = 3

Таким образом, слова будут такими: ааа ааа ааа ааа ... bbb ccc .. (выше должно быть сгенерировано в случайном порядке)

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

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

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

14.12.2008 19:07:18
Не могли бы вы рассказать нам, каковы требования к пространству? Есть ли у вас основания полагать, что проблему можно решить, используя меньше X для степени Y, и все же гарантировать завершение?
Norman Ramsey 14.12.2008 20:43:59
Вы должны быть более конкретными о том, «насколько случайным» он вам нужен, и о том, действительно ли вам нужна перестановка всего списка (все записи X ^ Y).
ShreevatsaR 14.12.2008 22:35:19
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));
        }

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

0
14.12.2008 19:18:02
Я хочу сгенерировать все записи X <sup> Y </ sup>. Если я использую ответ Зака, то нет никаких гарантий, что он прекратится. Если бы я хотел использовать hashmap ... я мог бы также вывести все в hashmap и распечатать его, так как hashmap все равно будет случайным образом вводить записи для меня.
Sridhar Iyer 14.12.2008 20:00:09
ОК, неправильно понял, извините - похоже, вы должны использовать метод грубой силы и генерировать все возможные комбинации и рандомизировать, я полагаю. Возможно, промежуточным решением было бы бросить все это в файл и прочитать строки оттуда!
Jennifer 14.12.2008 20:06:53

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

Во-первых, это невозможно сделать без использования памяти. Для вашей первой строки вам нужна функция, которая может производить любые строки с равной вероятностью. Скажем, эта функция называется 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 Calculator, составляет 251,67. Поэтому, если вы действительно умны, вы можете сжать информацию на 4 бита меньше, чем наивный алгоритм. Наверное, не стоит.

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

0
23.05.2017 11:48:38

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

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

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

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

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

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

1
22.06.2009 16:09:05
Мне нравится этот ответ, но я думаю, вы правы, что он не даст вам равномерно случайное распределение. Я думаю, что для получения равномерных вероятностей вам необходимо отслеживать, сколько оставшихся листьев доступно в каждой ветви узла. Затем используйте эти подсчеты, чтобы определить, какую ветку вы случайно выбрали из этого узла.
Nate Kohl 22.06.2009 16:37:50