전체 배열 알고리즘 및 구현

모든 배열 은 매우 많은 프로그램 에서 응용 되 고 자주 볼 수 없 는 알고리즘 이 며 일반적인 알고리즘 은 재 귀적 인 알고리즘 으로 이러한 알고리즘 은 아래 의 분석 방향 을 바탕 으로 한다.  n 개의 요 소 를 가 진 집합 (n > = 1) 을 지정 하여 이 집합 에서 요소 의 모든 가능 한 배열 을 출력 하도록 합 니 다.
        1. 순환 실현
        예 를 들 어 집합 이 {a, b, c} 이 라 고 가정 하면 이 집합 에서 요소 의 모든 배열 은 {(a, b, c), (a, c, b), (b, a, c), (b, c, a), (c, a, b)} 이 고 n 개의 요소 가 공동으로 n 을 가 진 것 이 분명 합 니 다!서로 다른 배열, 주어진 집합 이 {a, b, c, d} 이 라 고 가정 하면 다음 과 같은 간단 한 알고리즘 으로 모든 배열 을 만 들 수 있 습 니 다. 즉, 집합 (a, b, c, d) 의 모든 배열 은 다음 과 같은 배열 로 구성 되 어 있 습 니 다.
     (1) a 로 시작 하고 뒤에 (b, c, d) 의 배열 을 따른다.
    (2) b 로 시작 하여 (a, c, d) 의 배열 을 따른다.
    (3) c 로 시작 하여 (a, b, d) 의 배열 을 따른다.
    (4) d 로 시작 한 후에 (a, b, c) 의 배열 을 따 르 면 이것 은 분명히 재 귀 적 인 사고 이다. 그래서 우 리 는 다음 과 같은 실현 을 얻 었 다.

#include "iostream"

using namespace std;



void permutation(char* a,int k,int m)

{

	int i,j;

	if(k == m)

	{

		for(i=0;i<=m;i++)

			cout<<a[i];

		cout<<endl;

	}

	else

	{

		for(j=k;j<=m;j++)

		{

			swap(a[j],a[k]);

			permutation(a,k+1,m);

			swap(a[j],a[k]);

		}

	}

}

int main(void)

{

	char a[] = "abc";

	cout<<a<<"         ："<<endl;

	permutation(a,0,2);

	system("pause");

	return 0;

}

      2. STL 실현
        때때로 귀속 의 효율 때문에 우 리 는 이것 을 제외 한 다른 실현 을 고려 해 야 한다. 귀속 알고리즘 을 비 귀속 형식의 알고리즘 으로 전환 하 는 것 은 매우 어렵다. 이때 우 리 는 표준 템 플 릿 라 이브 러 리 가 이미 실현 한 알고리즘 을 잊 지 말 아야 한다. 이것 은 우 리 를 매우 가볍게 한다.STL 에는 함수 next 가 있 습 니 다.permutation () 의 역할 은 하나의 서열 에 대해 사전 에 따라 정렬 한 다음 배열 이 존재 한다 고 가정 하 는 것 입 니 다. 그러면 true 로 돌아 가 이 배열 을 만 듭 니 다. 그렇지 않 으 면 false 로 돌아 갑 니 다.전체 배열 을 만 들 기 위해 서 이 서열 이 질서 가 있다 면 sort 를 한 번 호출 하 는 것 입 니 다.아주 easy 를 실현 합 니 다. 코드 를 보 겠 습 니 다.

#include "iostream"

#include "algorithm"

using namespace std;



void permutation(char* str,int length)

{

	sort(str,str+length);

	do

	{

		for(int i=0;i<length;i++)

			cout<<str[i];

		cout<<endl;

	}while(next_permutation(str,str+length));



}

int main(void)

{

	char str[] = "acb";

	cout<<str<<"         ："<<endl;

	permutation(str,3);

	system("pause");

	return 0;

}

          3. 일정한 제약 조건 이 있 는 전체 배열
         대수 1, 2, 3, 4, 5 는 전체 정렬 을 실현 해 야 한다.4 는 3 의 왼쪽 에 있어 야 하고, 다른 숫자 는 임의로 해 야 한다. 
            사고방식: 먼저 위의 두 가지 방법 중 하 나 를 사용 하여 전체 배열 을 실현 한 다음 에 전체 배열 을 선별 하여 4 에서 3 왼쪽 의 배열 을 선별한다.

#include "iostream"

#include "algorithm"

using namespace std;



void permutation(int* a,int length)

{

	int i,flag;

	sort(a,a+length);

	do

	{

		for(i=0;i<length;i++)

		{

			if(a[i]==3)

				flag=1;

			else if(a[i]==4)             //  3 4   ，     ，flag  2

				flag=2;

		}

		if(flag==1)          //  4 3   ，     ，flag  1

		{

			for(i=0;i<length;i++)

				cout<<a[i];

			cout<<endl;

		}

	}while(next_permutation(a,a+length));



}

int main(void)

{

	int i,a[5];

	for(i=0;i<5;i++)

		a[i]=i+1;

	printf("%d    4 3         ：
",i);

	permutation(a,5);

	system("pause");

	return 0;

}