언어의 모든 단어를 열거하십시오.

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 

을 = /.

이 특별한 경우를 들어, 당신은 쉽게이 언어를 생성하는 간단한 알고리즘을 구축 할 수 있습니다 : 여기에 얼마나 많은 방법으로 계산이다 파이썬

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