For this project you will be designing and implementing a system, in either Cor

ID: 3744589 • Letter: F

Question

For this project you will be designing and implementing a system, in either Cor C++, to answer a few mathematical questions. First, given the number 123456789, is it possible to find a permutation (i.e. a rearrangement that preserves the count of each number) such that the left most digit is evenly divisible by 1, the two left most digits are evenly divisible by 2, the three left most digits are divisibly by 3 and so on? For example, in 123456789, 1 is evenly divisible by 1, 12 is evenly divisible by 2, 123 is evenly divisible by 3, but because 1234 is not evenly divisible by 4 this number is not a solution to the question. Second, is it possible to find a similar permutation given the number 1234567890? Finally, is it possible to find a similar permutation for any of the given hexadecimal numbers, 1234567890AB, 1234567890ABC, 1234567890ABCD, 1234567890ABCDE, 1234567890ABCDEF?

Explanation / Answer

// C program to print all permutations with duplicates allowed

#include <stdio.h>

#include <string.h>

/* Function to swap values at two pointers */

void swap(char *x, char *y)

{

char temp;

temp = *x;

*x = *y;

*y = temp;

}

/* Function to print permutations of string

This function takes three parameters:

1. String

2. Starting index of the string

3. Ending index of the string. */

void permute(char *a, int l, int r)

{

int i;

if (l == r)

printf("%s ", a);

else

{

for (i = l; i <= r; i++)

{

swap((a+l), (a+i));

permute(a, l+1, r);

swap((a+l), (a+i)); //backtrack

}

/* Driver program to test above functions */

int main()

{

char str[] = "ABC";

int n = strlen(str);

permute(str, 0, n-1);

return 0;

}