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.

If there is a particular language you are working with, I would tag it just for more exposure. I only say that because your post has been up for a while only has 11 views :) — Paul Samsotha
– Paul Samsotha, Commented Dec 8, 2013 at 10:07
@peeskillet The actual language I am using is uncommon so wouldn't help. I see that C# is the most popular tag, meta.stackexchange.com/questions/23554/tag-trends-by-week, so I'll use that one. Thanks for the suggestion. — Andrew
– Andrew, Commented Dec 8, 2013 at 10:41
It's very difficult to generate valid arrays one hundred percent of the time because you can reach the end of your modified Fisher-Yates routine and find you've got no valid candidates left. — Rob Lyndon
– Rob Lyndon, Commented Dec 8, 2013 at 11:46

Rob Lyndon · Accepted Answer · 2013-12-08 13:07:40Z

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;
}

Jatin Khurana · Accepted Answer · 2013-12-08 15:15:15Z

0

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.

answered Dec 8, 2013 at 15:15

Jatin Khurana

1,1758 silver badges17 bronze badges

2 Comments

Andrew Over a year ago

I'm not clear on how this is superior to "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." which was part of the question.

Jatin Khurana Over a year ago

The above algorithm is deterministic algorithm.you can use Hashing to store and retrieve the position(more efficient if number of character are predefined in your text). Whenever there is a wrong pattern, the above algorithm doesn't start with the starting. It calculates the pseudo pattern in one go.

Collectives™ on Stack Overflow

Shuffle an array without creating any runs

2 Answers 2

Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related