0
$\begingroup$

Disclaimer: I haven't done math in a decade. Sorry if this is not very scientific

Hello,

I am writing a computer program, that is supposed to return the number of all permutations of an input string, excluding the permutations where a letter is repeated consecutively. Ex. : Input is "aabc", valid permutations are "abac", "abca" invalid "baac", "bcaa".

My calculation looks like this:

  1. Take all permutations: 4!
  2. Take all permutations where "a" is repeated, treating the repeated character as one group. ex. [aa]bc, b[aa]c. In this case it's 3! - (length of string - group length + 1)
  3. Take all permutations of the letters within the group. ex. [a1a2]bc, [a2a1]bc. In this case 2! (group length)!

So the formula is 4! - (3! * 2!).

This seems to work as long as there is only one repeated character. However as soon as there is more than one, if I repeat the algorithm for all characters, I will discount some permutations twice (the ones that have both character repeated). Ex. input is: "aabbcd" "abbacd" is discounted once. "cdaabb" is discounted twice.

So I need an additional correction where I take the union of the results of the two algorithms and add it back.

Essentially: Out of all permutations of the string "aabbcd", what is the number of strings that have both "aa" and "bb" in them?

$\endgroup$
2
  • $\begingroup$ Just as you did before. Treat them as groups [aa][bb]cd. So 4! permutations with aa and bb. $\endgroup$ Commented Sep 22, 2015 at 15:35
  • $\begingroup$ You'll need to apply inclusion/exclusion principle. $\endgroup$ Commented Sep 22, 2015 at 16:07

2 Answers 2

Reset to default
0
$\begingroup$

@true blue anil

from the program's standpoint, the two a's are not treated as indistinguishable. ex. input: "aab"

  • a1a2b - invalid
  • a1ba2 - valid
  • a2a1b - invalid
  • a2ba1 - valid
  • ba1a2 - invlaid
  • ba2a1 - invalid

    • result should be 2.

    $\endgroup$
    1
    • $\begingroup$ I have added an edit to my answer to take care of this. $\endgroup$ Commented Sep 22, 2015 at 16:54
    0
    $\begingroup$

    In $#3$ of your calculations, permuting the two $a's$ is incorrect, since they are indistinguishable. The correct formula would just be $4!-3!$.

    For "valid" permutations of $aabbcd$, applying inclusion-exclusion, $[ 6!- 2*5! + 4! ]$

    Edit

    With the clarifications given in your answer, you will need to internally permute the identical letters, so $[6! - 2*5!*2! + 4!*2!*2!]$

    $\endgroup$

    You must log in to answer this question.

    Start asking to get answers

    Find the answer to your question by asking.

    Ask question

    Explore related questions

    See similar questions with these tags.