有没有办法对数组进行混洗,以便没有两个连续的值相同？

Question

我有一系列颜色可以填充饼图作为游戏微调器.我不希望相同的颜色彼此相邻,在圆圈中形成一个巨大的块.

我的数组看起来像这样:

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

问题当然是有三个蓝调在一起.Swift中是否有任何内容可以让我在总分布中平均(或尽可能接近)扩散值并避免它们相邻？

我可以使用以下代码测试匹配,但重新排列它们会证明有点困难.

var lastColor = "white"

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

更新:

为了制作我的colors数组,我从每种颜色的空格数开始.它看起来像这样:

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" ]

Answer 1

免责声明:为了生成"随机"解决方案,我将使用回溯.从空间的角度来看,这种方法并不快,并且不便宜.

事实上,时间和空间的复杂性都是O(n!)......这太棒了!

但它会为您提供尽可能随机的有效解决方案.

回溯

因此,如果没有2个连续的等于元素,则需要随机组合值列表和解决方案有效的条件.

为了得到真正的随机解决方案,我建议采用以下方法.

我生成了所有可能的有效组合.为此,我正在使用回溯方法

func combinations<Element:Equatable>(unusedElms: [Element], sequence:[Element] = []) -> [[Element]] {
    // continue if the current sequence doesn't contain adjacent equal elms
    guard !Array(zip(sequence.dropFirst(), sequence)).contains(==) else { return [] }

    // continue if there are more elms to add
    guard !unusedElms.isEmpty else { return [sequence] }

    // try every possible way of completing this sequence
    var results = [[Element]]()
    for i in 0..<unusedElms.count {
        var unusedElms = unusedElms
        let newElm = unusedElms.removeAtIndex(i)
        let newSequence = sequence + [newElm]
        results += combinations(unusedElms, sequence: newSequence)
    }
    return results
}

现在给出一个颜色列表

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

我可以生成每个有效的可能组合

let combs = combinations(colors)

