I have been trying to solve a question on permutation and haven't really been successful. I want to generate all the permutations of a specified length that start with a letter and end with the same,and no two consecutive letters should be the same. The permutations generated can have repeated letters.
For example,
if the array has {a,b,c,d} and i want all the permutations that start and end with a.
The answer should be:
abca
abda
acba
acda
If the array is {a,b,c,d,e}
Output:
abcda
abada
abdca
abaca
acbda
acada
acdba
acaba
adbca
adaca
adcba
adaba
abcba
ababa
abdba
acbca
acaca
acdca
adbda
adcda
adada
I even would like to know if there is some way by which i can directly get to know the no.of solutions I will get for an array by some formula..
Thank You everyone in advance..
The algoritm is as follows. You start from some letter a and then have a set of all letters which you can use next. Then for each element from the set you expand a to ab ac ad. Then you add a back to set and remove b, c, d from set for each of the new words correspondingly. After that you do the same (recursion). The only tricky part is when you are aboit to finish. Then you also need to remove letter from which you started before you choose second to last letter.
As for mathematics formula:
Let denote T(n,l) as number of "permutations" of length l and alphabet of size n.
Now we can devise the following recursion:
T(n,3) = n - 1 // a(something other than a)a
T(n,k) = (n-1)^(l-2) - T(n, k-1)
What happens in the recursive case. We start from considering the case when last and second to last letter may be equal. So we have a(letter other than previous, so (n-1) choices)^(l-2) and finally we substract these cases where first letter equals to second to last, which is T(n, k-1).
To compute it efficiently on computer use dynamic programming or memoization.