[코딩테스트] 자바 Java, 순열과 조합: 순열

순열과 조합

순열 Permutation : nPr

• 서로 다른 n개 중의 r개를 뽑을 때, 순서를 포함한 경우의 수
• 중복 가능한 n개 중 r개를 뽑으면, 중복 순열

 

예시

{A, B} 중 2개를 뽑는 순열 : {A, B,}, {B, A}

 

조합 Combination : nCr

• 서로 다른 n개 중의 r개를 뽑을 때, 순서의 상관없이 뽑는 경우의 수
• 중복 가능한 n개 중 r개를 뽑으면, 중복 조합

 

예시

{A, B} 중 2개를 뽀는 조합 : {A, B}

---

순열의 개수

nPk =  n! / (n-k)!

 

순열의 개수 구하기 예시(JAVA)

public class NumberOfPermutation {
    public static void main(String[] args) {
        int n = 3, r = 3;

        System.out.println("순열(nPr)의 개수: " + getNumberOfPermutation(n, r));
    }

    public static int getNumberOfPermutation(int n, int r) {
        return factorial(n) / factorial(n-r) ;
    }

    public static int factorial(int i) {
        if(i <= 1) return 1;
        else return i * factorial(i-1);
    }
}

결과 출력

순열(nPr)의 개수: 6

 

순열 사용 예시(JAVA)

import java.util.HashSet;
import java.util.Iterator;

public class Permutation {
    public static void main(String[] args) {
        String str = "123";

        permutation("", str);
    }

    public static void permutation(String s1, String s2) {
        if(!s1.equals("")) {
            System.out.println(Integer.valueOf(s1));
        }

        for(int i=0; i<s2.length(); i++) {
            permutation(s1+s2.charAt(i), s2.substring(0, i)+s2.substring(i+1));
        }
    }
}

결과 출력

1
12
123
13
132
2
21
213
23
231
3
31
312
32
321