Python에서 리스트 변수는 실제로는 메모리 어딘가에 있는 리스트를 가리키는 화살표(reference)입니다. 따라서 P.append(S)를 한 뒤 S에 append() 및 pop() 등으로 변경을 가하면 P에 들어간 원소가 같이 바뀝니다.

>>> s = []
>>> p = [s]
>>> s.append(1)
>>> p
[[1]]

이렇게 동작하지 않도록 하려면 S.copy() 등의 방법으로 복사본을 만들어 넣어야 합니다.