순열, 조합, 중복순열, 중복조합을 만드는 방법

 

---

순열, 조합, 중복순열, 중복조합을 만들 수 있는 여러가지 방법을 설명하겠다

마지막에는 한가지 방법으로 순열, 조합, 중복순열, 중복조합을 모두 만들 수 있는 방법을 알려주겠다

 

---

사용할 배열에는 1 2 3이 저장되어 있는 상태이다

이 배열을 이용하여 3개 중에서 2개를 뽑는 순열, 조합, 중복순열, 중복조합을 생성해보겠다

 

---

순열을 만드는 방법

1. 반복을 이용한 순열

가장 쉽게 만들 수 있는 순열이다

2~3개를 뽑는 경우에는 간단하게 사용할 수 있지만 뽑는 수가 많아지면 코드가 더러워(?)진다

static int[] arr = {1, 2, 3};

public static void per() {
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j <3; j++) {
            if (j != i) {
                System.out.println(arr[i] + " " + arr[j]);
            }
        }
    }
}

public static void main(String[] args) {
	per();
}

결과

 

3개를 뽑고 싶은 경우 for문을 하나 더 추가하면 된다

public static void per() {
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j <3; j++) {
            if (j != i) {
                for (int k = 0; k < 3; k++) {
                    if (k != i && k != j) {
                        System.out.println(arr[i] + " " + arr[j] + " " + arr[k]);
                    }
                }
            }
        }
    }
}

결과

 

2. 배열의 swap을 이용한 순열1 (임시 배열 사용)

swap을 이용하여 배열의 끝 인덱스를 기준으로 앞의 인덱스와 위치를 차례대로 바꿔가며

배열의 끝에서 부터 R개 만큼 tr배열에 담는 방법이다

값을 뽑고 나면 다시 배열을 원상복구 해준다

함수를 재귀 호출해 줄때 마다 뽑아야 하는 개수 r을 줄여가며

r==0이 되면 뽑은 원소가 들어있는 tr배열을 이용하여 원하는 작업을 해주면 된다

static int[] arr = {1, 2, 3};
static int N = 3;	// N개 중에서 R개를 뽑는다
static int R = 2;
static int[] tr;	//뽑은 원소를 저장할 임시 배열

public static void swap(int a, int b) {	// 배열의 값을 swap하는 함수
    int temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}

public static void per(int n, int r) {
    if (r == 0) {
        for (int i = 0; i < R; i++) {
            System.out.print(tr[i] + " ");
        }
        System.out.println();
    } else {
        for (int i = n - 1; i >= 0; i--) {
            swap(i, n - 1);
            tr[r - 1] = arr[n - 1];
            per(n - 1, r - 1);
            swap(i, n - 1);
        }
    }
}

public static void main(String[] args) {
	tr = new int[R];
	per(N, R);
}

결과

 

3. 배열의 swap을 이용한 순열2 (깊이 사용)

위의 방법과 동일하게 swap을 이용하지만 차이점이 있다

이번 방법은 뽑은 원소를 담을 임시배열 tr이 없다

임시 배열 대신 직접 자신의 배열 안에서 swap을 이용하여 순서를 바꾼다

깊이 k를 이용하여 k==R이 되어 원하는 개수만큼 뽑았을 경우

배열의 앞에서 부터 R개 만큼 원하는 작업을 해주면 된다

static int[] arr = {1, 2, 3};
static int N = 3;	// N개 중에서 R개를 뽑는다
static int R = 2;

public static void swap(int a, int b) {	// 배열의 값을 swap하는 함수
    int temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}

