algorithm - topological sort c++

Calcule el número mínimo de swaps para ordenar una secuencia

Question

Estoy trabajando en la clasificación de una secuencia entera sin números idénticos (sin pérdida de generalidad, supongamos que la secuencia es una permutación de 1,2,...,n ) en su orden creciente natural (es decir 1,2,...,n ). Estaba pensando en intercambiar directamente los elementos (independientemente de las posiciones de los elementos; en otras palabras, un intercambio es válido para cualquiera de los dos elementos) con un número mínimo de intercambios (lo siguiente puede ser una solución viable):

Intercambie dos elementos con la restricción de que uno o ambos de ellos deben cambiarse a la (s) posición (es) correcta (s). Hasta que cada elemento se ponga en su posición correcta.

Pero no sé cómo probar matemáticamente si la solución anterior es óptima. ¿Alguien puede ayudar?

Answer 1

// Suponiendo que estamos tratando con una secuencia comenzada con cero

function minimumSwaps(arr) {
    var len = arr.length
    var visitedarr = []
    var i, start, j, swap = 0
    for (i = 0; i < len; i++) {
        if (!visitedarr[i]) {
            start = j = i
            var cycleNode = 1
            while (arr[j] != start) {
                j = arr[j]
                visitedarr[j] = true
                cycleNode++
            }
            swap += cycleNode - 1
        }
    }
    return swap
}

Answer 2

Ehm, todo el conteo de ciclos es muy difícil de mantener en tu cabeza. Hay una forma que es mucho más simple de memorizar.

Primero, vamos a tirar un caso de muestra manualmente.

• Secuencia: [7, 1, 3, 2, 4, 5, 6]
• Enumérela: [(0, 7), (1, 1), (2, 3), (3, 2), (4, 4), (5, 5), (6, 6)]
• Ordene la enumeración por valor: [(1, 1), (3, 2), (2, 3), (4, 4), (5, 5), (6, 6), (0, 7)]
• Comienza desde el principio. Si bien el índice es diferente del índice enumerado, siga intercambiando los elementos definidos por el índice y el índice enumerado. Recuerde: swap(0,2);swap(0,3) es lo mismo que swap(2,3);swap(0,2)
  • swap(0, 1) => [ (3, 2) , (1, 1) , (2, 3), (4, 4), (5, 5), (6, 6), (0, 7) ]
  • swap(0, 3) => [ (4, 4) , (1, 1), (2, 3), (3, 2) , (5, 5), (6, 6), (0, 7) ]
  • swap(0, 4) => [ (5, 5) , (1, 1), (2, 3), (3, 2), (4, 4) , (6, 6), (0, 7) ]
  • swap(0, 5) => [ (6, 6) , (1, 1), (2, 3), (3, 2), (4, 4), (5, 5) , (0, 7) ]
  • swap(0, 6) => [ (0, 7) , (1, 1), (2, 3), (3, 2), (4, 4), (5, 5), (6, 6) ]

Es decir, semánticamente ordena los elementos y luego averigua cómo colocarlos en el estado inicial mediante el intercambio a través del elemento situado más a la izquierda que está fuera de lugar.

El algoritmo de Python es tan simple como esto:

def swap(arr, i, j):
    tmp = arr[i]
    arr[i] = arr[j]
    arr[j] = tmp


def minimum_swaps(arr):
    annotated = [*enumerate(arr)]
    annotated.sort(key = lambda it: it[1])

    count = 0

    i = 0
    while i < len(arr):
        if annotated[i][0] == i:
            i += 1
            continue
        swap(annotated, i, annotated[i][0])
        count += 1

    return count

Por lo tanto, no es necesario memorizar los nodos visitados ni calcular la duración de algún ciclo.

Answer 3

Este es el código de muestra en C ++ que encuentra el número mínimo de swaps para ordenar una permutación de la secuencia de (1,2,3,4,5,.......n-2,n-1,n)

#include<bits/stdc++.h>
using namespace std;


int main()
{
    int n,i,j,k,num = 0;
    cin >> n;
    int arr[n+1];
    for(i = 1;i <= n;++i)cin >> arr[i];
    for(i = 1;i <= n;++i)
    {
        if(i != arr[i])// condition to check if an element is in a cycle r nt
        {
            j = arr[i];
            arr[i] = 0;
            while(j != 0)// Here i am traversing a cycle as mentioned in 
            {             // first answer
                k = arr[j];
                arr[j] = j;
                j = k;
                num++;// reducing cycle by one node each time
            }
            num--;
        }
    }
    for(i = 1;i <= n;++i)cout << arr[i] << " ";cout << endl;
    cout << num << endl;
    return 0;
}

Answer 4

Para su referencia, aquí hay un algoritmo que escribí para generar el número mínimo de swaps necesarios para ordenar la matriz. Encuentra los ciclos descritos por @Andrew Mao.

/**
 * Finds the minimum number of swaps to sort given array in increasing order.
 * @param ar array of <strong>non-negative distinct</strong> integers. 
 *           input array will be overwritten during the call!
 * @return min no of swaps
 */
public int findMinSwapsToSort(int[] ar) {
    int n = ar.length;
    Map<Integer, Integer> m = new HashMap<>();
    for (int i = 0; i < n; i++) {
        m.put(ar[i], i);
    }
    Arrays.sort(ar);
    for (int i = 0; i < n; i++) {
        ar[i] = m.get(ar[i]);
    }
    m = null;
    int swaps = 0;
    for (int i = 0; i < n; i++) {
        int val = ar[i];
        if (val < 0) continue;
        while (val != i) {
            int new_val = ar[val];
            ar[val] = -1;
            val = new_val;
            swaps++;
        }
        ar[i] = -1;
    }
    return swaps;
}

