Is there a way to shuffle an array so that no two

问题:

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

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    
}

UPDATE:

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")
    }
}

Which ends up spitting out:

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

回答1:

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

回答2:

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.

Backtracking

So you want a random combination of a list of values with the condition that the solution is valid if there are not be 2 consecutive equals elements.

In order to have a real random solution I suggest the following approach.

I generate every possible valid combination. For this I'm using a backtracking approach

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
}

Now given a list of colors

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

I can generate every valid possible combination

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

Finally I just need to pick one of these combinations

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

Improvements

If you don't need a true random solution, but simply a permutation that doesn't have 2 consecutive equal elements we can change the previous function in order to return the first valid solution.

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
}

Now you can simply write

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

to get a valid solution (if it does exists)

["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.

回答3:

O(N) time and space solution

I've started with images as it's always more interesting :)

Introduction

First, I want to note you can't have a uniformly distributed sequence, since in your case quantities of colors are not the same.

To answer how to generate a random sequence let's go from the simplest case.

Having all colors unique, you generate a random value from 1 - N, take the color out, generate from 1 - (N-1) an so forth.

Now, having some colors more than others, you do the same thing as in the previous approach, but now probabilities of each color to appear differ - if you have more of black color its probability is higher.

Now, in your case you have the exact case, but with an additional requirement - the current random color doesn't equal to the previous one. So, just apply this requirement when generating each color - it'll be the best in terms of randomness.

Example

For example, you have 4 colors in total:

• black: 2;
• red: 1;
• green: 1.

The first sequence of steps that comes to mind is the following:

1. Place them in one line B B R G;
2. Choose a random one, for example: B, take away all the same colors so the next is guaranteed to be different. Now you have R G;
3. Choose a next random one, for example R, take away all the same colors, bring all the same colors of the previous color as it's now available for choice. At this step you end up with B G.
4. Etc...

But it's wrong. Note, at the step 3 the colors black and green have similar probability to appear (B G - it's either black or green), whereas at the beginning black had a bigger probability.

To avoid this, use bins of colors. Bins has width (probability) and quantity of colors remained in it. The width never changes and is set at the startup.

So proper steps are:

1. Create 3 beans and place them in one line:
   • black: 0.5, quantity: 2;
   • red: 0.25, quantity: 1;
   • green: 0.25, quantity: 1.
2. Generate a random number from the range 0.0 <-> 1.0. For example it's 0.4, which means black (0.9, for example, would mean green). After that, provided you can't pick black color at this step, the choice you have is:
   • red: 0.25, quantity: 1;
   • green: 0.25, quantity: 1.
3. Since you've taken the black bin of width 0.5, generate a random number from the range 0.0 <-> (1.0 - 0.5) =0.0 <-> 0.5. Let it be 0.4, i.e. red.

4. Take red away (-0.25), but bring black color back (+0.5). At this step you have:

   • black: 0.5, quantity: 1;
   • green: 0.25, quantity: 1.

   And the range for the next random value is 0.0 <-> (0.5 - 0.25 + 0.5) =0.0 <-> 0.75. Note that colors preserved its starting probabilities (black has a bigger one), in comparison to the previous approach.

The algorithm is O(N) in time complexity, because you do the same amount of work O(1) (choose a random bin, exclude it, include the previous one) as many times as many colors you have O(N).

The last thing I should note - since it's a probabilistic approach, a few colors of the biggest bin may be left at the end of the algorithm. In this case just iterate over the final list of colors and place them in suitable places (between colors both different from it).

And it's also possible that there's no such arrangement of colors so that no two same colors are adjacent (for example: black - 2, red - 1). For such cases I throw an exception in the code below.

The example of a result of the algorithm is present in the pictures at the beginning.

Code

Java (Groovy).

Note, for readability deletion of an element from a list is left standard (bins.remove(bin)) which is O(N) operation in Groovy. Therefore the algorithm doesn't work O(N) in total. Deletion should be rewritten as changing the last element of the list with the element to be deleted and decrementing the size property of the list - 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.")
    }
}

回答4:

The GKShuffledDistribution class in GameplayKit has two features that should make fulfilling this requirement pretty easy:

1. It draws "random" numbers from the range it's initialized with in such a way that it must use all the numbers in that range before repeating any one of them.

   Alone, this behavior creates "chunks" (for lack of a better word) in the random sequence. For example, if you have 4 possible values, the first four nextInt() calls would exhaust all four of them. But on the fifth call you're on a new "chunk", you'd be able to randomly get any of the 4 values again, including the final value from the last "chunk".

2. So, GKShuffledDistribution also makes sure that there aren't any repeats across "chunk" boundaries.

You can see this pretty easy by trying the following in a playground, and showing a value graph for the nextInt() line:

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()
}

Or with more colors:

You'll notice that some values get repeated with a skip in between (note the sequence of 11, 10, 11 early on in the second graph), but never is one value repeated consecutively.

To use this to shuffle an array of colors, just work from a shuffled index:

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

(Also showing a couple of other things in this example: using color literals instead of color names, though you could just as well do either, and using the dieWithSideCount initializer for GKShuffledDistribution. Note that color literals look a lot nicer in Xcode than on the web in SO.)