有没有一种方法可以对数组进行混洗，以使两个连续的值都不相同? [英] Is there a way to shuffle an array so that no two consecutive values are the same?

问题描述

我有多种颜色可以填充饼图以充当游戏微调框.我不希望相同的颜色彼此相邻出现，从而在圆圈中形成一大块.

I have an array of colors that will populate a pie chart to act as a game spinner. I don't want the same colors to appear next to each other, making one huge chunk in the circle.

我的数组看起来像这样:

My array looks something like this:

var colors = ["blue", "red", "green", "red", "blue", "blue", "blue", "green"]

当然，问题在于三个忧郁症在一起. Swift内置了什么功能，可以让我在总分布范围内均等(或尽可能接近均等)分布值，并避免它们相邻?

The problem is of course that there are three blues together. Is there anything built into Swift that will allow me to equally (or as close to equally as possible) spread values within the total distribution and avoid them being adjacent?

我可以使用以下代码测试是否匹配，但是重新排列它们会变得有些困难.

I can test for a match with the following code, but rearranging them proves to be a bit more difficult.

var lastColor = "white"

for color in colors {
    if color == lastColor {
        print("match")
    }
    lastColor = color    
}

更新:

要创建我的colors数组，我从每种颜色的空格数开始.看起来像这样:

To make my colors array, I start out with the number of spaces for each color. It looks something like this:

let numberOfReds = 2
let numberOfGreens = 2
let numberOfBlues = 4

let spaces = numberOfReds + numberOfGreens + numberOfBlues

for _ in 0..< spaces {
    if numberOfReds > 0 {
        numberOfReds -= 1
        colors.append("red")
    }
    if numberOfGreens > 0 {
        numberOfGreens -= 1
        colors.append("green")
    }
    if numberOfBlues > 0 {
        numberOfBlues -= 1
        colors.append("blue")
    }
}

最终吐出来的东西:

colors = ["red", "green", "blue", "red", "green", "blue", "blue", "blue" ]

推荐答案

尽管外观如此，但这并不简单.正如评论员@ antonio081014所指出的，这实际上是一个算法问题，并且(如@MartinR所指出的)被解决

Despite appearances, this is non-trivial. As the commentator @antonio081014 points out, it's actually an algorithmic question, and (as @MartinR points out) is addressed here. Here's a very simple heuristic that (unlike the solution from @appzYourLife) is not an algorithm, but will work in most cases, and is much faster (O(n^2) rather than O(n!)). For randomness, simply shuffle the input array first:

func unSort(_ a: [String]) -> [String] {
    // construct a measure of "blockiness"
    func blockiness(_ a: [String]) -> Int {
        var bl = 0
        for i in 0 ..< a.count {
            // Wrap around, as OP wants this on a circle
            if a[i] == a[(i + 1) % a.count] { bl += 1 } 
        }
        return bl
    }
    var aCopy = a // Make it a mutable var
    var giveUpAfter = aCopy.count // Frankly, arbitrary... 
    while (blockiness(aCopy) > 0) && (giveUpAfter > 0) {
        // i.e. we give up if either blockiness has been removed ( == 0)
        // OR if we have made too many changes without solving

        // Look for adjacent pairs    
        for i in 0 ..< aCopy.count {
            // Wrap around, as OP wants this on a circle
            let prev = (i - 1 >= 0) ? i - 1 : i - 1 + aCopy.count
            if aCopy[i] == aCopy[prev] { // two adjacent elements match
                let next = (i + 1) % aCopy.count // again, circular 
                // move the known match away, swapping it with the "unknown" next element
                (aCopy[i], aCopy[next]) = (aCopy[next], aCopy[i])
            }
        }
        giveUpAfter -= 1
    }
    return aCopy
}

var colors = ["blue", "red", "green", "red", "blue", "blue", "blue", "green"]
unSort(colors) // ["blue", "green", "blue", "red", "blue", "green", "blue", "red"]

// Add an extra blue to make it impossible...
colors = ["blue", "blue", "green", "red", "blue", "blue", "blue", "green"]
unSort(colors) //["blue", "green", "blue", "red", "blue", "blue", "green", "blue"]

这篇关于有没有一种方法可以对数组进行混洗，以使两个连续的值都不相同?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！