不重复字母而不搜索的随机单词生成器

Question

传递给生成器的参数:

• x -字数;
• N为字母的大小;
• L为输出字的长度。

有必要实现一个非递归算法，该算法将根据传递的三个参数返回一个单词。

字母表-按字母顺序排列的拉丁字母，大写。

对于N = 5,L = 3，我们构造了x对应的词:

• 0:美国广播公司(ABC)
• 1: ABD
安倍
• 2:
• 3: ACB
• 4: ACD
• 5: ACE
• 6:亚行
• 7: ADC
• 8正面
• 9: AEB
• 10原子能委员会
11 AED
12 BAC
• …

我的算法实现适用于L = 1;2. 但在L = 3时出现错误。该算法基于访问字母表时的移位。h数组存储新字典中字母的索引(已经进入单词的字符不包括在内)。数组A将索引h的强制转换存储到原始字典中(为从字母表左侧移除的每个字符添加缩进)。因此，最终，数组A存储的是没有重复的排列。

private static String getS (int x, int N, int L) {
String s = "ABCDEFGHJKLMNOPQ";
String out = "";
int [] h = new int [N];
int [] A = new int [N];
for (int i = 0; i <L; i ++) {
h [i] = (x / (factory (N - 1 - i) / factory (N - L)))% (N-i);
int sum = h [i];
for (int j = 0; j <i; j ++)
sum + = ((h [i]> = h [j])? 1: 0);

A [i] = sum;
out + = s.charAt (A [i]);
}
return out;
} 

Answer 1

生成长度为L的随机单词:将字母表保存在大小为N的数组中，通过将i中的随机元素交换为N-1 (i在[0,L-1]中)，得到长度为L的随机单词。

按字母顺序生成长度为L的第x个单词:注意，对于大小为L的单词，由大小为N的字母表中的不同字母组成，有(N-1)个!/(N-L) !以任意给定字母开头的单词

。， N=5, L=3，字母表= ABCDE。以A(或任何字母)开头的单词数是4个!/2 != 12。这些是所有可用的N-1个字母的有序n -l长度的子集。

所以单词(x, N, L)的第一个字母是x/(N-1)!/(N-L)!)字母(0索引)。

然后你可以递归地构建你的词。

。， word(15,5,3, ABCDE):第一个字母是15/(4!/2!) = 15/12) = 1，所以b

我们递归地得到第二个字母:word((15%) (4!/2!)， 4,2, ACDE) = word(3,4,2, ACDE)。因为3/(3!/2!) = 3/3 = 1，第二个字母是c

第三个字母:word(% 3,3,1, ADE) = word(0,3,1, ADE) = a

0. ABC
1. ABD
2. ABE
3. ACB
4. ACD
5. ACE
6. ADB
7. ADC
8. ADE
9. AEB
10. AEC
11. AED
12. BAC
13. BAD
14. BAE
15. BCA

Answer 2

另一种方法。你有一个由五个字母组成的列表:[ABCDE]，你有一些由其中三个字母组成的单词，没有重复。因此，每个字母在单词中要么包含(1)，要么不包含(0)。它将每个单词映射到一个5位整数上，只设置了3位。在更一般的情况下，你有每个字映射到一个L位整数与N位集合。

这意味着遍历L位整数，计算集合位的个数。跟踪有多少个整数有N位。当您到达所需位置时，将整数转换回单词:22 ->10110→澳洲牧牛犬。

如果简单的方法不够快，有各种技巧可以使用一些逻辑运算来加速计数集位。

预计到达时间:我应该说清楚，你是按照从0b11111到0b00000的反向顺序扫描的。这与字母顺序相符。ABC(11100)在CDE(00111)之前。