algorithm - 枚举一种语言的所有单词

Question

我有一种语言，由两个“1”和三个“0”组成的单词组成。如何有效地枚举该语言所有单词的有限集？

Answer 1

简单，写数字11100，计算这个值的排列次数=n！= 5!，除以 3 个 1 的排列数 = 3! 和 0 的排列数 = 2！=> 5！/ (2! * 3!) = 120 / (6 * 2) = 10

11100
11010
11001
10110
10101
10011
01110
01101
01011
00111

现在，如果您需要实际值，对于任意语言，您别无选择，只能使用回溯算法。

对于这种特殊情况，您可以轻松构建一个生成这种语言的简单算法：这是一个使用 python 的示例

def GenerateLanguage(nZeros, nOnes):
    if nZeros + nOnes == 0:
         return ['']
    res = [] # Resulting list, initialize with 1 empty string
    if nOnes > 0: # If we have 1's left, build all the strings that starts with a 1
         for l in GenerateLanguage(nZeros, nOnes - 1):
              res.append('1' + l)
    if nZeros > 0: # If we have 0's left, build all the strings that starts with a 0
         for l in GenerateLanguage(nZeros - 1, nOnes):
              res.append('0' + l)
    return res