有没有办法打乱一个数组，使得没有两个连续的值是相同的？

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

Disclaimer: In order to generate a "random" solution I am going to use backtracking. This approach is NOT fast and is NOT cheap by a space point of view.

Infact both Time And Space Complexity are O(n!)... and this is HUGE!

However it gives you a valid solution as random as possible.

回溯

所以你想要一个值列表的随机组合，条件是如果没有 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 个连续相等元素的排列，我们可以更改之前的函数以 return 第一个有效解。

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

This approach can be much faster (when the solution does exist) however the worst case scenario is still O(n!) for both space and time complexity.

Answer 2

尽管表面上看起来很重要，但这并不简单。正如评论员@antonio081014 指出的那样，它实际上是一个算法问题，并且（正如@MartinR 指出的那样）已解决here。这是一个非常简单的 heuristic（与@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"]

Answer 3

O(N) 时间和 space 解决方案

我从图片开始，因为它总是更有趣:)

简介

首先，我想指出你不能有一个均匀分布的序列，因为在你的情况下颜色的数量是不一样的。

要回答如何生成随机序列让我们从最简单的情况开始。

所有颜色都是唯一的，你从1 - N生成一个随机值，取出颜色，从1 - (N-1)生成等等。

现在，有一些颜色比其他颜色多，你做的事情和以前的方法一样，但现在每种颜色出现的概率不同 - 如果你有更多黑色它的概率更高。

现在，在你的情况下你有确切的情况，但有一个额外的要求 - 当前的随机颜色不等于以前的 。所以，只要在生成每种颜色时应用这个要求——就随机性而言，这将是最好的。

示例

比如你总共有4种颜色：

黑色：2；
红色: 1;
绿色：1.

首先想到的步骤如下：

将它们排成一行 B B R G;
随机选择一个，例如：B，去掉所有相同的颜色，保证下一个颜色不同。现在你有 R G;
选择下一个随机的，例如R，去掉所有相同的颜色，带上所有与现在可供选择的先前颜色相同的颜色。在此步骤中，您最终得到 B G.
等等...

但是错了。请注意，在步骤 3 中，黑色和绿色出现的概率相似（B G - 要么是黑色要么是绿色），而在开始时黑色出现的概率更大。

为避免这种情况，请使用颜色箱。垃圾箱具有宽度（概率）和其中保留的颜色数量。宽度永远不会改变，并在启动时设置。

所以正确的步骤是：

创建 3 个 bean 并将它们放在一行中：
- 黑色：0.5，数量：2；
- 红色：0.25，数量：1；
- 绿色：0.25，数量：1。
从 0.0 <-> 1.0 范围内生成一个随机数。例如，它是 0.4，表示黑色（例如，0.9 表示绿色）。之后，如果你不能在这一步选择黑色，你的选择是：
- 红色：0.25，数量：1；
- 绿色：0.25，数量：1。
由于您选择了宽度为 0.5 的黑色 bin，因此生成范围为 0.0 <-> (1.0 - 0.5) =0.0 <-> 0.5 的随机数。设为0.4，即红色。
去掉红色 (-0.25)，但带回黑色 (+0.5)。在这一步你有：
- 黑色：0.5，数量：1；
- 绿色：0.25，数量：1。
下一个随机值的范围是0.0 <-> (0.5 - 0.25 + 0.5) =0.0 <-> 0.75。请注意，与之前的方法相比，颜色保留了它的起始概率（黑色有更大的概率）。

算法的时间复杂度是O(N)，因为你做的工作量是一样的O(1)（选择一个随机的bin，排除它，包括前一个）是你拥有的颜色数量的倍数 O(N).

我应该注意的最后一件事 - 因为它是一种概率方法，所以最大 bin 的一些颜色可能会留在算法的末尾。在这种情况下，只需遍历最终的颜色列表并将它们放在合适的位置（在与它不同的颜色之间）。

也有可能没有这样的颜色排列，因此没有两种相同的颜色相邻（例如：黑色 - 2，红色 - 1）。对于这种情况，我在下面的代码中抛出异常。

算法结果的示例在开头的图片中。

代码

Java (Groovy).

注意，为了便于阅读，从列表中删除元素是标准的 (bins.remove(bin))，即 Groovy 中的 O(N) 操作。因此，该算法总共不起作用 O(N)。删除应重写为将列表的最后一个元素更改为要删除的元素并递减列表的 size 属性 - O(1).

Bin {
    Color color;
    int quantity;
    double probability;
}

List<Color> finalColors = []
List<Bin> bins // Should be initialized before start of the algorithm.
double maxRandomValue = 1

private void startAlgorithm() {
    def binToExclude = null

    while (bins.size() > 0) {
        def randomBin = getRandomBin(binToExclude)
        finalColors.add(randomBin.color)

        // If quantity = 0, the bin's already been excluded.
        binToExclude = randomBin.quantity != 0 ? randomBin : null

        // Break at this special case, it will be handled below.
        if (bins.size() == 1) {
            break
        }
    }

    def lastBin = bins.get(0)
    if (lastBin != null) {
        // At this point lastBin.quantity >= 1 is guaranteed.
        handleLastBin(lastBin)
    }
}

