如何洗牌一个没有两个重复项的对象数组？

Question

我需要打乱从 API 接收到的对象数组。该数组将具有相同的重复对象。

有效输入：

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

输入无效：

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

洗牌后：

i 和 i+1 处的对象应该不同
每次打乱数组时，它都应该生成一个新的有效解决方案

有效输出：

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

无效输出：

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

我开始使用 Fisher–Yates 进行初始洗牌，然后验证解决方案是否有效。一旦我有了一个小集合，这种蛮力方法就会起作用，但随着输入的增加，它就变得无用了。有没有一种有效的方法来生成随机排列而不会将重复项彼此相邻？

给出了如何使同类对象彼此远离的见解，不幸的是，我会运行进入相同的 solution/pattern 如果我尝试重新洗牌。

生成满足 "no two duplicates next to each other" 的所有可能排列，但遗憾的是我需要生成所有排列，然后随机选择一个

Answer 1

这个解决方案不是最优的，但你可以从这个开始

    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?

java

arrays

algorithm

shuffle