[["blue", "red", "green", "blue", "red", "blue", "green", "blue"], ["blue", "red", "green", "blue", "red", "blue", "green", "blue"], ["blue", "red", "green", "blue", "green", "blue", "red", "blue"], ["blue", "red", "green", "blue", "green", "blue", "red", "blue"], ["blue", "red", "green", "blue", "red", "blue", "green", "blue"], ["blue", "red", "green", "blue", "red", "blue", "green", "blue"], ["blue", "red", "green", "blue", "green", "blue", "red", "blue"], ["blue", "red", "green", "blue", "green", "blue", "red", "blue"], ["blue", "red", "green", "blue", "red", "blue", "green", "blue"], ["blue", "red", "green", "blue", "red", "blue", "green", "blue"], ["blue", "red", "green", "blue", "green", "blue", "red", "blue"], ["blue", "red", "green", "blue", "green", "blue", "red", "blue"], ["blue", "red", "blue", "green", "red", "blue", "green", "blue"], ["blue", "red", "blue", "green", "red", "blue", "green", "blue"], ["blue", "red", "blue", "green", "blue", "red", "blue", "green"], ["blue", "red", "blue", "green", "blue", "red", "green", "blue"], ["blue", "red", "blue", "green", "blue", "green", "red", "blue"], ["blue", "red", "blue", "green", "blue", "green", "blue", "red"], ["blue", "red", "blue", "green", "blue", "red", "blue", "green"], ["blue", "red", "blue", "green", "blue", "red", "green", "blue"], ["blue", "red", "blue", "green", "blue", "green", "red", "blue"], ["blue", "red", "blue", "green", "blue", "green", "blue", "red"], ["blue", "red", "blue", "red", "green", "blue", "green", "blue"], ["blue", "red", "blue", "red", "green", "blue", "green", "blue"], ["blue", "red", "blue", "red", "blue", "green", "blue", "green"], ["blue", "red", "blue", "red", "blue", "green", "blue", "green"], ["blue", "red", "blue", "red", "blue", "green", "blue", "green"], ["blue", "red", "blue", "red", "blue", "green", "blue", "green"], ["blue", "red", "blue", "red", "green", "blue", "green", "blue"], ["blue", "red", "blue", "red", "green", "blue", "green", "blue"], ["blue", "red", "blue", "green", "red", "blue", "green", "blue"], ["blue", "red", "blue", "green", "red", "blue", "green", "blue"], ["blue", "red", "blue", "green", "blue", "green", "red", "blue"], ["blue", "red", "blue", "green", "blue", "green", "blue", "red"], ["blue", "red", "blue", "green", "blue", "red", "green", "blue"], ["blue", "red", "blue", "green", "blue", "red", "blue", "green"], ["blue", "red", "blue", "green", "blue", "green", "red", "blue"], ["blue", "red", "blue", "green", "blue", "green", "blue", "red"], ["blue", "red", "blue", "green", "blue", "red", "green", "blue"], ["blue", "red", "blue", "green", "blue", "red", "blue", "green"], ["blue", "red", "blue", "green", "red", "blue", "green", "blue"], ["blue", "red", "blue", "green", "red", "blue", "green", "blue"], ["blue", "red", "blue", "green", "blue", "red", "blue", "green"], ["blue", "red", "blue", "green", "blue", "red", "green", "blue"], ["blue", "red", "blue", "green", "blue", "green", "red", "blue"], ["blue", "red", "blue", "green", "blue", "green", "blue", "red"], ["blue", "red", "blue", "green", "blue", "red", "blue", "green"], ["blue", "red", "blue", "green", "blue", "red", "green", "blue"], ["blue", "red", "blue", "green", "blue", "green", "red", "blue"], ["blue", "red", "blue", "green", "blue", "green", "blue", "red"], ["blue", "red", "blue", "red", "green", "blue", "green", "blue"], ["blue", "red", "blue", "red", "green", "blue", "green", "blue"], ["blue", "red", "blue", "red", "blue", "green", "blue", "green"], ["blue", "red", "blue", "red", "blue", "green", "blue", "green"], ["blue", "red", "blue", "red", "blue", "green", "blue", "green"], ["blue", "red", "blue", "red", "blue", "green", "blue", "green"], ["blue", "red", "blue", "red", "green", "blue", "green", "blue"], ["blue", "red", "blue", "red", "green", "blue", "green", "blue"], ["blue", "red", "blue", "green", "red", "blue", "green", "blue"], ["blue", "red", "blue", "green", "red", "blue", "green", "blue"], ["blue", "red", "blue", "green", "blue", "green", "red", "blue"], ["blue", "red", "blue", "green", "blue", "green", "blue", "red"], ["blue", "red", "blue", "green", "blue", "red", "green", "blue"], ["blue", "red", "blue", "green", "blue", "red", "blue", "green"], ["blue", "red", "blue", "green", "blue", "green", "red", "blue"], ["blue", "red", "blue", "green", "blue", "green", "blue", "red"], ["blue", "red", "blue", "green", "blue", "red", "green", "blue"], ["blue", "red", "blue", "green", "blue", "red", "blue", "green"], ["blue", "red", "blue", "green", "red", "blue", "green", "blue"], ["blue", "red", "blue", "green", "red", "blue", "green", "blue"], ["blue", "red", "blue", "green", "blue", "red", "blue", "green"], ["blue", "red", "blue", "green", "blue", "red", "green", "blue"], ["blue", "red", "blue", "green", "blue", "green", "red", "blue"], ["blue", "red", "blue", "green", "blue", "green", "blue", "red"], ["blue", "red", "blue", "green", "blue", "red", "blue", "green"], ["blue", "red", "blue", "green", "blue", "red", "green", "blue"], ["blue", "red", "blue", "green", "blue", "green", "red", "blue"], ["blue", "red", "blue", "green", "blue", "green", "blue", "red"], ["blue", "red", "blue", "red", "green", "blue", "green", "blue"], ["blue", "red", "blue", "red", "green", "blue", "green", "blue"], …, ["green", "blue", "green", "blue", "red", "blue", "red", "blue"], ["green", "blue", "green", "blue", "red", "blue", "red", "blue"], ["green", "blue", "green", "blue", "red", "blue", "red", "blue"], ["green", "blue", "green", "blue", "red", "blue", "red", "blue"], ["green", "blue", "green", "blue", "red", "blue", "red", "blue"], ["green", "blue", "green", "blue", "red", "blue", "red", "blue"], ["green", "blue", "green", "blue", "red", "blue", "red", "blue"], ["green", "blue", "green", "blue", "red", "blue", "red", "blue"], ["green", "blue", "red", "blue", "red", "blue", "green", "blue"], ["green", "blue", "red", "blue", "red", "blue", "green", "blue"], ["green", "blue", "red", "blue", "green", "blue", "red", "blue"], ["green", "blue", "red", "blue", "green", "blue", "red", "blue"], ["green", "blue", "red", "blue", "red", "blue", "green", "blue"], ["green", "blue", "red", "blue", "red", "blue", "green", "blue"], ["green", "blue", "red", "blue", "green", "blue", "red", "blue"], ["green", "blue", "red", "blue", "green", "blue", "red", "blue"], ["green", "blue", "red", "blue", "red", "blue", "green", "blue"], ["green", "blue", "red", "blue", "red", "blue", "green", "blue"], ["green", "blue", "red", "blue", "green", "blue", "red", "blue"], ["green", "blue", "red", "blue", "green", "blue", "red", "blue"]]

最后,我只需要选择其中一种组合

let comb = combs[Int(arc4random_uniform(UInt32(combs.count)))]
// ["red", "blue", "green", "blue", "green", "blue", "red", "blue"]

改进

如果您不需要真正的随机解决方案,而只是一个没有2个连续相等元素的置换,我们可以更改前一个函数以返回第一个有效解.

func combination<Element:Equatable>(unusedElms: [Element], sequence:[Element] = []) -> [Element]? {
    guard !Array(zip(sequence.dropFirst(), sequence)).contains(==) else { return nil }
    guard !unusedElms.isEmpty else { return sequence }

    for i in 0..<unusedElms.count {
        var unusedElms = unusedElms
        let newElm = unusedElms.removeAtIndex(i)
        let newSequence = sequence + [newElm]
        if let solution = combination(unusedElms, sequence: newSequence) {
            return solution
        }
    }
    return nil
}

现在你可以简单地写

combination(["blue", "red", "green", "red", "blue", "blue", "blue", "green"])

获得有效的解决方案(如果确实存在)

["blue", "red", "green", "blue", "red", "blue", "green", "blue"]

这种方法可以更快(当解决方案确实存在时),但最坏的情况仍然是空间和时间复杂度的O(n!).

Answer 2

尽管表面上看，这并不是一件小事。正如评论员 @antonio081014 指出的那样，这实际上是一个算法问题，并且（正如 @MartinR 指出的那样）在这里得到解决。这是一个非常简单的启发式（与 @appzYourLife 的解决方案不同）不是一种算法，但在大多数情况下都有效，并且速度更快（O(n^2) 而不是 O(n!)）。为了获得随机性，只需首先对输入数组进行洗牌：

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"]