Consideraciones
Esta pregunta podría no tener solución dependiendo la naturaleza de los datos de entrada para la implementación que se va ha desarrollar en esta respuesta, pero los conceptos son útiles también en machine learning - ML
Lo anterior se debe a que en última instancia se busca permutar
los elementos de un vector, esto equivale a barajar los naipes (shuffle
el termino en inglés) o como un bingo o lotería extraer los números sin que estos vuelvan al ánfora (extracción sin reposición). Acá está más detallado Variables aleatorias discretas y graficar su función de probabilidad acumulada en R
Esto último R
base lo contempla con la función sample
.
Si los elementos fueran c(1,1,1,1,1,1)
, estadísticamente hablando no se estaría contraviniendo nada de lo mencionado anteriormente, pero como la restricción es que no sean iguales los elementos adyacentes... el modelo que se plantea no podría solucionarlo.
Función Sample
Supongamos que tenemos el siguiente vector y por un momento olvidemos la restricción de que los adyacentes sean iguales:
x <- c(1,2,3,1,3,4,5,6,7,8,4)
Digamos que sale 5
en nuestro sorteo... ya quedan 10
, sacamos otro y sale 2
nos quedan 9
... y así sucesivamente
Esto implica que no se van a reemplazar los elementos que se extraen, en tal sentido se puede emplear la función sample
de la siguiente forma:
a <- sample(x, replace=FALSE)
a # es una permutacion de x
# 3 4 4 1 3 2 8 5 7 1 6
Adyacentes diferentes
Observando la permutación 3 4 4 1 3 2 8 5 7 1 6
se evidencia que 4 4
no satisface la restricción de adyacentes diferentes.
Si se hiciera lo siguiente:
# a 3 4 4 1 3 2 8 5 7 1 6 (este ultimo '6' no entra en la resta)
# b(-) 4 4 1 3 2 8 5 7 1 6 (se desfasa en 1 el vector a y se omite el primero '3')
#-----------------------------------
# -1 0 3 -2 1 -6 3 -2 6 -5
El vector -1 0 3 -2 1 -6 3 -2 6 -5
contiene cero
y se verifica que los adyacentes son iguales. Por tal motivo descartamos esta permutación y buscamos otra hasta encontrar la que satisfaga la restricción de adyacentes diferentes....
Acá la implementación
x <- c(1,2,3,1,3,4,5,6,7,8,4)
x_len <- length(x)
check_zero <- TRUE
while (check_zero){
a <- sample(x, replace=FALSE)
b <- a[2:x_len] # el desfase de 1
print(a); print(b)
check_zero <- a[1:x_len-1] - b # el ultimo elemento de "a" no entra en la resta
print(check_zero)
check_zero <- 0 %in% check_zero # si el cero está los adyacentes son iguales
cat("Sí hay cero continua iteracion:", check_zero,"\n\n")
}
cat("\nResultado\n")
print(a)
Al correr el código de arriba se obtiene la siguiente posible permutación
# [1] 3 4 4 1 3 2 8 5 7 1 6
# [1] 4 4 1 3 2 8 5 7 1 6
# [1] -1 0 3 -2 1 -6 3 -2 6 -5
#Sí hay cero continua iteracion: TRUE
# [1] 7 3 4 4 2 5 1 3 8 6 1
# [1] 3 4 4 2 5 1 3 8 6 1
# [1] 4 -1 0 2 -3 4 -2 -5 2 5
#Sí hay cero continua iteracion: TRUE
# [1] 7 3 2 5 6 8 4 4 1 1 3
# [1] 3 2 5 6 8 4 4 1 1 3
# [1] 4 1 -3 -1 -2 4 0 3 0 -2
#Sí hay cero continua iteracion: TRUE
# [1] 7 1 3 5 3 1 2 4 4 8 6
# [1] 1 3 5 3 1 2 4 4 8 6
# [1] 6 -2 -2 2 2 -1 -2 0 -4 2
#Sí hay cero continua iteracion: TRUE
# [1] 7 4 1 6 4 2 5 8 3 1 3
# [1] 4 1 6 4 2 5 8 3 1 3
# [1] 3 3 -5 2 2 -3 -3 5 2 -2
#Sí hay cero continua iteracion: FALSE
#Resultado
# [1] 7 4 1 6 4 2 5 8 3 1 3
En este caso se hizo 5 sorteos y nos quedamos con el último 7 4 1 6 4 2 5 8 3 1 3
ya que la variable check_zero
hace que se quiebre o rompa (break
) el bucle while
cuando es falsa.
Datos de la pregunta
Si se ejecuta el código tal como está (podría re-factorizarse las condicionales por rango en lugar del operador "o" "||") el vector longlist<-c()
quedaría de la siguiente forma:
# [1] 1 1 1 1 1 1 1 1 1 1 1 1 10 10 10 10 10 10 10 10 10 10 10 10 2
# [26] 2 2 2 2 2 20 20 20 20 20 20 3 3 3 3 3 3 30 30 30 30 30 30 4 4
# [51] 4 4 4 4 40 40 40 40 40 40 5 5 5 5 5 5 50 50 50 50 50 50 6 6 6
# [76] 6 6 6 60 60 60 60 60 60 7 7 7 7 7 70 70 70 70 70 8 8 8 8 8 8
Si x <- longlist
para el código que se expuso con el bucle while
se pueden obtener por ejemplo las siguientes permutaciones que no contienen números adyacentes iguales.
# Una posible permutacion con números adyacentes diferentes
# [1] 2 1 2 70 7 1 60 8 50 40 10 5 10 1 60 6 1 4 8 5 1 4 70 1 20
# [26] 5 40 7 8 1 10 5 10 3 30 10 7 8 3 50 20 7 10 70 3 5 40 30 6 20
# [51] 50 4 20 10 40 2 4 1 8 3 1 2 20 30 10 50 40 60 50 60 40 1 30 3 30
# [76] 3 6 4 2 1 6 2 10 60 5 20 8 10 70 6 50 4 60 10 30 6 10 7 1 70
# Otra posible permutacion con números adyacentes diferentes
# [1] 4 1 40 5 20 60 2 10 20 5 70 50 4 1 10 4 1 2 4 50 4 5 7 3 70
# [26] 60 10 1 5 30 4 70 20 1 50 1 10 2 50 8 30 8 30 40 30 60 20 8 40 10
# [51] 60 7 6 1 7 5 7 6 3 30 6 8 10 3 40 30 10 20 1 10 1 20 8 6 2
# [76] 70 3 10 70 7 50 6 1 60 5 2 40 3 10 6 2 8 10 50 1 40 1 10 60 3
Pero como se mencionó al inicio dependerá de los datos de entrada y su tamaño para verificar que exista una permutación con números adyacentes diferentes.
Sobre complejidad
Existen algoritmos recursivos que dan todas las posibles combinaciones... inclusive en el proyecto euler problema 24 se pide hallar todas las permutaciones de 0 1 2 3 4 5 6 7 8 9
es:
print(factorial(10)) # 3628800 # mas de tres millones
Acá lo que se ha hecho es un muestreo de las posibles combinaciones de interés sin tener que generar todas las posibles permutaciones print(factorial(100)) # 9.332622e+157
este concepto se emplea en minibatch para entrenamiento de machine learning (aprendizaje automático - AA) así como las permutaciones como tal a una base de datos (específicamente a sus indices) en dicha área.
Las aplicaciones prácticas en Aprendizaje Automático me hicieron contestar esta pregunta que al día de hoy lleva casi 4 años formulada.