순열 알고리즘

공부한 사이트

https://www.youtube.com/watchv=MjW10t9ppok&list=PL52K_8WQO5oUuH06MLOrah4h05TZ4n38l&index=8&t=950s

 

 

3!은 3개의 의자에서

첫번째 의자에 앉을 수 있는 경우 3 

두번째 의자에 앉을 수 있는 경우 2 ( 이미 첫번째 의자에 앉았으므로 )

세번째 의자에 앉을 수 있는 경우 1 (나머지)

3! = 3*2*1이다.

 

<코드 설명> 

첫번째 올 원소를 지정 + 나머지 원소들의 순열을 구한다.

 

집합 S={ a, b, c ,d}의 순열을 상태공간트리로 나타냈을 때 제일 마지막 노드를 출력하는 것.

 

- 기저 케이스: k번째 자리까지 다 지정을 한 상황, data배열을 출력한다.

 

- k번째 자리에 원소를 지정한다. = swap(data, k, i); 

  여기에서 i는 지정될 원소의 인덱스, k는 몇번째 자리인지를 의미. 

  k ~ n-1인덱스의 원소가 다 들어갈 수 있기 때문에 for문을 사용한다. 

 

- k자리에 원소가 결정되었으면 다음 자리를 지정하기 위해 k+1를 매개변수로 재귀한다. printPerm(k+1)

 

- swap()으로 바뀐 순서를 원위치 시킨다. = swap(data, k, i)

* 주의: recursion 호출 전 후로 공용으로 사용하는 데이터는 순서가 변경되지 않고 유지되도록 해야한다. 

   왜? data의 인덱스를 기준으로 자리배정을 하는데 원소의 위치가 바뀌면, 인덱스가 변경되어도 똑같은 원소를 가리켜 k자리에 똑같은 원소가 여러번 올 수 있음

   따라서 반드시 바꾼 순서를 원상복귀 시켜야 함.

 

package repeat;
import java.util.Arrays;

public class permutation {
	char data[] = {'a','b','c','d'};
	int n=4;
	
	void printPerm(int k) {
		if(k==n) {
			System.out.println(Arrays.toString(data));
			return;
		}
		for(int i=k; i<n; i++) {
			swap(data, k, i);	//swap data[k] and data[i]
			printPerm(k+1);
			swap(data, k, i);	//recursion전후로 데이터의 순서를 유지하기 위함.
		}
	}
	
	void swap(char array[], int k, int i) {
		char tmp = array[k];
		array[k] = array[i];
		array[i] = tmp;
	}
	
	public static void main(String[] args) {
		permutation p = new permutation();
		p.printPerm(0);
	}

}