1

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

例如字母=a,b,c,d,e,f,g Y=3

所以这些词是：aaa aab aac aba .. bbb ccc .. （上面应该以随机顺序生成）

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

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

任何代码/伪代码表示赞赏。

4

3 回答 3

1

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

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

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

作为实现细节，节点可以存储在该点不能产生的字母集合或在那个点仍然可以产生的字母集合。为了可能减少存储要求，您还可以允许节点存储带有指示它正在执行的标志的标志，以便当节点允许超过一半的字母表时，它存储到目前为止产生的字母并切换到使用剩余的字母时可用的字母不到一半。

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

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

于 2009-06-22T16:09:05.710 回答
0

我认为您可以通过根据您拥有的字母（在 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));
        }

显然，这可能会产生重复，但如果需要，您可以将结果存储在 hashmap 或其他东西中以检查重复。

于 2008-12-14T19:18:02.113 回答
0

所以我认为你想要的是使用尽可能少的内存来产生集合的排列。

首先，它不能不使用内存来完成。对于您的第一个字符串，您需要一个可以产生任何具有相同可能性的字符串的函数。假设该函数称为 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 字节）。这就是你说你不想做的事。您可以使用此问题中讨论的 shuffle 算法：Creating a random ordered list from an ordered list（您不需要在通过 shuffle 算法生成字符串时存储字符串，但仍需要标记它们）。

好的，现在的问题是，我们能做得更好吗？我们总共需要存储多少？

好吧，在第一次通话时，我们不需要任何存储空间。在第二次调用时，我们需要知道之前生产的是哪一个。在最后一个调用中，我们只需要知道哪个是最后一个。所以最坏的情况是当我们进行到一半时。当我们进行到一半时，已经生产了 128 根弦，还有 128 根要走。我们需要知道还有哪些需要生产。假设这个过程是真正随机的，任何分裂都是可能的。有（256 种选择 128）种可能性。为了能够存储这些中的任何一个，我们需要 lg(256 选择 128) 位，根据谷歌计算器，它是 251.67。因此，如果你真的很聪明，你可以将信息压缩到比简单算法少 4 位。可能不值得。

如果您只是希望它看起来随机且存储空间很小，请参阅以下问题：寻找一种算法以（伪）随机顺序吐出一系列数字

于 2009-06-22T15:21:14.167 回答