// 1. Given a positive integer n and a nonnegative integer not exceeding n, find the number of r-permutations and r combinations of a set with n elements.
#include <stdio.h>
int fact(int n) {
// Compute n!
int result = 1;
for (int i = 1; i <= n; i++) {
result *= i;
}
return result;
}
int nPr(int n, int r) {
// Compute the number of r-permutations of a set with n elements
return fact(n) / fact(n – r);
}
int nCr(int n, int r) {
// Compute the number of r-combinations of a set with n elements
return nPr(n, r) / fact(r);
}
int main() {
// Test the functions with some example values
int n = 6, r = 3;
printf(“n = %d, r = %d\n”, n, r);
printf(“nPr = %d\n”, nPr(n, r));
printf(“nCr = %d\n”, nCr(n, r));
return 0;
}
///
// 2. Given a positive integer n and a nonnegative integer r not exceeding n, list all the r-permutations
of the set {1, 2, 3, . . . , n} in lexicographic order.
////
// 3. Given a positive integer n, list all the permutations of the set {1, 2, 3, . . . , n} in lexicographic order.
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
void printArray(int *array, int size) {
for (int i = 0; i < size; i++) {
printf(“%d “, array[i]);
}
printf(“\n”);
}
bool nextPermutation(int *array, int size) {
int i = size – 2;
while (i >= 0 && array[i] >= array[i + 1]) {
i–;
}
if (i < 0) {
return false;
}
int j = size – 1;
while (array[j] <= array[i]) {
j–;
}
swap(&array[i], &array[j]);
int k = i + 1;
int l = size – 1;
while (k < l) {
swap(&array[k], &array[l]);
k++;
l–;
}
return true;
}
int main() {
int n;
printf(“Enter the number of elements in the set: “);
scanf(“%d”, &n);
int *array = (int*)malloc(n * sizeof(int));
for (int i = 0; i < n; i++) {
array[i] = i + 1;
}
printArray(array, n);
while (nextPermutation(array, n)) {
printArray(array, n);
}
free(array);
return 0;
}
///
// 4. Given a positive integer n and a nonnegative integer r not exceeding n, list all the r-combinations of the set {1, 2, 3, . . . , n} in lexicographic order.
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
void printArray(int *array, int size) {
for (int i = 0; i < size; i++) {
printf(“%d “, array[i]);
}
printf(“\n”);
}
bool nextCombination(int *array, int n, int r) {
int i = r – 1;
while (i >= 0 && array[i] == n – r + i + 1) {
i–;
}
if (i < 0) {
return false;
}
array[i]++;
for (int j = i + 1; j < r; j++) {
array[j] = array[j – 1] + 1;
}
return true;
}
int main() {
int n, r;
printf(“Enter the number of elements in the set: “);
scanf(“%d”, &n);
printf(“Enter the number of elements to choose: “);
scanf(“%d”, &r);
int *array = (int*)malloc(r * sizeof(int));
for (int i = 0; i < r; i++) {
array[i] = i + 1;
}
printArray(array, r);
while (nextCombination(array, n, r)) {
printArray(array, r);
}
free(array);
return 0;
}
