CODEWITHSUNDEEP
algorithmpermutation
WernerCD
WernerCD

Reputation: 2157

Unique Permutations - with exceptions

I just did a quiz and it had a question that I brute forced... but I'm certain there is a "mathmatical" formula that "solves" it.

Permutations of a String

Say you have a string "abcdef"... count all unique permutations of the string. For a string with all unique options, this is simple: Length Factoral. So 6! = 720 unique combinations.

Unique Permutations

Now, when you add duplicates... you take the factoral, and devide by the product of the unique letters: "aaabbb" => 6! / (3! * 3!) => 720 / 36 => 20 unique combinations.

Unique Permutations, with exclusions

The part that stumps me:

You have a string, possibly with duplicate data... except now, exclude permutations that start with a space (or a dot, for visibility): 

"aa.bb" => "aabb." is a valid permutation... ".aabb" is not. 
"aa.bb.cc" => "aa..bbcc" valid permutation. ".aabbcc." not valid. "..aabbcc" is not valid
"a.." => has one valid permutation: "a.."... the others are all duplicates or start with spaces.

My Solution

My solution - brute force - was to create the permutations... and manually exclude those starting with spaces... O(N!) if I remember correctly.

I know it has something to do with factorals and the number of spaces. But the final answer eludes me.

I should be able to take the length, divide by the counts... and the calculate the distinct number that start with spaces and subtract that.

Upvotes: 2

Views: 797

Answers (2)

sudhansh_
sudhansh_

Reputation: 145

Let's say that you have 5 unique letters,

so you'll have 5! combinations.

Now when you have 5 unique alphabets and one ., then

In the first position, you'll put one of those 5 alphabets. Then, you'll put the rest of them (4 alphabets and 1 .) in 5! ways,

The result being 5*5!

So, the answer according to me should be along the lines of

Let's say you have x unique alphabets, y alphabets in all and z spaces

So the answer should be

y * (y+z-1)! / (diving for repeated alphabets and spaces combinations)

Upvotes: 1

Prune
Prune

Reputation: 77857

You partition the first character as a separate case: there are fewer choices for that character. This changes the first factor of the numerator of the calculation. For instance, aa.bb.cc has only 6 choices for the first character, not 8. Therefore, the calculation that was

8! / (2! 2! 2! 2!)   -- four duplicates

is now

(6 * 7!) / (2! 2! 2! 2!)   -- we still have four duplicates

Upvotes: 1

Related Questions