Minimize the number of consecutive equal extractions in a deque of map<string, string>

Question

I hope this place is the best for this kind of question.

I've the following problem (I think is more complex than it appears).

I'm using a double-ended queue (deque) data structure of strings. deque < string > extractions;

The deque contains only N different strings, every string repeated for M times in random order, so that the lenght of the deque is N*M, for example, suppose M=4, N=2, string1="A", string2="B":

extractions[1] = "A"
extractions[2] = "A"
extractions[3] = "B"
extractions[4] = "B"
extractions[5] = "A"
extractions[6] = "B"
extractions[7] = "B"
extractions[8] = "A"

I'm in search of an algorithm which allows me to find an interesting configuration in which there aren't two consecutive equal elements, in this case there should be only two solutions, the "A","B","A","B","A","B","A","B" and the "B","A","B","A","B","A","B","A". For "interesting" configuration I mean the configuration not simply given by a number N of nested loops.

A very stupid solution I've implemented is to randomly shuffle the deck with std::random_shuffle until no occurence of consecutive equal elements is found, but this is both stupid and slow, this is more like a bogosort...

Clearly maximizing the edit distance between the strings should be better. Some hint?

Answer 1

Start with a trivial configuration, e.g for N=4 an M=4, start from

A B C D A B C D A B C D A B C D

and then run a standard shuffling algorithm but observing the constraint that you do not bring two equal elements next to each others, i.e.

for i = 0 .. N*M - 2
  let j = random(N*M - 2 - i) + i + 1
    if ((i == 0 || array[i - 1] != array[j])
        && (array[i + 1] != array[j])
        && (array[i] != array[j - 1])
        && (j == N*M - 1 || array[i] != array[j + 1]))
      swap (array[i], array[j])

This should leave you very quickly with a random configuration that fulfills your requirement of not having two consecutive equal elements.