枚举序列中一种语言的所有单词

Question

我已经使用以下方法成功枚举了语言 Σ={a*} 和 Σ={a^n b^n} 的所有单词：

public class AStar {
    public static int n = 0;
    public static void main(String[] args) {
        for(int i=0;i<10;i++){
            System.out.println(next());
        }
    }

    public static String next(){
        String as="" , bs="";
        String s= "";
        for(int i=0; i<n; i++) {
            as+="a"; bs+="b";
            s=as+bs;
        }
        n++;
        return s;
    }
}

在每次调用 next() 时，它都会打印一个这样的单词（使用 for 循环多次调用 next）： ab, aabb, aaabbb, ......, a^n b^n

当前问题

现在我正在研究一个类似的 class，它可以枚举语言 Σ*={a,b}

在每次调用 next() 时，它应该 return 在先前 return 编辑的单词之后出现一个新单词，例如，它应该 return 这些单词：

'', 'a', 'b', 'aa', 'ab', 'ba', 'bb', 'aaa', ......最多有n个字面值的单词

文字的顺序无关紧要，我试过这个逻辑但到目前为止没有成功

public class ABStar {
    static int col=0, row=0, cur=0, rlen=0, flag=1, set=0;
    public static void main(String[] args) {
        for(int i=0;i<5;i++){
            System.out.println(next());
        }
    }
    public static String next(){
        String s="";
        row = 1 << col;
        rlen = row/2;
        for(int i=1; i<=row; i++){
            for(int j=1 ; j<=col ; j++){
                if(col==1 && flag ==1){
                    return s+="a";
                }
                else if(col==1 && flag ==2){
                    return s+="b";
                }
                rlen --;
                if(rlen==0){
                    flag = 3-flag;
                    rlen=row/2;
                }
            }
        }
        col++;
        return "";
    }
}

我正在使用标志 col(columns)、row(rows)、cur(current)、flag(1 代表 a，2 代表 b)、rlen（每个标志的行长度），我正在使用这些属性用于保留不同调用之间的状态。

我尝试了将近 2 打逻辑来解决这个问题，但都是徒劳的，请帮助我解决这个问题，我将不胜感激。

Answer 1

两个字符字母表的优雅解决方案

因为你的字母表中只有两个字母，一个优雅的解决方案可能是使用整数的二进制分解（a 代表一个二进制 0 而 b 代表一个 1).这是您可以实施的算法：

private static final int MAX_LENGTH = 3;

public static void main(String[] args) {
    int wordLength = 1;
    int current = 0;
    int max = (1 << wordLength) - 1;

    while (wordLength <= MAX_LENGTH) {
        System.out.println(makeWord(current, wordLength));

        if (current < max) current++;
        else {
            wordLength++;
            current = 0;
            max = (1 << wordLength) - 1;
        }
    }
}

private static String makeWord(int current, int wordLength) {
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < wordLength; i++) {
        sb.append((char) ((current % 2) + 'a'));
        current >>= 1;
    }
    return sb.reverse().toString();
}

输出：

a
b
aa
ab
ba
bb
aaa
aab
aba
abb
baa
bab
bba
bbb

任何字母表的通用解决方案

您可以通过以 k（其中 k 是字母表的大小）而不是 2 为基数来概括上述解决方案。它可能看起来像这样：

public static void main(String[] args) {
    listWords(new char[]{ 'e', 'z', 'f' }, 3);
}

private static void listWords(char[] alphabet, int maxWordLength) {
    Arrays.sort(alphabet);
    int base = alphabet.length;

    int wordLength = 1;
    int current = 0;
    int max = (int) Math.pow(base, wordLength) - 1;

    while (wordLength <= maxWordLength) {
        System.out.println(makeWord(alphabet, current, wordLength));

        if (current < max) current++;
        else {
            wordLength++;
            current = 0;
            max = (int) Math.pow(base, wordLength) - 1;
        }
    }
}

private static String makeWord(char[] alphabet, int current, int wordLength) {
    int base = alphabet.length;

    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < wordLength; i++) {
        sb.append(alphabet[current % base]);
        current /= base;
    }
    return sb.reverse().toString();
}

输出：

e
f
z
ee
ef
ez
fe
ff
fz
ze
zf
zz
eee
eef
eez
efe
eff
efz
eze
ezf
ezz
fee
fef
fez
ffe
fff
ffz
fze
fzf
fzz
zee
zef
zez
zfe
zff
zfz
zze
zzf
zzz

请注意，此实现将比前一个慢很多，因为与二进制移位相比，除法和 Math.pow 是慢操作。

非算术通解

basek中的计数逻辑也可以手动实现。它可能更有效率，但肯定会花费更多时间和代码。下面是算法的总体思路：

您首先用最低值填充字符串
然后，你增加最后一个字符的值
当你不能再递增时，你重置当前位置右侧的所有字符
你增加你的位置，并增加这个位置的价值
你从字符串的右边开始做同样的事情

这很酷的是，如果你使用 StringBuilder，你可以将数组分配的数量减少到每次迭代只有一个，因为 StringBuilder 的每个状态都可以在几个来自先前状态的操作（与字符串的长度成比例）。

Answer 2

按照@Dici的方法，我写了这段代码专门解决了我的问题。

public class SigmaStar {

//max length of word, just to limit the execution
//change it with your own value
private static final int MAX_LENGTH = 4;

public static void main(String[] args) {
    int wordLength = 0;
    int current = 0;
    int max = (1 << wordLength) - 1;

    while (wordLength <= MAX_LENGTH) {
        System.out.println("'"+makeWord(current, wordLength)+"'");

        if (current < max) current++;
        else {
            wordLength++;
            current = 0;
            max = (1 << wordLength) - 1;
        }
    }
}

private static String makeWord(int current, int wordLength) {
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < wordLength; i++) {
        sb.append((char) ((current % 2) + 'a'));
        current >>= 1;
    }
    return sb.reverse().toString();
}

}

枚举序列中一种语言的所有单词

Enumerate all words of a language in a sequence

java

enumeration

两个字符字母表的优雅解决方案

任何字母表的通用解决方案

非算术通解