Ответ 1

Несмотря на внешность, это нетривиально. Как отмечает комментатор @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"]

Ответ 2

Отказ от ответственности: для генерации "случайного" решения я собираюсь использовать обратное отслеживание. Этот подход НЕ быстро и НЕ дешево с точки зрения пространства.

Infact and Time Complex - это O (n!)... и это ОГРОМНОЕ!

Однако он дает вам действительное решение как можно более случайным.

Откат

Итак, вам нужна случайная комбинация списка значений с условием, что решение допустимо, если не существует двух последовательных равных элементов.

Чтобы иметь реальное случайное решение, я предлагаю следующий подход.

Я генерирую каждую возможную комбинацию действительная. Для этого я использую подход backtracking

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!) для сложности пространства и времени.

Ответ 3

O (N) временное и пространственное решение

Я начал с изображений, поскольку это всегда более интересно:)

Введение

Во-первых, я хочу отметить, что вы не можете иметь равномерно распределенную последовательность, поскольку в вашем случае количество цветов не совпадает.

Чтобы ответить, как создать случайную последовательность , отпустите простейший случай.

Имея все уникальные цвета, вы генерируете случайное значение из 1 - N, выбираете цвет, генерируете из 1 - (N-1) и т.д.

Теперь , имеющий несколько цветов больше других, вы делаете то же самое, что и в предыдущем подходе, но теперь вероятность появления каждого цвета различается - если у вас больше черного цвета, то его вероятность выше.

Теперь в вашем случае у вас есть точный случай, но с дополнительным требованием - текущий текущий случайный цвет не соответствует предыдущему. Таким образом, просто примените это требование при генерации каждого цвета - оно будет лучшим с точки зрения случайности.

Пример

Например, у вас всего 4 цвета:

• черный: 2;
• красный: 1;
• зеленый: 1.

Первая последовательность шагов, которая приходит на ум, следующая:

• Поместите их в одну строку B B R G;
• Выберите случайный, например: B, заберите все одинаковые цвета, чтобы следующий, как гарантируется, был другим. Теперь у вас есть R G;
• Выберите следующий случайный, например R, заберите все одинаковые цвета, принесите все те же цвета предыдущего цвета, которые теперь доступны для выбора. На этом этапе вы получите B G.
• Etc...

Но это неправильно. Обратите внимание, что на шаге 3 цвета, черные и зеленые, имеют сходную вероятность появления (B G - это либо черный, либо зеленый), тогда как вначале черные имели большую вероятность.

Чтобы избежать этого, используйте бункеры цветов. Бункеры имеют ширину (вероятность) и количество цветов в ней. Ширина никогда не изменяется и устанавливается при запуске.

Итак правильные шаги:

• Создайте 3 beans и поместите их в одну строку:
  • черный: 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, создайте случайное число из диапазона 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) (выберите случайную ячейку, исключите ее, включите предыдущую) столько раз, сколько цвета у вас есть O(N).

Последнее, что я должен отметить - так как это вероятностный подход, в конце алгоритма может остаться несколько цветов самого большого бина. В этом случае просто перебирайте окончательный список цветов и размещайте их в подходящих местах (между цветами, отличными от него).

И также возможно, что нет такого расположения цветов, чтобы не было соседних двух одинаковых цветов (например: черный - 2, красный - 1). В таких случаях я делаю исключение в коде ниже.

Пример результата алгоритма присутствует в изображениях в начале.

код

Java (Groovy).

Примечание. Для удобства чтения элемент из списка остается стандартным (bins.remove(bin)), который является O(N) операцией в Groovy. Поэтому алгоритм не работает 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 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 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

GKShuffledDistribution класс в GameplayKit имеет две функции, которые должны сделать выполнение этого требования довольно простым:

• Он рисует "случайные" числа из диапазона, который он инициализировал таким образом, чтобы он должен использовать все числа в этом диапазоне перед повторением любого из них.

  В одиночку это поведение создает "куски" (из-за отсутствия лучшего слова) в случайной последовательности. Например, если у вас есть 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.)