algorithm - 生成字符串的随机固定长度排列

Question

假设我的字母表包含 X 个字母，而我的语言仅支持 Y 个字母的单词(当然是 Y < X)。我需要以随机顺序生成所有可能的单词。

例如字母表=a,b,c,d,e,f,gY=3

所以的话就是:啊啊aabaac阿坝..bbb抄送..(以上应该是随机生成的)

简单的方法是生成单词，然后随机化列表。我不想那样做。我想以随机顺序生成单词。

rondom(n)=letter[x].random(n-1) 将不起作用，因为那样你将得到一个以字母[x] 开头的单词列表。这将使列表不那么随机。

感谢任何代码/伪代码。

Answer 1

正如其他答案所暗示的那样，有两种主要方法:1) 跟踪您已经生成的内容(此类中提出的解决方案可能永远不会终止)，或 2) 跟踪尚未生成的排列(哪些暗示排列必须预先生成，这在要求中是明确不允许的)。这是另一种保证终止且不需要预生成的解决方案，但可能无法满足您的随机化要求(此时模糊)。

一般概述:生成一棵树来跟踪已生成的内容或剩余的内容。通过遍历树中的随机链接来“选择”新的排列，在该排列生成后修剪叶子处的树以防止再次生成它。

没有白板来绘制这个图，我希望这个描述足以描述我的意思:创建一个“节点”，该节点链接到字母表中的每个字母的其他节点。这可以使用字母表字母到节点的通用映射来实现，或者如果您的字母表是固定的，您可以创建特定的引用。该节点表示字母表中的可用字母，接下来可以“生成”这些字母以生成排列。通过访问根节点开始生成排列，从该节点的可用字母中选择一个随机字母，然后遍历该引用到下一个节点。每次遍历，都会为排列生成一个字母。当到达一片叶子时(即完全构建了一个排列)，您将回溯树以查看父节点是否还有剩余的可用排列；如果不是，则可以修剪父节点。

作为实现细节，节点可以存储在该点无法生成的字母集或在该点仍可生成的字母集。为了可能减少存储需求，您还可以允许节点存储 either 并带有一个标志，指示它正在做什么，这样当节点允许超过一半的字母表时，它会存储到目前为止生成的字母，并且当可用的字母少于一半时切换到使用剩余的字母。

使用这样的树结构限制了无需预先生成所有组合就可以生成的内容，因为您不需要预先构建整个树(它可以在生成排列时构建)并且可以保证由于节点的清除而完成(即，当这是未生成排列的允许组合时，您仅遍历节点链接)。

不过，我认为该技术的随机化有点奇怪，而且我认为每种组合在任何给定时间生成的可能性都不相同，尽管我还没有认真考虑过这一点。还可能值得注意的是，尽管不一定要预先生成完整的树，但所涉及的开销可能足以让您最好预先生成所有排列。