Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

i will try to be short. i need some "formula" or. a described way, how can i concat domains "together" so they dont touch?

in a example i will use letters instead of domains, i have:

A - gmail.com - 4
B - yahoo.com - 2
C - hotmail.com - 1
and thousand more

now i need some algorithm, so domains wont be together, like:

A | B | A | C | A | B | A

how can i accomplish that?


if letters must be togeter, let them be together as less as possible. another example is :

A - 10
B - 2

bad example of concat:

AAAAABAAAAAB

good example:

AAABAAABAAAA
share|improve this question
    
The problem is unclear. What makes AAABAAABAAA better than AAAAABAAAAAB? For what purpose are you concatenating them? Are you trying to find the shortest unambiguous string? Or is it about distributing the letters more evenly? –  Karolis Juodelė Aug 14 '12 at 10:38
    
hey, tnx for fast reply. rule: concat same characters as little as possible. AAAAABAAAAAB has AAAAAx2 = A10. AAABAAABAAAA has AAAx2 and AAAAx1 = 10A. in first example, they are more A's together than in second example. imagine this: 99xA and 2xB. in this example it is better to have 33A+B+33A+B+33A than 45A+B+44A+B... –  glavić Aug 14 '12 at 10:50
add comment

1 Answer 1

If no letter is more common than all the others put together, you should have no problems. You could first fill the even positions, then the odd. Example $A=3$, $B=2$, $C=2$ then $\text{A_A_A__} \rightarrow \text{ABA_A_B} \rightarrow \text{ABACACB}$. No repetitions will occur.

If A is more common than all the others put together, repetitions are unavoidable. Say $M$ is the number of As and $N$ is the number of all other characters. There are at most $N+1$ gaps between the $N$ characters. You need to distribute $M$ into $N+1$ parts as evenly as possible. All gaps will have $\lfloor \frac{M}{N+1} \rfloor$ As except for the first $M mod (N+1)$ which will have $1$ additional A.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.