Count all permutations where there are no two adjacent characters
Given a sequence that only contains different numbers of numbers 1, 2, 3, and 4 (examples: 13244, 4442, etc.), I want to consider all my permutations so that no two adjacent numbers match. I believe this is O (N! * N) and want to know if there is a better one out there. Does anyone have any idea?
class Ideone
{
static int permutationCount++;
public static void main(String[] args) {
String str = "442213";
permutation("", str);
System.out.println(permutationCount);
}
private static void permutation(String prefix, String str) {
int n = str.length();
if (n == 0){
boolean bad = false;
//Check whether there are repeating adjacent characters
for(int i = 0; i < prefix.length()-1; i++){
if(prefix.charAt(i)==prefix.charAt(i+1))
bad = true;
}
if(!bad){
permutationCount++;
}
}
else {
//Recurse through permutations
for (int i = 0; i < n; i++)
permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n));
}
}
}
source to share
I understand your question this way: Given a string containing only numbers 1,2,3,4 - how many permutations of these characters are there, when you put them back into the string there won't be any identical contiguous numbers.
I would suggest an approach like this:
L - length of your string
n1 - how many times is 1 repeated, n2 - how many times is 2 repeated etc.
P - number of all possible permutations
P = L! / (n1!*n2!*n3!*n4!)
C - number of all solutions fitting your constraint
C = P - start with all permutations
substract all permutations which have 11 in it (just take 11 as one number)
C = C - (L - 1)! / ((n1 - 1)! * n2! * n3! * n4!)
... do the same for 22 ...
add all permutations which have both 11 and 22 in it (because we have substracted them twice, so you need to add them)
C = C + (L - 2)! / ((n1 - 1)! * (n2 - 1)! * n3! * n4!)
... repeat previous steps for 33 and 44 ...
source to share
If you just want to calculate how many permutations fit your constraint, you don't need to specify each one.
If I am asking your question correctly, your input line contains 4 different inputs 1,2,3,4
and you want to know how many of them are possible?
Then you have to use some math, namely n! / (n-r)!
where n
is the number of items to choose from (in this case 4) and r
is the number of positions you want to fill (also 4).
Permutations are possible in your example 4! / (4-4)! = 24
:
{1,2,3,4} {1,2,4,3} {1,3,2,4} {1,3,4,2} {1,4,2,3} {1,4,3,2} {2,1,3,4} {2,1,4,3} {2,3,1,4} {2,3,4,1} {2,4,1,3} {2,4,3,1} {3,1,2,4} {3,1,4,2} {3,2,1,4} {3,2,4,1} {3,4,1,2} {3,4,2,1} {4,1,2,3} {4,1,3,2} {4,2,1,3} {4,2,3,1} {4,3,1,2} {4,3,2,1}
In a nutshell, for lengths n
with n
different values, the permutation counter n!
:
1 -> 1
2 -> 2
3 -> 6
4 -> 24
5 -> 120
...
source to share
Edit: After your changes and comments, it is clear that I misunderstood the question.
If you just want to check if there are any matching adjacent numbers, you can use a simple loop. This will be O (n) complexity.
public static void main(String[] args) {
String str = "442213";
System.out.println(permutation(str));
}
public static int permutation(String str) {
int permutationCount = 0;
if (str.length() > 1) {
for (int i = 0; i < str.length() - 1; i++) {
if (str.charAt(i) != str.charAt(i + 1)) {
permutationCount++;
}
}
}
return permutationCount;
}
If you want to stick with recursion, you can do something like this:
public static void main(String[] args) {
String str = "442213";
System.out.println(permutation(str, 0));
}
public static int permutation(String str, int currentIndex) {
int permutationCount = 0;
if (str == null || currentIndex + 1 >= str.length()) {
return permutationCount;
}
if (str.charAt(currentIndex) != str.charAt(currentIndex + 1)) {
permutationCount = 1;
}
return permutationCount + permutation(str, currentIndex + 1);
}
source to share