폭력 검색 테마 소결: 전체 배열 및 재 집합 배열 생 성 알고리즘

1 ~ n 의 전체 배열
(1) 사고: 재 귀 하 는 사상 에 따라 집합 S 에 1 ~ n 의 모든 요 소 를 초기 화 합 니 다.1 ~ n 의 집합 S 가 비어 있 으 면 출력 을 모두 배열 합 니 다.그렇지 않 으 면 어 릴 때 부터 모든 요소 i 를 차례대로 고려 하여 A 의 끝 에 i 를 추가 한 후 집합 S 는 S - {i} 로 변 합 니 다.여기 서 우 리 는 S 를 집합 할 필요 가 없습니다. 하나의 변수 cur 를 이용 하여 현재 비트 가 채 워 야 할 수 를 표시 하면 됩 니 다.그러면 A 에 나타 나 지 않 은 요 소 는 모두 선택 할 수 있다.

#define N 100
int A[N];
void print_permutation(int n, int*A, int cur)
{
	if (cur == n)
	{
		for (int i = 0; i < n; i++)
			printf("%d ", A[i]);
		printf("
");
	}
	else for (int i = 1; i <= n; i++)
	{
		int ok = 1;
		for (int j = 0; j < cur;j++)
		if (A[j] == i){ ok = 0; break; }
		if (ok)
		{
			A[cur] = i;
			print_permutation(n, A, cur + 1);
		}
	}
}

재 집합 가능 한 배열
이 문 제 를 '배열 P 입력' 으로 바 꾸 면 P 에 있 는 요소 의 모든 배열 을 사전 순서에 따라 출력 합 니 다. 이 P 배열 에 있 는 요 소 는 중복 할 수 있 습 니 다.그러면 이 방법 은 대체적으로 전체 배열 과 유사 하지만 일부 세부 사항 은 변동 이 필요 하 다.
(1) 먼저 P 배열 을 정렬 한 다음 print 를 호출 합 니 다.permutation 함수;
(2) P 배열 에 요소 가 중복 되 기 때문에 cur 비트 전에 몇 개의 요소 가 있 는 지 확인 해 야 합 니 다. c1 개가 있다 고 가정 하고 P 배열 에 모두 c2 개가 있다 면 이 때 선택 할 수 있 습 니 다.
(3) P 배열 에 있 는 요 소 는 반복 적 으로 나타 날 수 있 지만 매 거 할 때 매 거 를 반복 해 서 는 안 되 기 때문에 P 의 첫 번 째 요소 와 모든 '이전 요소 와 다르다' 는 요 소 를 검사 해 야 합 니 다.

#define N 100
int A[N];
int P[N];
void print_permutation(int n, int*P, int*A, int cur)
{
	if (cur == n)
	{
		for (int i = 0; i < n; i++)
			printf("%d ", A[i]);
		printf("
");
	}
	else for (int i = 0; i < n; i++)//       
	if (!i || P[i] != P[i-1])//          
	{
		int c1 = 0, c2 = 0;
		for (int j = 0; j < cur; j++)if (A[j] == P[i])c1++;
		for (int j = 0; j < n; j++)if (P[j] == P[i])c2++;
		if (c1<c2)
		{
			A[cur] = P[i];
			print_permutation(n, P, A, cur + 1);
		}
	}
}