Answer 5

Pude probar esto con la teoría de grafos. Es posible que desee agregar esa etiqueta en :)

Crea una gráfica con n vértices. Cree un borde desde el nodo n_i hasta n_j si el elemento en la posición i debería estar en la posición j en el orden correcto. Ahora tendrá una gráfica que consta de varios ciclos que no se intersecan. Sostengo que el número mínimo de swaps necesarios para ordenar la gráfica correctamente es

M = sum (c in cycles) size(c) - 1

Tómese un segundo para convencerse de que ... si dos elementos están en un ciclo, un intercambio puede encargarse de ellos. Si hay tres elementos en un ciclo, puede intercambiar un par para colocar uno en el lugar correcto y quedan dos ciclos, etc. Si n elementos están en un ciclo, necesita n-1 swaps. (Esto siempre es cierto incluso si no se intercambia con vecinos inmediatos).

Dado eso, ahora puede ver por qué su algoritmo es óptimo. Si realiza un intercambio y al menos un elemento está en la posición correcta, entonces siempre reducirá el valor de M en 1. Para cualquier ciclo de longitud n , considere la posibilidad de intercambiar un elemento en el lugar correcto, ocupado por su vecino. Ahora tienes un elemento correctamente ordenado y un ciclo de longitud n-1 .

Como M es el número mínimo de swaps, y su algoritmo siempre reduce M en 1 para cada swap, debe ser óptimo.

Answer 6

Solución bien hecha por @bekce. Si utiliza C #, el código inicial de configuración de la matriz modificada ar se puede expresar de manera sucinta como:

var origIndexes = Enumerable.Range(0, n).ToArray();
Array.Sort(ar, origIndexes);

luego use origIndexes lugar de ar en el resto del código.

Answer 7

Swift 4.2:

func minimumSwaps(arr: [Int]) -> Int {
    let sortedValueIdx = arr.sorted().enumerated()
        .reduce(into: [Int: Int](), { $0[$1.element] = $1.offset })

    var checked = Array(repeating: false, count: arr.count)
    var swaps = 0

    for idx in 0 ..< arr.count {
        if checked[idx] { continue }

        var edges = 1
        var cursorIdx = idx
        while true {
            let cursorEl = arr[cursorIdx]
            let targetIdx = sortedValueIdx[cursorEl]!
            if targetIdx == idx {
                break
            } else {
                cursorIdx = targetIdx
                edges += 1
            }
            checked[targetIdx] = true
        }
        swaps += edges - 1
    }

    return swaps
}

Answer 8

Una implementación en enteros con tipos primitivos en Java (y pruebas).

import java.util.Arrays;

public class MinSwaps {
  public static int computate(int[] unordered) {
    int size = unordered.length;
    int[] ordered = order(unordered);
    int[] realPositions = realPositions(ordered, unordered);
    boolean[] touchs = new boolean[size];
    Arrays.fill(touchs, false);
    int i;
    int landing;
    int swaps = 0;

    for(i = 0; i < size; i++) {
      if(!touchs[i]) {
        landing = realPositions[i];

        while(!touchs[landing]) {
          touchs[landing] = true;
          landing = realPositions[landing];

          if(!touchs[landing]) { swaps++; }
        }
      }
    }

    return swaps;
  }

  private static int[] realPositions(int[] ordered, int[] unordered) {
    int i;
    int[] positions = new int[unordered.length];

    for(i = 0; i < unordered.length; i++) {
      positions[i] = position(ordered, unordered[i]);
    }

    return positions;
  }

  private static int position(int[] ordered, int value) {
    int i;

    for(i = 0; i < ordered.length; i++) {
      if(ordered[i] == value) {
        return i;
      }
    }

    return -1;
  }

  private static int[] order(int[] unordered) {
    int[] ordered = unordered.clone();
    Arrays.sort(ordered);

    return ordered;
  }
}

Pruebas

import org.junit.Test;

import static org.junit.Assert.assertEquals;

public class MinimumSwapsSpec {
  @Test
  public void example() {
    // setup
    int[] unordered = new int[] { 40, 23, 1, 7, 52, 31 };

    // run
    int minSwaps = MinSwaps.computate(unordered);

    // verify
    assertEquals(5, minSwaps);
  }

  @Test
  public void example2() {
    // setup
    int[] unordered = new int[] { 4, 3, 2, 1 };

    // run
    int minSwaps = MinSwaps.computate(unordered);

    // verify
    assertEquals(2, minSwaps);
  }

  @Test
  public void example3() {
    // setup
    int[] unordered = new int[] {1, 5, 4, 3, 2};

    // run
    int minSwaps = MinSwaps.computate(unordered);

    // verify
    assertEquals(2, minSwaps);
  }
}

Answer 9

Versión Swift 4:

func minimumSwaps(arr: [Int]) -> Int {

      struct Pair {
         let index: Int
         let value: Int
      }

      var positions = arr.enumerated().map { Pair(index: $0, value: $1) }
      positions.sort { $0.value < $1.value }
      var indexes = positions.map { $0.index }

      var swaps = 0
      for i in 0 ..< indexes.count {
         var val = indexes[i]
         if val < 0 {
            continue // Already visited.
         }
         while val != i {
            let new_val = indexes[val]
            indexes[val] = -1
            val = new_val
            swaps += 1
         }
         indexes[i] = -1
      }
      return swaps
}