File contents

# TRABAJO PRÁCTICO Nº 1

# EQUIPO: Genoud Villafañe, Andrés Gerard, Milian Gannon, Alen, Zylberstein, Mat??as.

# ORDEN MÁXIMO.

# La función ordMax devuelve el orden máximo de una permutación perm.

# El algoritmo consiste en recorrer el vector que representa a la permutación, al tiempo que almacena en dos vectores
# auxiliares, listaCadena y listaOrden, información pertinente al objetivo. En listaCadena se guarda el máximo de cada
# cadena consecutiva creciente recorrida hasta el momento, mientras que en listaOrden se graban las longitudes
# respectivas de las mismas. Al finalizar el recorrido de perm, se devuelve la entrada máxima de listaOrden.

ordMax = function(perm){

  # Se inicializan las variables auxiliares.
  contador = 2
  listaCadena = c()
  listaOrden = c()
  
  for (e in perm){                  # Este ciclo es el encargado de recorrer la permutación.
    
    if (length(listaCadena) == 0){  # Verifica si es el primer paso del recorrido; si es as??, inicia una nueva cadena, y actualiza 
                                    # listaCadena y listaOrden acorde.
      
      listaCadena[1] = e            
      listaOrden[1] = 1             
      
    } else {
      
      i = which(listaCadena == e-1)  # Sino, verifica si alguna de las cadenas ya identificadas tiene como máximo a e - 1.
      
      if (length(i)==0){          #Si es as??, inicia una nueva cadena de primer elemento e, y actualiza listaCadena y 
                                  # listaOrden acorde.
        listaCadena[contador] = e    
        listaOrden[contador] = 1     
        contador = contador + 1
        
      } else {                    # Si existe dicha cadena, se actualiza su máximo valor y longitud, en listaCadena y listaOrden.
        
        listaCadena[i] = e      
        listaOrden[i] = listaOrden[i] + 1 
        
      }
    }
  }
  
  return(max(listaOrden)) # Devuelve el máximo entre las longitudes de todas las cadenas consecutivas crecientes de la permutación.
}

# RIFFLE SHUFFLE.

# La función riffle_shuffle permuta los elementos del vector mazo, de acuerdo al modelo adoptado del 'riffle shuffle'. Se particiona
# a mazo en dos tramos, con punto de corte a determinar por la realización de una variable binomial de parámetros (length(mazo), n).
# Se selecciona de manera aleatoria posiciones para las cartas de ambos tramos, y se actualiza el vector mazo en consecuencia.

riffle_shuffle = function(mazo){
  
  n = length(mazo)
  
  k = rbinom(1,n,1/2) # Punto de corte.
  
  # Se corta en dos 'mitades'.
  sub_mazo1 = mazo[1:k] 
  sub_mazo2 = mazo[(k + 1) : n]
  
  # Nuevas posiciones para las k cartas de sub_mazo1. Se las ordena para representar fielmente el hecho de que las posiciones
  # relativas de las cartas en cada submazo se mantiene después del entremezclado.
  nuevos_lugares = sort(sample(c(1:n), k, replace = FALSE))
  
  # Las posiciones para las cartas de su_mazo2 son el complemento de las anteriores, de nuevo, en orden.
  nuevos_lugares_comp = sort(setdiff(c(1:n), nuevos_lugares))
  
  # Se reubican las cartas de sub_mazo1.
  for (i in 1:k){
    
    r = nuevos_lugares[i]
    mazo[r] = sub_mazo1[i]
    
  }
  
  # Se reubican las cartas de sub_mazo2.
  for (j in 1 : (n-k)){
    
    r = nuevos_lugares_comp[j]
    mazo[r] = sub_mazo2[j]
    
  }
  
  return(mazo)
}

# SIMULACIÓN 1.

# En la primera simulación, se busca aproximar la esperanza y el desvío estándar del orden máximo de una permutación
# elegida al azar, para un mazo de 52 cartas.

# Se generan 100000 permutaciones y se calcula el orden máximo de cada una de ellas con ordMAx. El resultado es
# almacenado en el vector casos. Finalmente, se realizan las aproximaciones deseadas con los comandos mean y sd.

set.seed(1)
n = 100000
casos = rep(0, n)

for (i in 1:n){
  p = sample(1:52,52)
  o = ordMax(p)
  casos[i] = o
}

esp1 = mean(casos)
desv1 = sd(casos)
print(paste("Valor esperado: ",mean(casos)))
print(paste("Desvio estandar: ",sd(casos)))

# SIMULACIÓN 2.

# En la segunda simulación, se busca aproximar la esperanza y el desv??o estándar del orden máximo de un mazo,
# inicialmente ordenado, que ha sido mezclado i veces, de acuerdo al programa riffle_shuffle.

# Para cada i entre 1 y 20, se baraja el mazo i veces, en 1000 experimentos. Se almacena el orden máximo de cada
# permutación resultante en el vector casos, y finalmente se aproxima con el uso de los comandos mean y sd. Los datos son
# guardados en los vectores esp y desv.

# La simulación imprime dos vectores: esp2 y desv2. En la coordenada i-ésima, aparecen la esperanza y desvío estándar,
# respectivamente, del orden máximo del mazo que ha sido mezclado i veces.

esp2 = c()
desv2 = c()
n = 1000
iota = c(1:20)

for (i in iota) {
  
  casos = rep(0, n)
  
  for (j in 1:n) {
    
    mazo = c(1:52)
    
    for (k in 1:i) {
      
      mazo = riffle_shuffle(mazo)
      
    }
    
    casos[j] = ordMax(mazo)
    
  }
  
  esp2[i] = mean(casos)
  desv2[i] = sd(casos)
  
}

print(esp2)
print(desv2)

# GRÁFICO

# Se presentan los datos obtenidos para las esperanzas en ambas simulaciones. 

plot(iota,esp2,col = "blue",ylim = c(3,29), main = "Esperanza del orden maximo(OM) vs. Cantidad de mezclas", xlab = "Cantidad de mezclas" , ylab = "Esperanza del orden maximo")
abline(h = esp1, col = 'red')
abline(h = esp1 + desv1, lty = 2)
abline(h = esp1 - desv1, lty = 2)

legend('topright', c("Mazo ordenado","Esperanza del OM de mazos aleatorios","Intervalo de aceptacion"), col = c('blue','red','black'),pch = c(1,NA,NA), lty = c(NA,1,2))