[알고리즘]순열과 조합

순열(Permutation)

서로 다른 n개에서 r개를 뽑아 정렬하는 경우의 수

순열에서 가장 중요한 것은 '정렬'

순열에서 [1,2]와 [2,1]는 순서가 다르기 때문에 다른것으로 봄

자바 구현코드

public class Main{
	public static void permutation(int [] arr, int [] out, boolean [] visit, int depth, int r){
    	if(depth == r){
        	for(int i : out) System.out.print(i+" ");
            System.out.println();
            return;
        }
        for(int i = 0; i<arr.length; i++){
          if(!visit[i]){
              visit[i] = true;
              out[depth] = arr[i];
              permutation(arr, out, visit, depth+1, r);
              visit[i] = false;
          }
        }
    }
	public static void main(String[] args){
    	// 여기 이 숫자 중에서 
    	int [] arr = {1, 2, 3};
        // 두개씩 뽑을게요
        int r = 2;
        // 뽑은 숫자 들어갈 공간 
        int [] out = new int [r];
        // 숫자 방문했는지 체크 
        boolean [] visit = new boolean[arr.length];
        permutation(arr, out, visit, 0, r);
    }
}

• 인덱스 상 뒤의 원소가 앞에오는 경우도 카운트해야함
  그래서 반복문을 0부터 시작
• 순서대로 방문 원소를 저장해야하기 때문에 out을 사용
• 1 1 이렇게 중복해 선택하면 안되니깐 visit를 이용해 이미 선택한 원소 다시 선택안하도록 함

---

중복 순열

서로 다른 n개에서 중복이 가능하게 r개를 뽑아서 정렬하는 경우의 술

순서가 있게 뽑는 것은 동일한데, 같은 원소를 중복해서 뽑을 수 있다는 차이가 있음

[1,1]처럼 중복 되는 것도 허용

자바 구현코드

public class Main{
	public static void permutation(int [] arr, int [] out, int depth, int r){
    	if(depth == r){
        	for(int i : out) System.out.print(i+" ");
            System.out.println();
            return;
        }
        for(int i = 0; i < arr.length; i++){
        	out[depth] = arr[i];
            permutation(arr, out, depth+1, r);
        }
    }
  public static void main(String [] args){
      int [] arr = {1, 2, 3};
      int r = 2;
      int [] out = new int [r];
      permutation(arr, out, 0, r);
  }
}

이전 코드에서 visit부분만 제거하면 된다

---

조합(Combination)

서로 다른 n개에서 순서 없이 r개를 뽑는 경우의 수

순서와 상관 없다는 말은 순열과 달리 [1,2]와[2,1]을 같은 것으로 본다는 말

자바 구현코드

public class Main{
	public static void combination(int [] arr, boolean[] visit, int start, int depth, int r){
    	if(depth == r){
        	for(int i = 0; i<arr.length; i++){
            	if(visit[i]) System.out.print(arr[i]);
            }
            System.out.println();
            return;
        }
        for(int i = start; i<arr.length; i++){
        	if(!visit[i]){
            	visit[i] = true;
                combination(arr, visit, i+1, depth+1, r);
                visit[i] = false;
            }
        }
    }
    
    public static void main(String[] args){
    	int [] arr = {1, 2, 3};
        boolean [] visit = new boolean[arr.length];
        int r = 2;
        
        combination(arr, visit, 0, 0, r);
    }
}

---

중복 조합

서로 다른 n개에서 순서 없이, 중복이 가능하게 r개를 뽑는 경우의 수

순서 없이 뽑는 조합과 동일하지만, 이미 뽑은 것을 또 뽑을 수 있음
즉 중복이 가능하다는 차이가 있음
[1,1]나 [2,2] 처럼 중복 수도 조합으로 뽑음

자바 구현코드

public static void combination(int[] arr, int[] out, int start, int depth, int r){
        if(depth == r){
            for(int i : out) System.out.print(i+" ");
            System.out.println();
            return;
        }
        for(int i=start; i<arr.length; i++){
            out[depth] = arr[i];
            combination(arr, out, i, depth+1, r);
        }
    }

    public static void main(String[] args){
        int[] arr = {1, 2, 3};
        int r = 2;
        int[] out = new int[r];
        combination(arr, out, 0, 0, r);
    }
}