Count All Permutations Where No Two Adjacent Characters Are the Same

Question

Given a sequence which contains only various amounts of the numbers 1, 2, 3, and 4 (examples: 13244, 4442, etc), I want to count all its permutations such that no two adjacent numbers are the same. I believe it is O(N! * N) and want to know if there is a better one out there. Anyone have any ideas?

 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));
            }
        }
    }

but your string is "442213" - can you describe what you mean by no "repeating" characters? — dognose, Nov 11 '14 at 18:41
Your algorithm returns a permutation count of `2` for the input `"121"`. Is this the expected result? — eee, Nov 11 '14 at 20:37
@JohnRoberts I think my answer to this question describes a more efficient algorithm: http://stackoverflow.com/questions/25285792/generate-all-permutations-of-a-list-without-adjacent-equal-elements/32366585#32366585 — m69's been on strike for years, Sep 03 '15 at 04:09

jakub.petr · Accepted Answer · 2014-11-11T19:56:08.737

I understand your question like this: Given a string containing only numbers 1,2,3,4 - how many permutations of these characters exist that when you put them into string again there won't be any same adjecent numbers.

I would suggest this approach:

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

I could not understand this step `C = P - start with all permutations`. Do we need to calculate these many steps? Cant we reach one single formula, for suppose with only 1, 2 and 3 as the digits — Vivek Vardhan, Mar 08 '15 at 15:22

score 0 · Answer 2 · edited Nov 11 '14 at 18:58

0

If you just want to calculate how many permutations match your constraint, it is not required to spell each of them out.

If I get your question right, your input string has 4 distinct input characters 1,2,3,4 and you want to know how many permutations of this are possible?

Then you should use some maths, namely n! / (n-r)!, where n is the number of elements to choose from (4 in this case) and r is the number of positions you want to fill (also 4).

Your example would have 4! / (4-4)! = 24 permutations possible:

{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 length n with n distinct values the count of permutations is n!:

1 -> 1
2 -> 2
3 -> 6
4 -> 24
5 -> 120
...

edited Nov 11 '14 at 18:58

Jean-François Corbett

37,420
30
139
188

answered Nov 11 '14 at 18:47

dognose

20,360
9
61
107

I am not just looking for the number of permutations of a particular sequence using those distinct characters, but the number of permutations where no two adjacent numbers are the same. For example, if I had the sequence 323, then 332 would not be a valid permutation. – John Roberts Nov 11 '14 at 19:03
@JohnRoberts that changes the picture a bit. For a input sequence of `1223` - would `1212` be valid, or is lacking the `3` ? – dognose Nov 11 '14 at 19:10
It needs the 3, as it needs to be a permutation of 1223. So 1232 would be valid, for example. – John Roberts Nov 11 '14 at 19:13

LucasP · Answer 3 · 2014-11-11T19:13:21.133

Edit: After your edits and comments it is clear that I misunderstood the question.

If you just want to check to see if there are no matching adjacent numbers, then 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 wanted to stick with recursion, you could 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);
}

Count All Permutations Where No Two Adjacent Characters Are the Same

3 Answers3

Linked