无需搜索即可生成不重复字母的随机单词生成器

Question

传递给生成器的参数是什么：

x - 字数；
N 是字母表的大小；
L是输出字的长度。

有必要实现一个非递归算法，该算法将return一个基于传递的三个参数的单词。

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

对于N = 5, L = 3我们构建x对应词：

0: ABC
1：ABD
2：安倍
3：ACB
4: ACD
5：ACE
6：亚行
7：ADC
8 ADE
9：自动包围曝光
10 个 AEC
11 迪拉姆
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个元素替换为i到N-1中的一个随机元素来得到一个长度为L的随机单词我在 [0, L-1].

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

例如，N=5，L=3，字母表 = ABCDE。以 A（或任何字母）开头的单词数是 4！ / 2！ = 12。这些是可用 N-1 个字母的所有有序 N-L 长度子集。

所以 word(x, N, L) 的第一个字母是字母表中的 x / ((N-1)!/ (N-L)!) 字母（从零开始索引）。

然后您可以递归地构建单词。

例如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, 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)。这将每个单词映射到一个仅设置了三位的五位整数。更一般地说，您将每个单词映射到一个设置了 N 位的 L 位整数。

表示运行通过L位整数，统计设置位的个数。跟踪设置了 N 位的整数数量。当您到达所需位置时，将整数转换回单词：22 -> 10110 -> ACD。

如果简单的方法不够快，可以使用一些逻辑运算来加快设置位的计数速度。

ETA：我应该说清楚你是从 0b11111 到 0b00000 以相反的顺序扫描的。这与字母顺序相匹配。 ABC (11100) 在 CDE (00111) 之前。

无需搜索即可生成不重复字母的随机单词生成器

Generator of random words without repeating letters without searching

algorithm

random

generator

permutation

combinatorics