파이썬 순열 재귀 Permutation

알고리즘을 풀다보면 조합을 해야할 때가 있다 파이썬은 이터툴스가 있어 사용하면 되지만 역시 한번 만들어 보는게 재미있다.

알고리즘을 순열알고리즘과 데이터를 섞어서 만들지 말고 일단 순열리스트를 만들고 그 리스트를 이용해 for문으로 데이트를 순회하는게 더 나은것 같다. 문제를 나누어 푸는게 좋다.

알고리즘은 간단하다. 순열을 만든 숫자리스트가 있고 이걸 이용해 재귀를 부른다. 재귀는 자리수를 만족하면 순열을 iterarr에 저장하고 한칸 뒤로 빠진다. 여기서 기술은 다음줄이다.

permut( plist + [v], others[:i]+others[i+1:],n-1)

재귀는 Stack과 동일하다 따라서 복귀했을때는 전의 상황이 재현되어야 하는데 재귀함수를 부름 파라미터는 + 와 슬라이스를 이용해 원하는 파리미터를 만들어 주었지만 자기 자신의 데이터는 변형되지 않고 동일하다. 돌아왔을때 복구가 필요없다.

iterarr = []
def permut( plist, others ,n):
    if n== 0:
        iterarr.append(plist)
        return
    for i,v in enumerate(others):
        permut( plist + [v], others[:i]+others[i+1:],n-1)
    return
def main():
    nums = [ v for v in range(10)]
    permut( [],  nums,4)
    
    for v in iterarr:
        print(v)
    return
main()