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