[알고리즘] 순열/조합

🚀순열/조합에 대해 잘 정리해둔 블로그
순열 / 조합
아래 코드도 이를 참고하여 짰다.

💻 순열 nPr

순열은 순서가 의미 있음
따라서, [1, 2, 3]과 [1, 3, 2]는 다르게 인식한다.

class Solution {
    int n = 3;
    int r = 3;
    int[] numbers = {1, 2, 3};
    boolean[] visited = new boolean[n+1];
    int[] output = new int[n+1];
    
    public void permutation(int n, int r, int[] output, int cnt){
        if(cnt==r){
            print(output, r);
            return;
        }
        
        for(int i=0; i<n; i++){
            if(!visited[i]){
                visited[i] = true;
                output[cnt] = numbers[i];
                permutation(n, r, output, cnt+1);
                visited[i] = false;
            }
        }
    }
    
    public void print(int[] output, int r){
        for(int i=0; i<r; i++){
            System.out.print(output[i] + " ");
        }
        System.out.println();
    }
    
    public int solution(String numbers) {
        int answer = 0;
        
        permutation(n, r, output, 0);
        
        return answer;
    }
}

💻 중복순열

중복을 허용하기 때문에 방문여부를 체크할 필요 없음

class Solution {
    int n = 3;
    int r = 3;
    int[] numbers = {1, 2, 3};
    int[] output = new int[n+1];
    
    public void permutation(int n, int r, int[] output, int cnt){
        if(cnt==r){
            print(output, r);
            return;
        }
        
        for(int i=0; i<n; i++){
            output[cnt] = numbers[i];
            permutation(n, r, output, cnt+1);
        }
    }
    
    public void print(int[] output, int r){
        for(int i=0; i<r; i++){
            System.out.print(output[i] + " ");
        }
        System.out.println();
    }
    
    public int solution(String numbers) {
        int answer = 0;
        
        permutation(n, r, output, 0);
        
        return answer;
    }
}

💻 조합 nCr

조합은 순서가 의미 없음
따라서, [1, 2, 3]과 [1, 3, 2]는 같다고 판단한다.

class Solution {
    int n = 4;
    int r = 2;
    boolean[] visited = new boolean[n+1];
    int[] numbers = {1, 2, 3, 4};
    
    public void combination(int n, int r, int[] numbers, int idx){
        if(r==0){
            for(int i=0; i<visited.length; i++){
                //방문했다는 것은 해당 숫자를 뽑았다는 것
                if(visited[i]){
                    System.out.print(numbers[i] + " ");
                }
            }
            System.out.println();
            return;
        }
        
        if(idx == n)
            return;
        
        //선택했을 때
        visited[idx] = true;
        combination(n, r-1, numbers, idx+1);
        //선택하지 않았을 때
        visited[idx] = false;
        combination(n, r, numbers, idx+1);
    }
    
    public int solution(String numberss) {
        int answer = 0;
        
        combination(n, r, numbers, 0);
        
        return answer;
    }

}