Permutation algorithm in the form of..

Question

R= repeats allowed -> 2
A= alphabet (1-10)
S= space = 4;

So we want example:

[1][1][4][5]
[1][7][4][5]
[5][1][4][5]

But need a fancy math formula to calculate this and all combinations ?

Answer 1

There are relatively few possible solutions (< 10000), so it should be ok to generate all words in A^4, then remove the words with more than 2 repeats.

OR

• Generate the (ordered) combinations of N distinct words

• Generate the permutations of that subset to get all the possibilities without duplicates

• Do the same with N-1 words

• For each element in these words, add a duplicate at all the positions but the position of the said character.

Answer 2

As I understand it, your alphabet is 1 .. 10, with each 'letter' possibly occurring twice. So what you really have is an alphabet that is ...

1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10

It has a length of 20, not 10.

The problem now becomes 20 permute 4.

Hope this helps.

EDIT: As per your additional comments to your question, you can then check each generated permutation to see if it is of the form XXYY as that would be invalid according to what you have written.

Answer 3

The total number is
N * [ (S choose 1) * ((N-1) permute (S-1)) + (S choose 2) * ((N-1) permute (S-2)) + ... + (S choose R) * ((N-1) permute (S-R)) ]

• In otherwords, probably best to fix 1 of the repeated item in place (S choose 1 different ways of doing this) and permute the remaining N-1 items over the S-1 remaining spaces; (same as normal N permute S)

• then fix 2 of your identical item in place (S choose 2 different ways of doing this) and permute the remaining N-1 items over the remaining S-2 spaces.

• etc for each possible number of repeated items, from 1 up to R

• And then there are N choices for your possible repeated item.

You can use this algorithm to enumerate the possibilities too.

Edit

Oh dear. Thanks @blueraja, you are absolutely correct! the n-repeated-items case does not generalise to 1 item!

corrected formula is therefore

(N permute S)
+ N * [ (S choose 2) * ((N-1) permute (S-2)) 
      + (S choose 3) * ((N-1) permute (S-3)) 
      + ... 
      + (S choose R) * ((N-1) permute (S-R)) ]

Answer 4

A correct general answer requires a summation. I will show you how to do it for these particular values, and let you generalize it.

There are two cases:

• Permutations containing no duplicates. This is just 10 P 4
• Permutations containing exactly one duplicate:
  • Choose which number is the duplicate: 10 C 1
  • Choose two places for it: 4 C 2
  • Choose the numbers which fit into the remaining two places: 9 P 2

Thus the answer to this particular case is 9360.

Answer 5

I assume that only one item can repeat, and this item is not predetermined.

Here is a formula that works on A(alphabet size), S(strings size) and R(maximum repetition count):

f(A,S,R) = (A perm S) + A*Sum[r=2 to R] ( (S choose r)*(A-1 perm S-r) )

For example, for R=1 (simple permutation) we get f(A,S,R)=(A perm S) as expected. For A=S=R=2 we have f(A,S,R)=4 which corresponds to:

1,2

2,1

1,1

2,2

The case you describe in the question is A=10, R=2, S=4, and then we have:

f(A,S,R) = 9360

(Exactly as BlueRaja calculated)

Answer 6

This is a nice article about combinations and permutations, there you can find all the formulas