¿Número mínimo de intercambios necesarios para cambiar el Array 1 al Array 2?

Por ejemplo, la entrada es

Array 1 = [2, 3, 4, 5] Array 2 = [3, 2, 5, 4] 

El número mínimo de swaps necesarios es 2 .

Los swaps no necesitan estar con celdas adyacentes, se pueden intercambiar dos elementos.

Como @IVlad señaló en el comentario de su pregunta, el problema de Yodaness le pide que cuente el número de inversiones y el número mínimo de intercambios.

Por ejemplo:

 L1 = [2,3,4,5] L2 = [2,5,4,3] 

El número mínimo de intercambios es uno (intercambie 5 y 3 en L2 para obtener L1 ), pero el número de inversiones es tres : (5 4), (5 3) y (4 3) pares están en el orden incorrecto.

La forma más simple de contar el número de inversiones se deriva de la definición :

Un par de elementos (p i , p j ) se llama inversión en una permutación p si i i > p j .

En Python:

 def count_inversions_brute_force(permutation): """Count number of inversions in the permutation in O(N**2).""" return sum(pi > permutation[j] for i, pi in enumerate(permutation) for j in xrange(i+1, len(permutation))) 

Puede contar la inversión en O(N*log(N)) usando la estrategia de dividir y conquistar (similar a cómo funciona un algoritmo de ordenación por fusión ). Aquí hay un pseudocódigo de Counting Inversions traducido al código de Python:

 def merge_and_count(a, b): assert a == sorted(a) and b == sorted(b) c = [] count = 0 i, j = 0, 0 while i < len(a) and j < len(b): c.append(min(b[j], a[i])) if b[j] < a[i]: count += len(a) - i # number of elements remaining in `a` j+=1 else: i+=1 # now we reached the end of one the lists c += a[i:] + b[j:] # append the remainder of the list to C return count, c def sort_and_count(L): if len(L) == 1: return 0, L n = len(L) // 2 a, b = L[:n], L[n:] ra, a = sort_and_count(a) rb, b = sort_and_count(b) r, L = merge_and_count(a, b) return ra+rb+r, L 

Ejemplo:

 >>> sort_and_count([5, 4, 2, 3]) (5, [2, 3, 4, 5]) 

Aquí hay una solución en Python para el ejemplo del problema :

 yoda_words = "in the force strong you are".split() normal_words = "you are strong in the force".split() perm = get_permutation(normal_words, yoda_words) print "number of inversions:", sort_and_count(perm)[0] print "number of swaps:", number_of_swaps(perm) 

Salida:

 number of inversions: 11 number of swaps: 5 

Las definiciones de get_permutation() y number_of_swaps() son:

 def get_permutation(L1, L2): """Find permutation that converts L1 into L2. See http://en.wikipedia.org/wiki/Cycle_representation#Notation """ if sorted(L1) != sorted(L2): raise ValueError("L2 must be permutation of L1 (%s, %s)" % (L1,L2)) permutation = map(dict((v, i) for i, v in enumerate(L1)).get, L2) assert [L1[p] for p in permutation] == L2 return permutation def number_of_swaps(permutation): """Find number of swaps required to convert the permutation into identity one. """ # decompose the permutation into disjoint cycles nswaps = 0 seen = set() for i in xrange(len(permutation)): if i not in seen: j = i # begin new cycle that starts with `i` while permutation[j] != i: # (i σ(i) σ(σ(i)) ...) j = permutation[j] seen.add(j) nswaps += 1 return nswaps 

Como lo implica la solución de Sebastian, el algoritmo que está buscando puede basarse en la inspección de los ciclos de la permutación .

Deberíamos considerar la matriz n. ° 2 como una transformación de permutación en la matriz n. ° 1. En su ejemplo, la permutación se puede representar como P = [2,1,4,3].

Cada permutación se puede express como un conjunto de ciclos disjuntos, que representan cambios cíclicos de posición de los elementos. La permutación P por ejemplo tiene 2 ciclos: (2,1) y (4,3). Por lo tanto, dos intercambios son suficientes. En el caso general, simplemente debe restar el número de ciclos de la longitud de permutación, y obtiene la cantidad mínima de intercambios requeridos. Esto se desprende de la observación de que para “arreglar” un ciclo de N elementos, los intercambios N-1 son suficientes.

Este problema tiene una solución limpia, codiciosa y trivial:

  1. Encuentre cualquier operación de intercambio que coloque los dos elementos intercambiados en Array1 más cerca de su destino en Array2. Realice la operación de intercambio en Array1 si existe.
  2. Repita el paso 1 hasta que no existan más operaciones de intercambio de este tipo.
  3. Encuentre cualquier operación de intercambio que consiga un elemento intercambiado en Array1 más cerca de su destino en Array2. Si existe tal operación, actívela en Array1.
  4. Regrese al paso 1 hasta Array1 == Array2.

La corrección del algoritmo puede demostrarse definiendo un potencial para el problema como la sum de las distancias de todos los elementos en el conjunto1 desde su destino en el conjunto2.

Probablemente haya alguna solución inteligente de progtwigción dinámica, pero no puedo resolverlo en este momento. Podría hacer una travesía BFS ingenua utilizando algo como esto:

  • afirmar que es posible (por ejemplo, clasificando y comparando)
  • Queue q = [(0, L1)]
  • Mientras que q no está vacío
    • extraer un par (i, L)
    • si L == L2, devuelve i
    • para cada 0 <= i, j <= L1.length
      • agregue (i + 1, L.swap (i, j)) a q

