# dms

// 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.

#include <stdio.h>
void permutations(int n, int r, int *arr, int index)
{
if (index == r)
{
for (int i =0; i < r; i++)
{
printf(“%d”, arr[i]);
}
printf(“\n”);
return;
}
int start = (index ==0) ?1:arr[index -1] +1;
for (int i = start; i <= n; i++)
{
arr[index] = i;
permutations(n, r, arr, index +1);
}
}
int main()
{
int n, r;
printf(“Enter n and r: “);
scanf(“%d%d”, &n, &r);
intarr[r];
permutations(n, r, arr, 0);
return0;
}

////

// 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;

}