알고리즘

[java] 순열

벨포트조던 2016. 10. 21. 15:09
반응형

C++ 같은 경우에는 표준 라이브러리인 STL에 포함된 next_permutation()함수에서 모든 순열을 생성해준다.

가능한 순열의 수는 N!인데, N이 10을 넘어간다면 시간 안에 모든 순열을 생성하기 어려우므로 전체를 생성하는

방법 외에 다른 방법을 찾아본다.



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// n : 전체 원소의 개수
// picked : 지금까지 고른 원소의 개수
// isPick : 이전에 선택된 원소인지 저장하고있는 변수
// n개의 원소의 모든 순열을 구하는 방법
int n;
void permutation( ArrayList<Integer> picked, boolean isPick[] ){
    // 기저사례 : 모든 개수를 뽑아냈다.
    if( picked.size() == n ){
        System.out.println(picked);
        return ;
    }
     
    for(int next = 0; next < n; next++){
        if( isPick[next] )
            continue;
         
        picked.add(next);
        isPick[next] = true;
         
        permutation( new ArrayList<Integer>(picked), isPick );
         
        picked.remove(picked.size()-1);
        isPick[next] = false;
    }
}

출처 :프로그래밍 대회에서 배우는 알고리즘 문제해결 전략 / 구종만 지음






다른 참고자료 


http://gorakgarak.tistory.com/523


반응형
저작자표시