[알고리즘] 순열(Permutation)

순열(Permutation)

개념

- 서로 다른 것들(n개) 중에서 몇 개(r개)를 뽑아 순서있게 한 줄로 나열

- nPr

- 순서가 의미가 있으면 순열 / 순서가 의미가 없으면 조합

- n번째 수를 뽑을 때, n-1번 비교를 해야 사용 가능한 수를 판단할 수 있음(최악의 경우)

 

구현

- 몇 번째 자리의 수를 뽑는지 달라지고 있기 때문에 해당 부분이 가변적임 -> 매개변수로 받아옴(cnt)

- input[] : 서로 다른 숫자(n개)를 저장하기 위한 Integer 배열

- numbers[] : 뽑은 숫자(r개)를 저장하기 위한 Integer 배열

- isSelected[] : 중복 체크를 위한 Boolean 배열

- 해당 자리를 선택하고 뒤를 다 탐색하고 다시 돌아오면 다른 수를 또 탐색해야하므로 그 자리를 다시 false로 해주어야 함

 

코드

public static void permutation(int cnt){
        if(cnt == R){
            System.out.println(Arrays.toString(numbers));
            return;
        }

        for(int i = 0; i<N; i++){
            if(isSelected[i]) continue;

            numbers[cnt] = input[i];
            isSelected[i] = true;
            permutation(cnt+1);
            isSelected[i] = false;
        }
}