[Java] 순열(permutation)

• 순열과 조합의 차이

  뽑힌 자리 (순서의 의미 0 )→ 순열
  뽑힌 자리 (순서의 의미 X )→ 조합 

💡 순열

nPr : 여기서 r은 루프를 구성하는 개수가 된다. 그러나, r의 수가 미정이라면 재귀로 구현해야 한다.

재귀 결정 요인: 달라지는 수가 무엇인가? 뽑힌 수가 저장될 자리, 뽑히는 순서 등이 와야한다!!

nPn

// 1,2,3을 포함하는 순열을 생성하는 재귀함수 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class PermutationTest1 {

    static int N;
    static int totalCnt;
    static int[] arr;
    static boolean[] isSelected;

    // nPn: 1부터 n까지의 수 중 n 개를 모두 뽑아서 순서있게 나열함
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        totalCnt = 0;

        arr = new int[N];
        isSelected = new boolean[N + 1]; // 0이 아닌 1부터 시작

        permutation(0);
        System.out.println("총 경우의 수 :" + totalCnt);
    }

/*****  재귀 함수 구현   *****/
    private static void permutation(int cnt) {

        if (cnt == N) {
            totalCnt++;
            System.out.println(Arrays.toString(arr));
            return;
        }

        // 가능한 모든 수에 대해서 탐색
        for (int i = 1; i <= N; i++) {

            // 시도되는 수가 선택되었는가?
            if (isSelected[i])// true -> 사용중인 수
                continue;
            // 사용되지 않은 수
            arr[cnt] = i;
            isSelected[i] = true;// 그 수가 사용중

            // 다음 수 뽑으러
            permutation(cnt + 1);
            // 사용 되었던 수를 다시 되돌림
            isSelected[i] = false;
        }

    }
}

nPr

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class PermutationTest2 {

    static int N, R;
    static int totalCnt;
    static int[] arr, input;
    static boolean[] isSelected;

    // nPr: n까지의 수 중 r개를 모두 뽑아서 순서있게 나열함(1<=r<=n)

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        R = Integer.parseInt(st.nextToken());

        totalCnt = 0;
        input = new int[N];
        arr = new int[R];
        isSelected = new boolean[N];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            input[i] = Integer.parseInt(st.nextToken());

        }

        permutation(0);
        System.out.println("총 경우의 수 :" + totalCnt);
    }

    private static void permutation(int cnt) {

        if (cnt == R) {
            totalCnt++;
            System.out.println(Arrays.toString(arr));
            return;
        }

        // 가능한 모든 수에 대해서 탐색 ->(input 배열의 모든 수를 시도해야함 )
        for (int i = 0; i < N; i++) {

            // 시도되는 수가 선택되었는가?
            if (isSelected[i])// true -> 사용중인 수
                continue;
            // 사용되지 않은 수
            arr[cnt] = input[i];
            isSelected[i] = true;// 그 수가 사용중

            // 다음 수 뽑으러
            permutation(cnt + 1);
            // 사용 되었던 수를 다시 되돌림
            isSelected[i] = false;
        }

    }
}