양의 정수 n과 n을 넘지 않고 음이 아닌 정수r이 주어져 있을 때, 집합{1,2,3,….,n}의 모든 r-순열을 사전순으로 나열하라.

#include <stdio.h>
#include <stdlib.h>

int n, r;
int *leaf; // 트리의 잎 배열
int *overlap; // 중복 확인 배열 
int count = 0; // 순열 나열한 것 줄 단위로 카운트

// 팩토리얼 함수
int factorial(int a, int b) {
	if (a == 0)
		return 1;

	else {
		int result = 1;
		for (int i = a; i > b; i--)
			result *= i;
		return result;
	}
}

// 순열 개수 구하는 함수
int permu_num() {
	if (r >= 0 && r <= n) {
		int answer = factorial(n, n - r);
		printf("▷ P(%d,%d) = %d\n\n", n, r, answer);
	}
}

// 순열 나열하는 함수 
void permutation(int depth)
{
	if (r == depth) {
		for (int i = 0; i < r; i++)
			printf("%d ", leaf[i]);
		printf("\n");
		if(r!=0) count++;
		return;
	}

	for (int i = 0; i < n; i++) {
		/* 이전의 i와 이번의 i랑 같으면
		   ex) selected[0]=selected[1]=i+1이 되므로 중복!! */
		if (overlap[i] == 1)
			continue;
		overlap[i] = 1;
		leaf[depth] = i + 1;
		permutation(depth + 1);
		overlap[i] = 0;
	}
}

int main()
{
	printf("■ 양의 정수 n과 n을 넘지 않고 음이 아닌 정수 r이 주어져 있을 때, 집합 {1,2,3,....,n}의 모든 r-순열을 사전순으로 나열하라.\n");
	printf("\n□ n을 입력하시오: ");

	// n 입력 받기
	scanf_s("%d", &n);

	// r만들기 (0~n-1)
	srand(time(NULL));
	r = rand()%n;
	printf("\n▷ r = %d\n", r);

	// n과 r을 바탕으로 트리 구성에 필요한 데이터 구하기 
	if (r != 0) leaf = (int *)malloc(sizeof(int)*r);
	overlap = (int *)malloc(sizeof(int)*n);

	// 순열 문제 풀기 
	permu_num();
	permutation(0);
	printf("\n◈ 순열 나열한 것 카운트 = %d\n", count);

	// 메모리 할당 해제
	free(leaf);
	free(overlap);

	return 0;
}

확률 코드 패키지

조합 사전 순으로 나열하기

중복 조합 사전 순으로 나열하기

중복 순열 사전 순으로 나열하기

순열 사전 순으로 나열하기