algorithm - 言語のすべての単語を列挙する

Question

私はちょうど2つの「1」と3つの「0」を持つ単語で構成される言語を持っています。この言語のすべての単語の有限集合を効率的に列挙するにはどうすればよいですか？

Answer 1

簡単です。数値11100を記述し、この値の順列の数を計算します= n！= 5 !、 31の順列の数で割る=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