Python-역 추적

역 추적은 재귀의 한 형태입니다. 그러나 그것은 모든 가능성 중에서 옵션만을 선택하는 것을 포함합니다. 이 특정 옵션이 필요한 솔루션을 제공하지 않는다고 결론을 내릴 경우 옵션을 선택하고이를 역 추적하는 것으로 시작합니다. 원하는 솔루션을 얻을 때까지 사용 가능한 각 옵션을 탐색하여 이러한 단계를 반복합니다.

다음은 주어진 문자 세트의 가능한 모든 배열 순서를 찾는 예입니다. 쌍을 선택할 때 정확한 쌍이 이미 생성되었는지 여부를 확인하기 위해 역 추적을 적용합니다. 아직 생성되지 않은 경우 쌍이 응답 목록에 추가되고 그렇지 않으면 무시됩니다.

def permute(list, s):
    if list == 1:
        return s
    else:
        return [ y + x
                 for y in permute(1, s)
                 for x in permute(list - 1, s)
                 ]

print(permute(1, ["a","b","c"]))
print(permute(2, ["a","b","c"]))

위의 코드가 실행되면 다음과 같은 결과가 생성됩니다.

['a', 'b', 'c']
['aa', 'ab', 'ac', 'ba', 'bb', 'bc', 'ca', 'cb', 'cc']