How to shuffle a array of objects with no two duplicates next to each other?

Question

I need to shuffle an array of objects that I receive from an API. The array will have the same occurrence of repeated objects.

Valid input:

["a","a","a","a","b","b","b","b","c","c","c","c"]
["a", "a", "b", "b"] or ["b", "b", "a", "a"]

Invalid input:

["a","a","a","a","b","c"]
["a", "b", "a", "b"]

After shuffling:

The objects at i and i + 1 should be different
Every time the array is shuffled it should generate a new valid solution

Valid outputs:

b,a,c,b,a,c,a,c,b,a,c,b
c,a,b,a,b,c,a,c,b,a,b,c
c,b,a,c,b,a,c,b,a,c,b,a

Invalid outputs:

c,c,a,b,b,a,c,b,a,c,b,a

I started using Fisher–Yates for an initial shuffle and then validate if the solution is valid. This brute force approach is working once I have a small set, but as the input grows it gets useless. Is there an efficient way to generate a random permutation without leaving duplicates next to each other?

Efficient algorithm for ordering different types of objects gave an insight on how to keep the objects of the same kind far from each other, unfortunately, I'll run into the same solution/pattern If I try to shuffle it again.

https://stackoverflow.com/a/32366585/4271233 generates all possible permutations that satisfy the "no two duplicates next to each other", but I'd sadly need to generate all of them and then pick randomly one

You need an array shuffled, and I need a question. Other than *solve this please* :) [ask] — sleepToken, Nov 25 '19 at 16:58
@luk2302, I'm using Fisher–Yates and then validating if the solution is valid. This brute force approach is working once I have a small set, but as the input grows it gets useless — Ygor, Nov 25 '19 at 17:05
Possible duplicate of [Efficient algorithm for ordering different types of objects](https://stackoverflow.com/questions/37452547/efficient-algorithm-for-ordering-different-types-of-objects) — beaker, Nov 25 '19 at 17:43
Also see https://stackoverflow.com/questions/37040164/how-to-shuffle-a-character-array-with-no-two-duplicates-next-to-each-other — beaker, Nov 25 '19 at 17:43
@elbraulio, the objects of the same type will be received together, thus, just [a,a,b,b] or [b,b,a,a] are valid — Ygor, Nov 25 '19 at 18:11

score 1 · Accepted Answer · answered Nov 25 '19 at 20:15

This solution is not optimal but you can start from this

    public static void main(String[] args) {
        String[] input = new String[]{
                "a", "a", "a", "a", "b", "b", "b", "b", "c", "c", "c", "c"
        };
        // here we'll generate the output
        String[] output = new String[input.length];
        // how many different characters do we have?
        int characters = 0;
        for (int i = 1; i < input.length; i++) {
            if (!input[i - 1].equals(input[i])) {
                break;
            } else {
                characters++;
            }
        }
        // how many times each character appears
        int times = input.length / characters;
        // different characters to shuffle
        String[] toShuffle = new String[characters];
        int m = 0;
        while (times * m < input.length) {
            toShuffle[m] = input[times * m];
            m++;
        }
        // for each position in output
        for (int i = 0; i < output.length;) {
            // define a list with all different characters
            List<String> remain = new ArrayList<>(Arrays.asList(toShuffle));
            // set a random character without repetition
            int j = 0;
            while (j < characters) {
                int pos = 0;
                // after {characters} we have a chance of repetition so we check
                if(i % characters == 0 && i != 0) {
                    do {
                        pos = Double.valueOf(Math.random() * remain.size())
                                .intValue();
                    } while (output[i-1].equals(remain.get(pos)));
                } else {
                    pos = Double.valueOf(Math.random() * remain.size())
                            .intValue();
                }
                // assign a character
                output[i] = remain.get(pos);
                // remove from possible chars to not repeat
                remain.remove(pos);
                j++;
                i++;
            }
        }
        // this is the solution
        System.out.println(Arrays.toString(output));
    }

How to shuffle a array of objects with no two duplicates next to each other?

1 Answers1

Linked