0

Me preguntaba qué algoritmos o enfoques existen para poder resolver el siguiente problema.

Teniendo dos arrays (código en Python):

arr_start = [1,2,3,4,5,6]
arr_finish = [5,3,6,1,4,2]

Y declarando algunas funciones específicas como estas dos, donde la primera corta la matriz en el n-ésimo elemento como si cortara una baraja de cartas y la segunda realiza una mezcla faro (que es una mezcla perfecta de las cartas, cartas mezcladas una a una):

def cut_arr(n,arr):
r=[1]*len(arr)
for i in range(len(arr)):
    if (i+n)<len(arr):
        r[i] = arr[i+n]
    else:
        r[i] = arr[i+n-len(arr)]
return r


def faro_shuffle(arr):
r = []

for (a, b) in zip(arr[0:3], arr[3:]):
    r.append(a)
    r.append(b)
arr = r
return r

El objetivo del algoritmo sería encontrar cuántas veces y cuáles de las funciones declaradas tenemos que usar para ir de arr_start a arr_finish identificando el camino más corto.

En este ejemplo, el algoritmo que estoy pidiendo nos diría que hagamos una mezcla faro y luego cortaría la matriz en el tercer elemento, obteniendo arr_finish a partir de arr_start.

arr1 = faro_shuffle(arr_start)
cut_arr(3,arr1)

Output: [5,3,6,1,4,2]

El objetivo en el futuro sería trabajar con arrays más largos y declarar más funciones.

6
  • Esto parece un ejercicio. Cual es la pregunta concreta, que no sea hacer el ejercicio?
    – gbianchi
    Commented el 9 ene. 2020 a las 12:28
  • El ejemplo puesto es para intentar explicar qué es lo que haría el algoritmo que estoy buscando. La pregunta concreta es si existen algoritmos y cuáles son que resuelvan este problema (ir de un orden de un array a otro orden de un array usando funciones específicas que le digamos).
    – sarasataco
    Commented el 9 ene. 2020 a las 12:41
  • Le doy vuelta a tu pregunta pero no entiendo hacia que apunta. Tienes una lista A y una versión con otro orden de la B, ¿lo que buscas es saber que funciones aplicar para lograr transforma B nuevamente en A? ¿es eso? Commented el 9 ene. 2020 a las 15:24
  • Gracias por contestar @PatricioMoracho. No. Lo que quiero es dada la lista A de la que partimos, y la lista B que es la lista A con otro orden al que queremos llegar usando solamente las funciones especificadas por nosotros, haya un algoritmo que te diga cuantas veces y en qué orden hay que usar esas funciones especificadas (en mi ejemplo las únicas funciones que se pueden usar para llegar de un orden al otro son mezcla faro y cortar el array por el número n).
    – sarasataco
    Commented el 9 ene. 2020 a las 15:51
  • Ahora si, Pareciera un problema NP-completo (¿lo será?), si fuera así, no hay otra que usar fuerza bruta. Commented el 9 ene. 2020 a las 16:09

0

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

Examina otras preguntas con la etiqueta o formula tu propia pregunta.