枚舉一種語言的所有單詞

我有一個由正好具有兩個「1」和三個「0」的單詞組成的語言。我如何有效地枚舉這種語言的所有單詞的有限集？枚舉一種語言的所有單詞

2012-10-13 stracktracer

簡單，寫出數字11100，計算這個數值的排列次數= n！ = 5 !, 除以3 1的排列數= 3！和0的排列數= 2！ => 5！ /（2！* 3！）= 120 /（6×2）= 10

現在，如果你需要的實際值，對於任意的語言，你沒有其他選擇，只能使用一個回溯算法。

對於這個特殊的情況下，您可以輕鬆地構建一個簡單的算法來生成這個語言：下面是使用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

來源

2012-10-13 02:48:06

這就是計算有多少種方法有一個例子。如果我想輸出這些？ – stracktracer

我已經添加了一個簡單的算法來找出所有的值。 –

枚舉一種語言的所有單詞

回答

相關問題