[Algorithm] 순열, 중복 순열, 조합, 중복 조합

재귀를 이용한 백트래킹을 사용할 것.

n이 10 근처일때 사용하기(n이 너무 크면 시간 초과 발생!)

 

순열

순서를 고려하면서 서로 다른 n개에서 중복 없이 r개를 일렬로 나열하는 수

시간 복잡도 O(n!)

 

static void permutation(int dept, int n, int r){
	//순열이 완성된 경우
    if(dept == r){
    	System.out.println(Arrays.toString(output));
        return;
    }
    
    for(int i = 0; i<n; i++){
    	if(!visited[i]){
        	visited[i] = true;
            output[depth] = arr[i]; //현재 depth를 인덱스로 사용
            permutation(depth+1, n, r);
            visited[i] = false;  //다음 순열을 뽑기 위해 방문 처리 제거
            }
        }
    }

 

 

중복 순열

 

순서를 고려하면서 서로 다른 n개에서 중복으로 r개를 일렬로 나열하는 수

시간 복잡도

O(n^r) 

방문처리 X

 

static void repeatPermutation(int depth, int n, int r){
	//순열이 완성된 경우
    
    if(depth == r){
    	System.out.println(Arrays.toString(output));
        return;
     }
     
     
     //0부터 n까지 반복
     for(int i = 0; i<n; i++){
     	output[depth] = arr[i];
        repeatPermutation(depth+1,n,r);
        }
     }
  }

 

 

조합

순서를 고려하지 않고 n개에서 중복 없이 r개를 일렬로 나열하는 수

 

시간 복잡도 

O(2^n)

 

static void combination(int start, int depth, int n, int r){
	//조합이 완성된 경우
    if(depth == r){
    	System.out.println(Arrays.toString(output));
        return;
      }
      
      for(int i = start, i<n; i++){
      		output[depth] = arr[i];
            combination(i+1, depth+1, n, r);
            }
        }
   }

 

중복 조합

순서를 고려하지 않고 n개에서 중복으로 r개를 일렬로 나열하는 수

조합과 다르게 i+1이 아닌 i를 인자로 전달

static void combination(int start, int depth, int n, int r){
	//조합이 완성된 경우
    if(depth == r){
    	System.out.println(Arrays.toString(output));
        return;
      }
      
      for(int i = start, i<n; i++){
      		output[depth] = arr[i];
            combination(i, depth+1, n, r);
            }
        }
   }