private Bin getRandomBin(Bin binToExclude) {
    excludeBin(binToExclude)

    def randomBin = getRandomBin()

    randomBin.quantity--
    if (randomBin.quantity == 0) {
        excludeBin(randomBin)
    }

    includeBin(binToExclude)

    return randomBin
}

private Bin getRandomBin() {
    double randomValue = randomValue()

    int binIndex = 0;
    double sum = bins.get(binIndex).probability
    while (sum < randomValue && binIndex < bins.size() - 1) {
        sum += bins.get(binIndex).probability;
        binIndex++;
    }

    return bins.get(binIndex)
}

private void excludeBin(Bin bin) {
    if (bin == null) return

    bins.remove(bin)
    maxRandomValue -= bin.probability
}

private void includeBin(Bin bin) {
    if (bin == null) return

    bins.add(bin)
    def addedBinProbability = bin.probability

    maxRandomValue += addedBinProbability
}

private double randomValue() {
    return Math.random() * maxRandomValue;
}

private void handleLastBin(Bin lastBin) {
    // The first and the last color're adjacent (since colors form a circle),
    // If they're the same (RED,...,RED), need to break it.
    if (finalColors.get(0) == finalColors.get(finalColors.size() - 1)) {
        // Can we break it? I.e. is the last bin's color different from them?
        if (lastBin.color != finalColors.get(0)) {
            finalColors.add(lastBin.color)
            lastBin.quantity--
        } else {
            throw new RuntimeException("No possible combination of non adjacent colors.")
        }
    }

    // Add the first color to the other side of the list
    // so that "circle case" is handled as a linear one.
    finalColors.add(finalColors.get(0))

    int q = 0
    int j = 1
    while (q < lastBin.quantity && j < finalColors.size()) {
        // Doesn't it coincide with the colors on the left and right?
        if (finalColors.get(j - 1) != lastBin.color && finalColors.get(j) != lastBin.color) {
            finalColors.add(j, lastBin.color)
            q++
            j += 2
        }  else {
            j++
        }
    }
    // Remove the fake color.
    finalColors.remove(finalColors.size() - 1)

    // If still has colors to insert.
    if (q < lastBin.quantity) {
        throw new RuntimeException("No possible combination of non adjacent colors.")
    }
}

Answer 4

GameplayKit 中的 GKShuffledDistribution class 有两个功能可以很容易地满足这个要求：

它从它初始化的范围中抽取“随机”数字，这样它必须在重复其中任何一个之前使用该范围内的所有数字。

单独使用时，此行为会在随机序列中创建“块”（因为缺少更好的词）。例如，如果您有 4 个可能的值，则前四个 nextInt() 调用将耗尽所有四个值。但是在第五次调用时，你在一个新的“块”上，你将能够再次随机获取 4 个值中的任何一个，包括最后一个“块”的最终值。
因此，GKShuffledDistribution 还确保没有任何跨“块”边界的重复。

通过在操场上尝试以下操作并显示 nextInt() 行的值图表，您可以很容易地看到这一点：

import GameplayKit

let colors = ["red", "green", "blue"
// the effect is easier to see with more than three items, so uncomment for more:
//    , "mauve", "puce", "burnt sienna", "mahogany",
//    "periwinkle", "fuschia", "wisteria", "chartreuse"
]

let randomizer = GKShuffledDistribution(lowestValue: 0, highestValue: colors.count - 1)
for _ in 1...100 {
    randomizer.nextInt()
}

或使用更多颜色：

您会注意到某些值会重复，中间会跳过（请注意第二张图中早期 11, 10, 11 的顺序），但绝不会连续重复一个值。

要使用它来打乱一组颜色，只需从打乱的索引开始：

extension GKShuffledDistribution {
    func shuffledInts(count: Int) -> [Int] {
        // map on a range to get an array of `count` random draws from the shuffle
        return (0..<count).map { _ in self.nextInt() }
    }
}

let colors = [#colorLiteral(red: 1, green: 0, blue: 0, alpha: 1), #colorLiteral(red: 0, green: 1, blue: 0, alpha: 1), #colorLiteral(red: 0, green: 0, blue: 1, alpha: 1)]
let random = GKShuffledDistribution(forDieWithSideCount: colors.count)
let dieRolls = random.shuffledInts(count: 10)
let shuffledColors: [SKColor] = dieRolls.map { num in
    // forDieWithSideCount gives us values between 1 and count
    // we want values betwen 0 and (count-1)
    return colors[num - 1]
}

（在这个例子中还展示了一些其他的东西：使用颜色文字而不是颜色名称，尽管你也可以这样做，并且使用 dieWithSideCount 初始值设定项 GKShuffledDistribution。请注意，颜色文字在 Xcode 中看起来比在 SO 中的网络上好看得多。）

有没有办法打乱一个数组，使得没有两个连续的值是相同的？

Is there a way to shuffle an array so that no two consecutive values are the same?

random

distribution

swift

回溯

改进

O(N) 时间和 space 解决方案

简介

示例

代码