You are given a sequence of n numbers. Each number is either distinct or occurs in duplicate, i.e., each number in the sequence occurs at most two times. The goal is to count the number of permutations that are “good”. A good permutation is one in which no two duplicates occur together. For example if the sequence is 2 1 1 2, the number of good permutations are 2 which are: 1 2 1 2 and 2 1 2 1. (Note that any other permutation such as 1 2 2 1 is not good, since 2 and 2 occur next to each other.) If the sequence is 3 3, then there are no good permutations, and if the sequence is 2, then there is only one good permutation {3,1,2,1,2,3} output : 30 {2,1,1} output : 1 e.g 1 1 2 -Bad 1 2 1 Good 1 2 1 Good(unique) pick only 1 etc Hint: you only need the number of unique elements and the number of repeated elements in your dp. an element can only be repeated at most twice
Comments: Thanks for the contributions,so on what i have tried, I have tried solving this problem by simply n! * (n-1)! * 2!, that works when the repeated character is just one, then n! - "invalid"(n-1)!* duplicates * 2! + overlap * duplicates * 2! This works for a case where the repeated chars is only two but above two returns an incorrect answer i will need the general case. If this is not clear then see this stack overflow post second solution. Unfortunately none of the solutions i have found so far is a dp solution. I can't even get a good close form https://stackoverflow.com/questions/32282607/permutations-excluding-repeated-characters?lq=1
A "closed-form" answer can be obtained using the inclusion-exclusion principle. Suppose there are $d$ numbers occurring twice; w.l.o.g. we can assume that these numbers are $1,\ldots,d$. For $1\leqslant j\leqslant d$, let $A_j$ be the set of the permutations with consecutive occurrences of $j$. Then the answer is the size of $\bigcap_{j=1}^{d}\overline{A_j}$, which we compute using IEP: for $0\leqslant k\leqslant d$, the size of the intersection of any $k$ of the sets $A_j$ is equal to $(n-k)!/2^{d-k}$, hence the answer is $$\sum_{k=0}^{d}(-1)^k\binom{d}{k}\frac{(n-k)!}{2^{d-k}}.$$