네모장 | 네모장

순열, 중복순열, 조합, 중복조합

순열

서로 다른 n개의 원소 중에서 중복 없이 r개를 골라 순서대로 나열하는 것

nPr = n! / (n - r)!

// 순열
boolean[] isSelected = new boolean[N + 1];
int[] numbers = new numbers[N + 1];

public void perm(int cnt) {
  if (cnt == R) {
    System.out.println(Arrays.toString(numbers));
    return;
  }
  for (int i = 1; i <= N; i++) {
    if (isSelected[i]) continue;
    numbers[cnt] = i;
    isSelected[i] = true;
    perm(cnt + 1);
    isSelected[i] = false;
  }
}

중복 순열

서로 다른 n개의 원소 중에서 중복을 허용하여 r개를 골라 순서대로 나열하는 것

nΠr = n^r

// 중복 순열
int[] numbers = new int[N + 1];

public void perm2(int cnt) {
  if (cnt == R) {
    System.out.println(Arrays.toString(numbers));
    return;
  }
  for (int i = 1; i <= N; i++) {
    numbers[cnt] = i;
    perm2(cnt + 1);
  }
}

조합

서로 다른 n개의 원소 중에서 중복없이 r개를 선택하는 것

순서는 고려하지 않는다.

nCr = n! / ((n - r)! * r!)

// 조합
int[] numbers = new int[N + 1];

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

중복 조합

서로 다른 n개의 원소 중에서 중복을 허락하여 r개를 선택하는 것

순서는 고려하지 않는다.

nHr = (n+r-1)Cr

int[] numbers = new int[N + 1];

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