¿Cuál es el número mínimo de intercambios adyacentes necesarios para segregar una lista de 0 y 1?

Question

Estoy tratando de resolver un problema de Estructuras de datos y algoritmos, que establece que, dado un grupo de 1 y 0, agrupe los dígitos de manera que todos los 0 estén juntos y todos los 1 estén juntos. ¿Cuál es el número mínimo de intercambios necesarios para lograr esto si solo se pueden intercambiar dos elementos adyacentes? No importa qué grupo esté en qué extremo.

P.ej:

[0,1,0,1] = [0,0,1,1] 1 intercambios

[1,1,1,1,0,1,0] = [1,1,1,1,1,0,0] 1 intercambios

[1, 0, 1, 0, 0, 0, 0, 1] = = [1,1,1,0,0,0,0,0] 6 intercambios

Tenga en cuenta que esto es diferente de las preguntas que se hacen aquí:

Encuentre el número mínimo de intercambios requeridos de manera que todos los 0 y todos los 1 estén juntos

No estoy ordenando la matriz, solo estoy tratando de agrupar todos los 0 y todos los 1 juntos y no importa cuál es en qué extremo.

Realmente no tengo ni idea de por dónde empezar. ¿Alguien me puede ayudar?

Answer 1

Centrémonos en los ceros. Cada intercambio mueve un solo cero una sola posición más cerca de la orden final. Luego, podemos encontrar el número de intercambios al encontrar el número de desplazamientos ceros y la gravedad del desplazamiento.

Comencemos asumiendo que los ceros terminan al comienzo de la matriz. Realizaremos un seguimiento de dos cosas: count_of_ones y desplazamiento, ambos inicializados a cero. Cada vez que encontramos un 1, incrementamos count_of_ones. Cada vez que encontramos un 0, aumentamos el desplazamiento en count_of_ones.

Luego hacemos esto en la otra dirección. Ambas formas son lineales, por lo que esto es lineal.

Por ejemplo, 1010001

1: count_of_ones: 0 -> 1
0: displacement: 0 -> 1
1: count_of_ones: 1 -> 2
0: displacement: 1 -> 3
0: displacement: 3 -> 5
0: displacement: 5 -> 7
1: count_of_ones: 2 -> 3

La respuesta para esta dirección es el desplazamiento final, o 7. En sentido contrario, obtenemos 5. La respuesta final es 5.

De hecho, la suma de los desplazamientos finales (comenzando vs terminando con todos los ceros) siempre será igual a num_zeroes * num_ones. Esto reduce a la mitad el trabajo (aunque sigue siendo lineal).

---

Por los comentarios, parece que algunas personas no entendieron mi respuesta. Aquí hay una implementación de Ruby para aclarar las cosas.

def find_min_swaps(arr)
  count_of_ones = 0
  displacement = 0
  arr.each do |v|
    count_of_ones += 1 if v == 1
    displacement += count_of_ones if v == 0
  end

  count_of_zeroes = arr.length - count_of_ones
  reverse_displacement = count_of_ones * count_of_zeroes - displacement
  return [displacement, reverse_displacement].min
end

Los ceros terminan a la izquierda si displacement <reverse_displacement, ya sea si son iguales, o a la derecha si displacement> reverse_displacement.

Answer 2

Sea SUM0la suma de los índices (basados ​​en 0) de todos los ceros, y SUM1sea ​​la suma de los índices de todos los unos. Cada vez que intercambias 10-> 01, SUM0baja por uno y SUM1sube por uno. Van al revés cuando cambias 01-> 10.

Digamos que tienes N0ceros y N1unos. Si los ceros estuvieran empaquetados juntos al comienzo de la matriz, entonces lo habría hecho SUM0 = N0*(N0-1)/2. Eso es lo más pequeño SUM0que puedes tener.

Dado que un único intercambio adyacente puede reducirse SUM0exactamente en uno, se necesitan SUM0 - N0*(N0-1)/2intercambios exactos para empaquetar los ceros en la parte delantera. Del mismo modo, se necesitan SUM1 - N1*(N1-1)/2intercambios para empaquetar los que están juntos en la parte delantera.

Tu respuesta es el menor de estos números: min( SUM0 - N0*(N0-1)/2 , SUM1 - N1*(N1-1)/2 )

Todos esos valores son fáciles de calcular en tiempo lineal.

Answer 3

El enfoque simple usando Bubble Sort, que toma O (n ² ), sería este:

public class MainClass {

    public static void main(String[] args) {
        int[] arr = new int[]{1, 0, 0, 0, 0, 0, 0, 1, 0};
        int minSwaps = minimumSwaps(arr);
        System.out.println("Minimum swaps required: " + minSwaps);
    }

    public static int minimumSwaps(int[] array) {
        int[] arr1 = array.clone(), arr2 = array.clone();
        int swapsForRight = 0, swapsForLeft = 0;

        boolean sorted = false;

        while (!sorted) {
            sorted = true;
            for (int i = 0; i < arr1.length - 1; i++) {
                if (arr1[i + 1] < arr1[i]) {
                    int temp = arr1[i + 1];
                    arr1[i + 1] = arr1[i];
                    arr1[i] = temp;
                    sorted = false;
                    swapsForRight++;
                }
            }
        }
            
        sorted = false;
        while (!sorted) {
            sorted = true;
            for (int i = 0; i > arr2.length - 1; i++) {
                if (arr2[i + 1] < arr2[i]) {
                    int temp = arr2[i + 1];
                    arr2[i + 1] = arr2[i];
                    arr2[i] = temp;
                    sorted = false;
                    swapsForLeft++;
                }
            }
        }
        return swapsForLeft > swapsForRight ? swapsForRight : swapsForLeft;
    }
}