Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 - - 4
B - - 2
C - - 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:


good example:

share|cite|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

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|cite|improve this answer

Your Answer


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.