비트 마스크를 사용하여 순열 생성

Question

인터넷에서 프로그래밍 문제에 대한 답변을하고 있었으므로이 문제에 관심이 있습니다. 문자열의

이 코드를 인쇄 모든 순열을 사전 식 : 문제는 다음과 같이 정의된다. 뭔가 잘못되었습니다. 한 줄을 수정하거나 추가하여 찾아서 수정하십시오!

입력 :

입력 사이의 공백없이 소문자의 문자열을 포함하는 단일 선으로 구성. 길이는 최대 7 자이며 문자는 사전 식으로 정렬됩니다.

출력 :

전적으로 나열된 각 줄에 하나를 인쇄 문자열의 모든 순열.

def permutations(): 
global running 
global characters 
global bitmask 
if len(running) == len(characters): 
    print(''.join(running)) 
else: 
    for i in xrange(len(characters)): 
     if ((bitmask>>i)&1) == 0: 
      bitmask |= 1<<i 
      running.append(characters[i]) 
      permutations() 
      running.pop() 

raw = raw_input() 
characters = list(raw) 
running = [] 
bitmask = 0 
permutations() 

누군가 내게 답변하고 어떻게 작동하는지 설명 할 수 있습니까? 나는 비트 마스킹의 응용에 정말로 익숙하지 않다. 고맙습니다.

당신은 줄을 추가하여 비트 마스크 비트 0을 다시해야

Answer 1

:

bitmask ^= 1<<i 

코드 :

def permutations(): 
    global running 
    global characters 
    global bitmask 
    if len(running) == len(characters): 
     print(''.join(running)) 
    else: 
     for i in xrange(len(characters)): 
      if ((bitmask>>i)&1) == 0: 
       bitmask |= 1<<i 
       running.append(characters[i]) 
       permutations() 
       bitmask ^= 1<<i #make the bit zero again. 
       running.pop() 

raw = raw_input() 
characters = list(raw) 
running = [] 
bitmask = 0 
permutations() 

설명 :
비트 마스크가 취급하는 정수 비트 문자열. 귀하의 경우이 문자열의 길이는 입력 문자열의 길이와 같습니다.

이 문자열의 각 위치는 해당 문자가 부분적으로 작성된 문자열에 이미 추가되었는지 여부를 나타냅니다.

코드는 빈 문자열에서 시작하는 새 문자열을 작성하여 작동합니다. 모든 문자가 추가 될 때마다 비트 마스크가이를 기록합니다. 그런 다음 문자가 더 추가 될 때까지 문자열이 재귀로 더 깊숙이 보내집니다. 재귀에서 코드가 반환되면 추가 된 문자는 이고 비트 마스크 값은 원래 값인으로 만들어야합니다.

마스킹에 대한 자세한 내용은 여기를 참조하십시오. http://en.wikipedia.org/wiki/Mask_%28computing%29

편집 :
입력 문자열이 "ABCDE"이며, 코드의 실행의 어느 지점에서 비트 마스크가 "00100"말한다. 이것은 문자 'c'만이 부분적으로 만들어진 문자열에 지금까지 추가되었음을 의미합니다. 따라서 'c'문자를 다시 추가하면 안됩니다.
"if"조건 ((bitmask >> i) & 1) == 0은 비트 마스크의 i 번째 비트가 설정되었는지, 즉 i 번째 문자가 이미 문자열에 추가되었는지 여부를 확인합니다. 추가되지 않으면 문자 만 추가되고 그렇지 않으면 추가되지 않습니다.

비트 작업이 새로운 것이라면 인터넷에서이 항목을 찾아 보시기 바랍니다.