public static void per(int k) {
    if (k == R) {	
        for (int i = 0; i < R; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    } else {
        for (int i = k; i < N; i++) {
            swap(k, i);
            per(k + 1);
            swap(k, i);
        }
    }
}

public static void main(String[] args) {
	per(0);
}

결과

 

---

조합을 만드는 방법

공식을 이용한 재귀

조합에는 다음과 같은 공식이 있다

위의 공식을 그대로 코드에 적용시키면 된다

배열의 뒤에서부터 값을 뽑고 배열의 최대 인덱스를 하나씩 줄여가면서 재귀 호출을 해준다

다만 com(n - 1, r)이 계속 호출되다보면 r이 배열의 최대 인덱스 보다 커질 수 있으므로

이 경우에는 조건을 걸어 if (r > n)  함수를 종료시킨다

static int[] arr = {1, 2, 3};
static int N = 3;	// N개 중에서 R개를 뽑는다
static int R = 2;
static int[] tr;	//뽑은 원소를 저장할 임시 배열

public static void com(int n, int r) {
    if (r == 0) {
        for (int i = 0; i < R; i++) {
            System.out.print(tr[i] + " ");
        }
        System.out.println();
    } else if (r > n) {
        return;
    } else {
        tr[r - 1] = arr[n - 1];
        com(n - 1, r - 1);
        com(n - 1, r);
    }
}

public static void main(String[] args) {
	tr = new int[R];
	com(N, R);
}

결과

 

---

중복 순열을 만드는 방법

배열의 swap을 이용한 중복 순열

순열을 생성할 때 사용했던 swap방법에서 토씨 하나만 바꾸면 중복 순열을 만들 수 있다

재귀 호출을 할 때 인덱스 제한을 하지 않으면 된다 n-1대신 n을 그대로 넘겨주면 된다

static int[] arr = {1, 2, 3};
static int N = 3;	// N개 중에서 R개를 뽑는다
static int R = 2;
static int[] tr;	//뽑은 원소를 저장할 임시 배열

public static void swap(int a, int b) {	// 배열의 값을 swap하는 함수
    int temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}

public static void pi(int n, int r) {
    if (r == 0) {
        for (int i = 0; i < R; i++) {
            System.out.print(tr[i] + " ");
        }
        System.out.println();
    } else {
        for (int i = N - 1; i >= 0; i--) {
            swap(i, n - 1);
            tr[r - 1] = arr[n - 1];
            pi(n, r - 1);
            swap(i, n - 1);
        }
    }
}

public static void main(String[] args) {
	tr = new int[R];
	pi(N, R);
}

결과

 

---

중복 조합을 만드는 방법

공식을 이용한 재귀

조합처럼 중복 조합에도 공식이 있다

이를 그대로 코드로 구현하면 된다

예외가 발생하는 경우만 잘 처리해주면 된다

h(n - 1, r)에 의해 함수가 계속 호출되므로 n==0이 되는 경우 함수를 종료시킨다

static int[] arr = {1, 2, 3};
static int N = 3;	// N개 중에서 R개를 뽑는다
static int R = 2;
static int[] tr;	//뽑은 원소를 저장할 임시 배열

public static void h(int n, int r) {
    if (r == 0) {
        for (int i = 0; i < R; i++) {
            System.out.print(tr[i] + " ");
        }
        System.out.println();
    } else if (n == 0) {
        return;
    } else {
        tr[r - 1] = arr[n - 1];
        h(n, r - 1);
        h(n - 1, r);
    }
}

public static void main(String[] args) {
	tr = new int[R];
	h(N, R);
}

결과

 

---

필자가 주로 사용하는 방법

필자는 주로 깊이 k를 이용하여 순열, 조합, 중복순열, 중복조합을 생성한다
깊이를 이용한 순열을 생성하는 법만 잘 기억하면 나머지는 쉽게 만들 수 있다

 

순열 - visited를 사용한 순열

위에서 설명한 순열을 생성하는 방법에는 swap을 사용해야한다는 귀찮음이 있었다

swap대신 방문 표시를 이용한 visited를 이용하면 훨씬 간편하게 순열을 생성할 수 있다

먼저 깊이 k를 이용하여 R개를 뽑을 때 까지(k==R) 재귀 호출을 한다

함수를 호출할 때마다 visited를 이용하여 이미 뽑았는지 안뽑았는지 확인을 한 후

뽑지 않은 원소인 경우, 임시 배열에 담고 visited에 뽑았다고 표시를 한다

static int[] arr = {1, 2, 3};
static int N = 3;	// N개 중에서 R개를 뽑는다
static int R = 2;
static int[] tr;	//뽑은 원소를 저장할 임시 배열
static boolean[] visited;	// 뽑았는지 안뽑았는지 체크할 배열

public static void per(int k) {
    if (k == R) {
        for (int i = 0; i < R; i++) {
            System.out.print(tr[i] + " ");
        }
        System.out.println();
    } else {
        for (int i = 0; i < N; i++) {
            if (!visited[i]) {
                visited[i] = true;
                tr[k] = arr[i];
                per(k + 1);
                visited[i] = false;
            }
        }
    }
}

public static void main(String[] args) {
	tr = new int[R];
	visited = new boolean[N];
	per(0);
}

결과

 

---

중복 순열

정말 간단하다

위의 순열을 생성한 방법에서

뽑았는지 안뽑았는지 표시해주는 visited배열만 제거해주면 중복 순열을 만들 수 있다

static int[] arr = {1, 2, 3};
static int N = 3;	// N개 중에서 R개를 뽑는다
static int R = 2;
static int[] tr;	//뽑은 원소를 저장할 임시 배열

public static void pi(int k) {
    if (k == R) {
        for (int i = 0; i < R; i++) {
            System.out.print(tr[i] + " ");
        }
        System.out.println();
    } else {
        for (int i = 0; i < N; i++) {
            tr[k] = arr[i];
            pi(k + 1);
        }
    }
}

public static void main(String[] args) {
	tr = new int[R];
	pi(0);
}

결과

 

---

조합 - 시작 인덱스를 사용한 조합

순열을 생성하는 방법에서 차이점 2개만 기억하면 된다

뽑았는지 안뽑았는지 표시해주는 visited배열이 없고

함수를 호출할 때 어디서 뽑아야 할지 정해주는 s변수가 추가되었다

순열과 마찬가지로 깊이 k를 이용하여 R개를 뽑을 때 까지(k==R) 재귀 호출을 한다

조합은 순서가 중요하지 않으므로 이미 앞에서 뽑은 경우

해당 인덱스의 뒤에 있는 원소만 뽑으면 된다

재귀 호출을 할 때 현재 뽑은 원소의 인덱스에 +1을 하여 재귀호출을 해주면 된다

static int[] arr = {1, 2, 3};
static int N = 3;	// N개 중에서 R개를 뽑는다
static int R = 2;
static int[] tr;	//뽑은 원소를 저장할 임시 배열

public static void com(int k, int s) {
    if (k == R) {
        for (int i = 0; i < R; i++) {
            System.out.print(tr[i] + " ");
        }
        System.out.println();
    } else {
        for (int i = s; i <= N - R + k; i++) {
            tr[k] = arr[i];
            com(k + 1, i + 1);
        }
    }
}

public static void main(String[] args) {
	tr = new int[R];
	com(0, 0);
}

결과

 

---

중복 조합 - 시작 인덱스를 사용한 중복 조합

위의 조합을 만드는 방법만 기억한다면 쉽게 만들 수 있다

조합의 경우 함수를 재귀 호출할 때 시작 인덱스를 현재 인덱스+1로 넘겨주었지만

중복 조합은 함수를 재귀 호출할 때 시작 인덱스를 현재 인덱스로 넘겨주면 된다

static int[] arr = {1, 2, 3};
static int N = 3;	// N개 중에서 R개를 뽑는다
static int R = 2;
static int[] tr;	//뽑은 원소를 저장할 임시 배열

public static void h(int k, int s) {
    if (k == R) {
        for (int i = 0; i < R; i++) {
            System.out.print(tr[i] + " ");
        }
        System.out.println();
    } else {
        for (int i = s; i < N; i++) {
            tr[k] = arr[i];
            h(k + 1, i);
        }
    }
}

public static void main(String[] args) {
	tr = new int[R];
	h(0, 0);
}

결과

 

---

정리

순열을 생성하는 방법만 제대로 기억하면

나머지는 쉽게 생각할 수 있다

 

깊이와 임시배열을 이용하는 점은 모두 동일하다

서로의 차이점만 잘 기억하자

순열을 생성할 때만 visited를 사용하는 것을 기억하고

조합, 중복 조합을 생성할 때는 시작 인덱스가 필요하다는 것을 기억하자

 

순열 - visited 이용

중복 순열 - x

조합 - 시작인덱스 이용

중복 조합 - 시작인덱스 이용