Shuffle an array without creating any runs

Question

I have an array of repeating letters:

AABCCD

and I would like to put them into pseudo-random order. Simple right, just use Fisher-Yates => done. However there is a restriction on the output - I don't want any runs of the same letter. I want at least two other characters to appear before the same character reappears. For example:

ACCABD

is not valid because there are two Cs next to each other.

ABCACD

is also not valid because there are two C's next to each other (CAC) with only one other character (A) between them, I require at least two other characters.

Every valid sequence for this simple example:

ABCADC ABCDAC ACBACD ACBADC ACBDAC ACBDCA ACDABC ACDACB ACDBAC ACDBCA ADCABC ADCBAC BACDAC BCADCA CABCAD CABCDA CABDAC CABDCA CADBAC CADBCA CADCAB CADCBA CBACDA CBADCA CDABCA CDACBA DACBAC DCABCA

I used a brute force approach for this small array but my actual problem is arrays with hundreds of elements. I've tried using Fisher-Yates with some suppression - do normal Fisher-Yates and then if you don't like the character that comes up, try X more times for a better one. Generates valid sequences about 87% of the time only and is very slow. Wondering if there's a better approach. Obviously this isn't possible for all arrays. An array of just "AAB" has no valid order, so I'd like to fail down to the best available order of "ABA" for something like this.

Answer 1

Here is a modified Fisher-Yates approach. As I mentioned, it is very difficult to generate a valid sequence 100% of the time, because you have to check that you haven't trapped yourself by leaving only AAA at the end of your sequence.

It is possible to create a recursive CanBeSorted method, which tells you whether or not a sequence can be sorted according to your rules. That will be your basis for a full solution, but this function, which returns a boolean value indicating success or failure, should be a starting point.

public static bool Shuffle(char[] array) 
{
    var random = new Random();
    var groups = array.ToDictionary(e => e, e => array.Count(v => v == e));
    char last = '\0';
    char lastButOne = '\0';
    for (int i = array.Length; i > 1; i--)
    {
        var candidates = groups.Keys.Where(c => groups[c] > 0)
            .Except(new[] { last, lastButOne }).ToList();
        if (!candidates.Any())
            return false;

        var @char = candidates[random.Next(candidates.Count)];
        var j = Array.IndexOf(array.Take(i).ToArray(), @char);
        // Swap.
        var tmp = array[j];
        array[j] = array[i - 1];
        array[i - 1] = tmp;
        lastButOne = last;
        last = @char;
        groups[@char] = groups[@char] - 1;
    }
    return true;
}

Answer 2

Maintain a link list that will keep track of the letter and it's position in the result.

After getting the random number,Pick it's corresponding character from the input(same as Fisher-Yates) but now search in the list whether it has already occurred or not.

If not, insert the letter in the result and also in the link list with its position in the result.

If yes, then check it's position in the result(that you have stored in the link list when you have written that letter in result). Now compare this location with the current inserting location, If mod(currentlocation-previouslocation) is 3 or greater, you can insert that letter in the result otherwise not, if not choose the random number again.