[C++] 순열 만들기

순열을 만드는 아이디어는 다음과 같다

N	Permutation
1	a
2	ba   ab
3	cba   bca   bac   cab  acb   abc
...	...

표를 자세히 보면 

N이 1에서 2가 될 때,

a를 사이에 두고 b가 앞 뒤쪽으로 하나씩 생겨 2개의 순열이 생겨났다.

N이 2에서 3이 될 때,

O b O a O 의 O에 c가 하나씩 생겨 3개의 순열이,

O a O b O 의 O에 c가 하나씩 생겨 3개의 순열이 

생겨 총 6개의 순열이 생겼다.

여기서 ba, ab는 N=1 -> N=2로 될 때 만들어 진 것.

따라서 Recursive Call 방법으로 순열을 만들 수 있을 것이다.

(N! 이면, '(N-1)!은 내가 만드니 N만 니가 처리해줘' 라는 방식)

코드를 짜봤지만, 그 다지 깔끔한 코드가 아닌 듯 하다... 

	
#include 
#include 

using namespace std;

class PermutaString{

public:
	PermutaString(){}
	PermutaString(int L){
		numOfL = L;
		
	};

	~PermutaString(){}

	void makePermutation(){
		vector> v;
		makePermutation(v, 1);
	}

	void makePermutation(vector> v, int cnt){
		if (cnt > numOfL){
			permuVector = v;
			return;
		}

		//cnt는 현재 배열에 들어간 원소개수
		vector> tempPermuVector;

		if (cnt==1){
			vector v1;
			v1.push_back(1);
			tempPermuVector.push_back(v1);
		}

		else{
			vector v1;
			v1.resize(cnt);
			for (int i = 0; i < v.size(); i++){
				for (int j = 0; j < cnt; j++){
					v1[j] = cnt;
					int c = 0;
					for (int k = 0; k < cnt; k++){
						if (k != j){
							v1[k] = v[i][c];
							c++;
						}
					}
					tempPermuVector.push_back(v1);
				}
			}
		}

		cnt++;
		makePermutation(tempPermuVector, cnt);
	}


	void printPermutation(){
		for (int i = 0; i < permuVector.size(); i++){
			for (int j = 0; j < numOfL; j++){
				cout << permuVector[i][j] << " ";
			}
			cout << endl;
		}
	}


private:
	vector> permuVector;
	int numOfL;
};



int main(){

	PermutaString p(3);

	p.makePermutation();
	p.printPermutation();

	return 0;
}

(코드 마지막에 <~~> 처리된 부분을 HTML 태그로 받아들어서 출력되는 듯...)