자바 java 조합 중복조합 순열 중복순열

오래 안 보면 자꾸 헷갈려서 그냥 정리해놓는다..

 

조합

private static void combination(int cnt, int start) {	
  //cnt: 현재까지 뽑은 조합의 개수, start: 조합에 시도할 원소 시작점
  if(cnt == R) {
    System.out.println(Arrays.toString(numbers));
    return;
  }
  // 앞선 수의 선택 다음부터 시도
  for(int i = start; i < N; i++) {
    numbers[cnt] = input[i];
    combination(cnt+1, i+1);
  }
}

 

중복 조합

private static void combination(int cnt, int start) {	
  if(cnt == R) {
    System.out.println(Arrays.toString(numbers));
    return;
  }
  for(int i = start; i < N; i++) {
    numbers[cnt] = input[i];
    combination(cnt+1, i);
  }
}

나왔던 수가 또 나와도 되므로 시작점을 +1 하지 않고 바로 재귀 호출

 

순열

static boolean[] selected;
private static void permu(int cnt) {	
  if(cnt == R) {
    System.out.println(Arrays.toString(numbers));
    return;
  }
  for(int i = 0; i < N; i++) {
    if(selected[i]) continue;
    selected[i] = true;
    numbers[cnt] = input[i];
    permu(cnt+1);
    selected[i] = false;
  }
}

 

중복 순열

private static void permu(int cnt) {
  if(cnt == R) {
    System.out.println(Arrays.toString(numbers));
    return;
  }
  for(int i = 0; i < N; i++) {
    numbers[cnt] = input[i];
    permu(cnt+1);
  }
}