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

Question

Por ejemplo, la entrada se

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

Número mínimo de permutas necesarios son 2.

Los intercambios no tienen que ser con celdas adyacentes, dos elementos pueden intercambiarse.

Answer 1

Como @IVlad observó en el comentario de su pregunta Yodaness problem le pide que cuente number of inversions y no un número mínimo de intercambios.

Por ejemplo:

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

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

La forma más sencilla para contar número de inversiones se sigue de the definition:

un par de elementos (p _i, p _j) se llama una inversión en una permutación p si i < j y p _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))) 

Se podía contar la inversión en O(N*log(N)) usando división & estrategia de conquista (similar a cómo funciona a merge sort algorithm). Aquí está pseudo-código de Counting Inversions traducido a código 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í está solución en Python para el ejemplo de the problem:

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) 

de salida:

number of inversions: 11 
number of swaps: 5 

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 

Answer 2

Probablemente haya alguna solución inteligente de programación dinámica pero no puedo resolverlo ahora. Se podría hacer un recorrido BFS ingenua usar algo como esto:

• afirman que es posible (por ejemplo, mediante una clasificación y comparación)
• cola q = [(0, L1)]
• Mientras q no es -empty
  • extracto de algún par (i, L)
  • si L == L2, de regreso i
  • para cada 0 < = i, j = < L1.length
    • add (i + 1, L.swap (i, j)) para q

ACTUALIZACIÓN: implementación en Python (es O lento ((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 

Answer 3

Esto parece como un problema de edit distance, excepto que solo se permiten transposiciones.

Echa un vistazo Damerau–Levenshtein distance pseudo código. Creo que puedes ajustarlo para contar solo las transposiciones.

Answer 4

como se deduce de la solución de Sebastian, el algoritmo que busca puede estar basado en la inspección de la permutation's cycles.

Debemos considerar el arreglo # 2 para ser una transformación en la matriz de permutación # 1. En su ejemplo, la permutación se puede representar como P = [2,1,4,3].

cada permutación se puede expresar como un conjunto de ciclos disjuntos, representando los cambios de posición cíclica de los artículos. 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.

Answer 5

Este problema tiene una solución limpia, codicioso, trivial:

1. encontró ninguna operación de canje que se pone ambos elementos cambiados 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. encontró ninguna operación de canje que se pone uno elemento intercambiado en Array1 más cerca de su destino en Array2. Si existe tal operación, actívela en Array1.
4. Vuelva al paso 1 hasta Array1 == Array2.

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

Answer 6

@ J.F. La respuesta de Sebastian y @Eyal Schneider son geniales. Me inspiré en la solución de un problema similar: Calcular las permutas mínimos necesarios para ordenar una matriz, ej .: para ordenar {2,1,3,0}, se necesita un mínimo de 2 permutas.

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<a.length; i++) A[i] = a[i]; 
    Integer[] B = Arrays.copyOf(mapping(A), A.length, Integer[].class); 

    int cycles = 0; 
    HashSet<Integer> set = new HashSet<>(); 
    boolean newCycle = true; 
    for(int i=0; i<B.length;) { 
     if(!set.contains(B[i])) { 
      if(newCycle) { 
       newCycle = false; 
       cycles++; 
      } 
      set.add(B[i]); 
      i = B[i]; 
     } 
     else if(set.contains(B[i])) { // duplicate in existing cycles 
      newCycle = true; 
      i++; 
     } 
    } 

    // suppose sequence has n cycles, each cycle needs swap len(cycle)-1 times 
    // and sum of length of all cycles is length of sequence, so 
    // swap = sequence length - cycles 
    return a.length - cycles; 
} 

// a b b c 
// c a b b 
// 3 0 1 1 
private static Object[] mapping(Object[] A) { 
    Object[] B = new Object[A.length]; 
    Object[] ret = new Object[A.length]; 
    System.arraycopy(A, 0, B, 0, A.length); 
    Arrays.sort(A); 
    HashMap<Object, Integer> map = new HashMap<>(); 
    for(int i=0; i<A.length; i++) { 
     map.put(A[i], i); 
    } 

    for(int i=0; i<B.length; i++) { 
     ret[i] = map.get(B[i]); 
    } 
    return ret; 
} 

Answer 7

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

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

se convertirían en

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

con la asignación 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.

Convirtiendo la permutación de uno a otro se puede convertir a un problema similar (Number of swaps in a permutation) invirtiendo la permutación objetivo en O (n), componiendo las permutaciones en O (n) y luego encontrando el número de permutas desde allí a un 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, un algoritmo simple se puede diseñar, tales 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 artículo para un lugar en el que 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 cierto. 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 o O(n + n - 1) de iteraciones de bucle aquí, que es prácticamente O(n) (se omite el factor constante de 2 en este último caso).

El algoritmo solo funcionará para permutaciones válidas, se repetirá infinitamente para secuencias con valores duplicados y realizará acceso de matriz fuera de límites (y bloqueo) para secuencias con valores que no sean [0, n). Se puede encontrar un caso de prueba completo here (compilaciones 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 .

Answer 8

Algoritmo:

1. Comprobar si los elementos de la lista en la misma posición son iguales. Si es así, no se requiere intercambio. En caso negativo, cambie la posición del elemento de lista donde coincida el elemento
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