순열나열 (Permutation)

1부터 n까지

혹은

n부터 1까지 

나열된 일련의 숫자를

오름차순

혹은

내림차순으로 나열하는 알고리즘이다.

ex)

123

132

213

231

312

321

재귀함수는 사용하지 않았으므로

숫자가 크면 시간은 오래걸리겠지만

스택 오버플로우는 걱정 안해도 될거 같다.

c++로 작성

#include <iostream>
#include <vector>
#include <algorithm> // for swap()
using namespace std;

class Permutation
{
private:
	int n; // 원소 개수
	vector<int> v;
	bool isAsc; // true : 오름차순으로 진행?

public:
	void assign()
	{
		int i;
		v.reserve(n);
		for (i = 0; i < n; ++i)
		{
			if (isAsc)
				v.push_back(i + 1);
			else
				v.push_back(n - i);
		}
	}

	Permutation(bool asc)
	{
		cout << "Input n : ";
		cin >> n;
		isAsc = asc;
		assign();
	}

	Permutation(int num, bool asc = true)
	{
		n = num;
		isAsc = asc;
		assign();
	}

	// 오름차순일때 사용
	bool next()
	{
		if (isAsc)
		{
			int k, j, r, s;
			k = n - 2;
			while (v[k] > v[k + 1])
			{
				if (k == 0)
					return false;
				k--;
			}

			j = n - 1;

			while (v[k] > v[j]) j--;
			swap(v[j], v[k]);

			r = n - 1;
			s = k + 1;

			while (r > s)
				swap(v[r--], v[s++]);
			return true;
		}
		return false;
	}

	// 내림차순 일때 사용
	bool previous()
	{
		if (!isAsc)
		{
			int k, j, r, s;
			k = n - 2;
			while (v[k] < v[k + 1])
			{
				if (k == 0)
					return false;
				k--;
			}
			j = n - 1;

			while (v[k] < v[j]) j--;
			swap(v[j], v[k]);

			r = n - 1;
			s = k + 1;

			while (r > s)
				swap(v[r--], v[s++]);
			return true;
		}
		return false;
	}

	// 출력
	void print()
	{
		int i;
		for (i = 0; i < n; ++i)
			cout << v[i];
		cout << endl;
	}

	void fullprint()
	{
		if (isAsc)
		{
			for (; next(); )
				print();
		}
		else
			for (; previous(); )
				print();

	}
};

int main()
{
	Permutation p1(4), p2(5, false);

	cout << "----- 오름차순 순열 -----" << endl;
	p1.print();
	for (; p1.next(); )
		p1.print();

	cout << endl << "----- 내름차순 순열 -----" << endl;
	p2.fullprint();
	return 0;
}