ACTUALIZACIÓN : implementación en Python (es lento O ((N 3 ) n ))

 def bfs(L1, L2): assert sorted(L1) == sorted(L2) q = deque([ (0,L1) ]) while q: n, L = q.popleft() if L == L2: return n for i, j in combinations(range(len(L1)), 2): # all N*(N-1)/2 pairs q.append((n+1, swap(L, i, j))) from collections import deque from itertools import combinations def swap(L, i, j): a = list(L) # make copy a[i], a[j] = a[j], a[i] # swap return a 

Esto se puede convertir fácilmente a otro tipo de problema, que se puede resolver de manera más eficiente. Todo lo que se necesita es convertir las matrices en permutaciones, es decir, cambiar los valores a sus ID. Entonces tus matrices:

 L1 = [2,3,4,5] L2 = [2,5,4,3] 

se convertiría

 P1 = [0,1,2,3] P2 = [0,3,2,1] 

con la tarea 2->0, 3->1, 4->2, 5->3 . Esto solo se puede hacer si no hay elementos repetidos. Si hay, entonces esto se vuelve más difícil de resolver.

La conversión de la permutación de uno a otro se puede convertir en un problema similar ( número de intercambios en una permutación ) invirtiendo la permutación objective en O (n), componiendo las permutaciones en O (n) y luego encontrando el número de permutas desde allí a una permutación de identidad en O (m). Dado:

 int P1[] = {0, 1, 2, 3}; // 2345 int P2[] = {0, 3, 2, 1}; // 2543 // we can follow a simple algebraic modification // (see http://en.wikipedia.org/wiki/Permutation#Product_and_inverse): // P1 * P = P2 | premultiply P1^-1 * // P1^-1 * P1 * P = P1^-1 * P2 // I * P = P1^-1 * P2 // P = P1^-1 * P2 // where P is a permutation that makes P1 into P2. // also, the number of steps from P to identity equals // the number of steps from P1 to P2. int P1_inv[4]; for(int i = 0; i < 4; ++ i) P1_inv[P1[i]] = i; // invert the first permutation in O(n) int P[4]; for(int i = 0; i < 4; ++ i) P[i] = P2[P1_inv[i]]; // chain the permutations in O(n) int num_steps = NumSteps(P, 4); // will return 2 // now we just need to count the steps in O(num_steps) 

Para contar los pasos, se puede diseñar un algoritmo simple, como:

 int NumSteps(int *P, int n) { int count = 0; for(int i = 0; i < n; ++ i) { for(; P[i] != i; ++ count) // could be permuted multiple times swap(P[P[i]], P[i]); // look where the number at hand should be } // count number of permutations return count; } 

Esto siempre intercambia un elemento por un lugar donde debería estar en la permutación de identidad, por lo tanto, en cada paso deshace y cuenta un intercambio. Ahora, siempre que el número de intercambios que devuelve sea realmente mínimo, el tiempo de ejecución del algoritmo está limitado por él y se garantiza que finalizará (en lugar de quedar atrapado en un ciclo infinito). Se ejecutará en O(m) swaps o O(m + n) iteraciones de bucle donde m es el número de swaps (el count devuelto) y n es el número de elementos en la secuencia ( 4 ). Tenga en cuenta que m < n siempre es verdadero. Por lo tanto, esto debería ser superior a las soluciones O(n log n) , ya que el límite superior es O(n - 1) de swaps u O(n + n - 1) de iteraciones de bucle aquí, que es prácticamente O(n) (factor constante de 2 omitido en este último caso).

El algoritmo solo funcionará para permutaciones válidas, se repetirá infinitamente para secuencias con valores duplicados y hará acceso de matriz fuera de límites (y locking) para secuencias con valores distintos de [0, n) . Aquí puede encontrar un caso de prueba completo (comstackciones con Visual Studio 2008, el algoritmo en sí mismo debería ser bastante portátil). Genera todas las permutaciones posibles de longitudes 1 a 32 y las comprobaciones frente a soluciones, generadas con la primera búsqueda de ancho (BFS), parece funcionar para todas las permutaciones de longitudes 1 a 12, luego se vuelve bastante lento, pero supongo que continuará funcionando .

Esto parece un problema de distancia de edición , excepto que solo se permiten las transposiciones.

Echa un vistazo al pseudo código de distancia de Damerau-Levenshtein . Creo que puedes ajustarlo para contar solo las transposiciones.

Algoritmo:

  1. Compruebe si los elementos de la lista en la misma posición son iguales. Si es así, no se requiere intercambio. Si no, cambie la posición del elemento de lista donde el elemento coincida
  2. Iterar el proceso para todos los elementos de la lista.

Código:

 def nswaps(l1, l2): cnt = 0 for i in range(len(l1)): if l1[i] != l2[i]: ind = l2.index(l1[i]) l2[i], l2[ind] = l2[ind], l2[i] cnt += 1 pass return cnt 

@JF Sebastian y la respuesta de @Eyal Schneider son geniales. Me inspiré para resolver un problema similar: calcule los intercambios mínimos necesarios para ordenar una matriz , por ejemplo: para ordenar {2,1,3,0} , necesita un mínimo de 2 intercambios.

Aquí está el código de Java:

 // 0 1 2 3 // 3 2 1 0 (0,3) (1,2) public static int sortWithSwap(int [] a) { Integer[] A = new Integer[a.length]; for(int i=0; i set = new HashSet<>(); boolean newCycle = true; for(int i=0; i map = new HashMap<>(); for(int i=0; i