0

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

vanandsh
  • 1
  • 2
  • This is tagged contest math; it would make sense to link to the contest so people can check what sort of contest it is and whether they want to answer questions about it. – joriki Apr 14 '13 at 07:42
  • 1
    For the first case where the array is ${a,b,c,d}$ why you don't include $adba$ and $adca$ in the answer? – P.. Apr 14 '13 at 07:46
  • sorry mate..missed out on it.. i have edited it – vanandsh Apr 14 '13 at 08:24

1 Answers1

0

So, for given $n, k$, it should be easy to figure this out ad hoc. By going from left to right. Pick the first letter, there are $n$ choices, the second letter would could be of $n-1$ choices (unless $k = 2$; then there are no words). Then we can go back to $n$ for the third letter (unless $k =3$) etc. You must have to worry about cases for the second to last letter for clear reasons.

AlexM
  • 931
  • 1
  • 5
  • 6