Make a program able to count permutations and combinations. Follow these steps:
ID: 3574907 • Letter: M
Question
Make a program able to count permutations and combinations. Follow these steps: Read and make sure you understand the content presented in https://www.mathsisfun.com/combinatorics/combinations-permutations.html Read from file input prog1.txt a phrase that describes the counting to be performed. The phrase should have the following format: Count how many different possibilities are there for choosing r out of n elements with/without repetition. Order is/is not important. Words in bold are static which means that the user must type these exact words. Words in italic are the variables of the particular count. This is an example of the input: Count how many different possibilities are there for choosing 2 out of 3 elements without repetition. Order is important. Validate that the phrase is in the proper format. Store the four variables (n, r, order is or is not important, and with or without repetition). Output to console the type of count that the program will do: permutation or combination, with or without repetition. Output to console the formula to compute the count and the result Here, the output for the previous example:Explanation / Answer
Permutations with duplicates
#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
}
}
}
int main()
{
char str[] = "ABC";
int n = strlen(str);
permute(str, 0, n-1);
return 0;
}
Permutations without duplicates
public final class Permutation
{
private Permutation()
{
};
/* Return permutation of a given string. if the string contains duplicate characters, it will remove duplicate permutations. */
public static List<String> permutation(String string)
{
final List<String> stringPermutations = new ArrayList<String>();
permute(string, 0, stringPermutations);
return stringPermutations;
}
private static void permute(String s, int currIndex, List<String> stringPermutations)
{
if (currIndex == s.length() - 1)
{
stringPermutations.add(s); return;
} // prints the string without permuting characters from currIndex onwards.
permute(s, currIndex + 1, stringPermutations); // prints the strings on permuting the characters.
for (int i = currIndex + 1; i < s.length(); i++)
{
if (s.charAt(currIndex) == s.charAt(i)) continue;
s = swap(s, currIndex, i);
permute(s, currIndex + 1, stringPermutations);
}
}
private static String swap(String s, int i, int j)
{
char[] ch = s.toCharArray();
char tmp = ch[i]; ch[i] = ch[j]; ch[j] = tmp;
return new String(ch);
}
public static void main(String[] args)
{
for (String str : permutation("abc"))
{
System.out.println(str);
}
System.out.println("------------");
for (String str : permutation("aabb"))
{
System.out.println(str);
}
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.