jasonbla

[Algorithm] 순열 조합 본문

Programming

[Algorithm] 순열 조합

jason jason hwang 2016.10.23 02:46

본 글은 아래 블로그에서 참고하여 재정리한 글임을 먼저 밝힙니다.


고락고락 닷컴님의 순열(Permutation) 알고리즘

http://www.eandbsoftware.org/print-all-permutations-of-a-given-string/


알고리즘 문제를 풀다보면 다음과 같이 N개의 숫자 중 R개의 숫자를 골라서 만들어낼 수 있는 모든 조합을 구해야 하는 경우가 종종 있다.


ㅁ 4개의 숫자


1, 2, 3, 4

ㅁ 4개의 숫자 중 4가지 숫자로 만들어낼 수 있는 조합 (중복을 허용하지 않음) 


1, 2, 3, 4

1, 2, 4, 3

1, 3, 2, 4

1, 3, 4, 2

...


출처 : http://www.eandbsoftware.org/print-all-permutations-of-a-given-string/



중요한 포인트는, 각 노드에서 스위칭된 원소는 Fixed되어 버리고, Fixed된 원소를 제외한 나머지 원소에 대해 다시 스위칭을 하면서 자식 노드를 뻗어 내려간다는 것이다. (더 이상 스위칭할 원소가 없을때까지)


C++ 버전으로 재작성한 코드


C++ STL 활용

0 Comments
댓글쓰기 폼