swift - trucos - spring de cartas
¿Hay alguna manera de barajar una matriz para que no haya dos valores consecutivos iguales? (4)
Descargo de responsabilidad: con el fin de generar una solución "aleatoria" , voy a utilizar el rastreo retroactivo. Este enfoque NO es rápido y NO es barato desde el punto de vista espacial.
De hecho, tanto la complejidad del tiempo como del espacio son O (n!) ... ¡y esto es ENORME!
Sin embargo, le ofrece una solución válida lo más aleatoria posible .
Retroceder
Por lo tanto, desea una combinación aleatoria de una lista de valores con la condición de que la solución sea válida si no hay dos elementos equivalentes consecutivos.
Para tener una solución aleatoria real, sugiero el siguiente enfoque.
Genero todas las combinaciones válidas posibles. Para esto estoy usando un enfoque de retroceso
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
}
Ahora dada una lista de colores
let colors = ["blue", "red", "green", "red", "blue", "blue", "blue", "green"]
Puedo generar todas las combinaciones posibles válidas
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"]]
Finalmente, solo necesito elegir una de estas combinaciones
let comb = combs[Int(arc4random_uniform(UInt32(combs.count)))]
// ["red", "blue", "green", "blue", "green", "blue", "red", "blue"]
Mejoras
Si no necesita una verdadera solución aleatoria , sino simplemente una permutación que no tiene 2 elementos iguales consecutivos, podemos cambiar la función anterior para devolver la primera solución válida.
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
}
Ahora puedes simplemente escribir
combination(["blue", "red", "green", "red", "blue", "blue", "blue", "green"])
para obtener una solución válida (si existe)
["blue", "red", "green", "blue", "red", "blue", "green", "blue"]
Este enfoque puede ser mucho más rápido (cuando existe la solución); sin embargo, el peor de los casos sigue siendo O (n!) Para la complejidad espacial y temporal.
Tengo una variedad de colores que rellenarán un gráfico circular para actuar como un juego giratorio. No quiero que los mismos colores aparezcan uno al lado del otro, formando un gran trozo en el círculo.
Mi matriz se parece a esto:
var colors = ["blue", "red", "green", "red", "blue", "blue", "blue", "green"]
El problema es, por supuesto, que hay tres blues juntos. ¿Hay algo incorporado en Swift que me permita distribuir por igual (o lo más cerca posible) los valores distribuidos dentro de la distribución total y evitar que sean adyacentes?
Puedo probar una coincidencia con el siguiente código, pero reorganizarlos resulta ser un poco más difícil.
var lastColor = "white"
for color in colors {
if color == lastColor {
print("match")
}
lastColor = color
}
ACTUALIZAR:
Para hacer mi matriz de colors , comienzo con la cantidad de espacios para cada color. Se ve algo como esto:
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")
}
}
Lo que termina escupiendo:
colors = ["red", "green", "blue", "red", "green", "blue", "blue", "blue" ]
O (N) solución de tiempo y espacio
Empecé con imágenes, ya que siempre es más interesante :)
Introducción
Primero, quiero señalar que no se puede tener una secuencia uniformemente distribuida, ya que en su caso las cantidades de colores no son las mismas.
Para responder a cómo generar una secuencia aleatoria, vamos desde el caso más simple .
Teniendo todos los colores únicos , genere un valor aleatorio de 1 - N , elimine el color, genere desde 1 - (N-1) y así sucesivamente.
Ahora, teniendo más colores que otros , haces lo mismo que en el enfoque anterior, pero ahora las probabilidades de cada color son diferentes: si tienes más de color negro, la probabilidad es mayor.
Ahora, en su caso tiene el caso exacto, pero con un requisito adicional: el color aleatorio actual no es igual al anterior . Entonces, solo aplica este requisito al generar cada color: será el mejor en términos de aleatoriedad.
Ejemplo
Por ejemplo, tienes 4 colores en total:
- negro: 2;
- rojo: 1;
- verde: 1.
La primera secuencia de pasos que viene a la mente es la siguiente:
- Colóquelos en una línea
BBRG; - Elija uno al azar, por ejemplo:
B, quite todos los mismos colores, por lo que se garantiza que el siguiente será diferente. Ahora tienesRG; - Elija uno al azar siguiente, por ejemplo
R, quite todos los mismos colores, traiga todos los mismos colores del color anterior, ya que está disponible para su elección. En este paso, terminas conBG. - Etc ...
Pero está mal . Tenga en cuenta que, en el paso 3, los colores negro y verde tienen una probabilidad similar de aparecer ( BG : es negro o verde), mientras que al principio el negro tiene una mayor probabilidad.
Para evitar esto, usa contenedores de colores. Los contenedores tienen ancho (probabilidad) y cantidad de colores que permanecen en él. El ancho nunca cambia y se establece al inicio.
Entonces, los pasos correctos son :
- Crea 3 frijoles y colócalos en una línea:
- negro: 0.5, cantidad: 2;
- rojo: 0.25, cantidad: 1;
- verde: 0.25, cantidad: 1.
- Genere un número aleatorio del rango
0.0 <-> 1.0. Por ejemplo, es 0.4, lo que significa negro (0.9, por ejemplo, significa verde). Después de eso, siempre que no pueda elegir color negro en este paso, la elección que tiene es:- rojo: 0.25, cantidad: 1;
- verde: 0.25, cantidad: 1.
- Como ha tomado el contenedor negro de ancho 0.5, genere un número aleatorio del rango
0.0 <-> (1.0 - 0.5) =0.0 <-> 0.5. Deje que sea 0.4, es decir, rojo. Quite el rojo (
-0.25), pero traiga el color negro hacia atrás (+0.5). En este paso tienes:- negro: 0.5, cantidad: 1;
- verde: 0.25, cantidad: 1.
Y el rango para el siguiente valor aleatorio es
0.0 <-> (0.5 - 0.25 + 0.5) =0.0 <-> 0.75. Tenga en cuenta que los colores preservaron sus probabilidades iniciales (el negro tiene una mayor), en comparación con el enfoque anterior.
El algoritmo es O(N) en la complejidad del tiempo , porque usted hace la misma cantidad de trabajo O(1) (elija un bin al azar, excluya, incluya el anterior) tantas veces como tantos colores tenga O(N) .
Lo último que debo señalar es que, dado que se trata de un enfoque probabilístico, al final del algoritmo pueden quedar algunos colores del contenedor más grande. En este caso, solo itere sobre la lista final de colores y colóquelos en lugares adecuados (entre colores diferentes de él).
Y también es posible que no haya una disposición de colores tal que no haya dos colores iguales adyacentes (por ejemplo: negro - 2, rojo - 1). Para tales casos arrojo una excepción en el código a continuación.
El ejemplo de un resultado del algoritmo está presente en las imágenes al principio.
Código
Java (Groovy).
Tenga en cuenta que para la legibilidad, la eliminación de un elemento de una lista se deja estándar ( bins.remove(bin) ) que es una operación O(N) en Groovy. Por lo tanto, el algoritmo no funciona O(N) en total. La eliminación se debe volver a escribir como si se cambiara el último elemento de la lista con el elemento que se eliminará y se redujera la propiedad de size de la lista: 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.")
}
}
La clase GKShuffledDistribution en GameplayKit tiene dos características que deberían hacer que cumplir este requisito sea bastante fácil:
Dibuja números "aleatorios" del rango con el que se inicializa de tal forma que debe usar todos los números en ese rango antes de repetir cualquiera de ellos.
Solo, este comportamiento crea "trozos" (por falta de una palabra mejor) en la secuencia aleatoria. Por ejemplo, si tiene 4 valores posibles, las primeras cuatro llamadas
nextInt()agotarían a los cuatro. Pero en la quinta llamada se encuentra en un nuevo "bloque", podrá obtener aleatoriamente cualquiera de los 4 valores nuevamente, incluido el valor final del último "fragmento".Entonces,
GKShuffledDistributiontambién se asegura de que no haya repeticiones en los límites del "fragmento".
Puede ver esto bastante fácil probando lo siguiente en un patio de recreo, y mostrando un gráfico de valores para la línea 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()
}
Notará que algunos valores se repiten con un salto intermedio (observe la secuencia de 11, 10, 11 comienzo del segundo gráfico), pero nunca se repite un valor de forma consecutiva.
Para usar esto para mezclar una matriz de colores, solo trabaje desde un índice mezclado:
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]
}
(También muestra un par de otras cosas en este ejemplo: usar literales de color en lugar de nombres de colores, aunque también podría hacer cualquiera de las dos cosas, y usar el inicializador GKShuffledDistribution para GKShuffledDistribution . Tenga en cuenta que los literales de color se ven mucho mejor en Xcode que en el web en SO.)
A pesar de las apariencias, esto no es trivial. Como señala el comentarista @ antonio081014, en realidad es una pregunta algorítmica, y (como señala @MartinR) se trata aquí . Aquí hay una heurística muy simple que (a diferencia de la solución de @appzYourLife) no es un algoritmo, pero funcionará en la mayoría de los casos, y es mucho más rápido (O (n ^ 2) en lugar de O (n!)). Para aleatoriedad, simplemente mezcle primero la matriz de entrada:
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"]