Qual è il numero minimo di swap adiacenti necessari per separare un elenco di 0 e 1?

Aug 21 2020

Sto cercando di risolvere un problema di strutture dati e algoritmi, che afferma che dato un gruppo di 1 e 0, raggruppa le cifre in modo tale che tutti gli 0 siano insieme e tutti gli 1 siano insieme. Qual è il numero minimo di scambi necessari per ottenere ciò se si possono scambiare solo due elementi adiacenti? Non importa quale gruppo sia a quale fine.

Per esempio:

[0,1,0,1] = [0,0,1,1] 1 swap

[1,1,1,1,0,1,0] = [1,1,1,1,1,0,0] 1 swap

[1, 0, 1, 0, 0, 0, 0, 1] = = [1,1,1,0,0,0,0,0] 6 scambi

Nota che questo è diverso dalle domande poste qui:

Trova il numero minimo di swap richiesti in modo che tutti gli 0 e tutti gli 1 siano insieme

Non sto ordinando l'array, sto solo cercando di raggruppare tutti gli 0 e tutti gli 1 insieme e non importa quale sia a quale fine.

Non ho davvero la minima idea da dove cominciare. Qualcuno può aiutarmi?

Risposte

1 Dave Aug 21 2020 at 05:42

Concentriamoci sugli zeri. Ogni scambio sposta un singolo zero di una singola posizione più vicino all'ordine finale. Quindi possiamo trovare il numero di scambi trovando il numero di zeri spostati e la gravità dello spostamento.

Partiamo dal presupposto che gli zeri finiscano all'inizio dell'array. Terremo traccia di due cose: count_of_ones e displacement, entrambi inizializzati a zero. Ogni volta che troviamo un 1, incrementiamo count_of_ones. Ogni volta che troviamo uno 0, aumentiamo lo spostamento di count_of_ones.

Quindi lo facciamo nella direzione opposta. Entrambi i modi sono lineari, quindi questo è lineare.

Ad esempio 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 risposta per questa direzione è lo spostamento finale, o 7. Andando dall'altra parte otteniamo 5. La risposta finale è 5.

In effetti, la somma degli spostamenti finali (iniziando vs finendo con tutti zeri) sarà sempre uguale a num_zeroes * num_ones. Questo dimezza il lavoro (sebbene sia ancora lineare).


Dai commenti sembra che alcune persone non abbiano capito la mia risposta. Ecco un'implementazione di Ruby per rendere le cose più chiare.

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

Gli zeri finiscono a sinistra se displacement <reverse_displacement, o se sono uguali, oppure a destra se displacement> reverse_displacement.

MattTimmermans Aug 21 2020 at 09:22

Sia SUM0la somma degli indici (a base 0) di tutti gli zeri, e SUM1sia la somma degli indici di tutti gli uno. Ogni volta che si scambia 10-> 01, SUM0scende di uno e SUM1sale di uno. Vanno dall'altra parte quando scambi 01-> 10.

Diciamo che hai N0zeri e N1uno. Se gli zeri fossero stati impacchettati insieme all'inizio dell'array, allora avresti SUM0 = N0*(N0-1)/2. È il più piccolo SUM0che puoi avere.

Poiché un singolo scambio adiacente può ridursi SUM0esattamente di uno, sono necessari SUM0 - N0*(N0-1)/2scambi esattamente per raggruppare gli zeri nella parte anteriore. Allo stesso modo, sono necessari degli SUM1 - N1*(N1-1)/2scambi per mettere insieme quelli nella parte anteriore.

La tua risposta è il più piccolo di questi numeri: min( SUM0 - N0*(N0-1)/2 , SUM1 - N1*(N1-1)/2 )

Questi valori sono tutti facili da calcolare in tempo lineare.

GiorgiTsiklauri Aug 21 2020 at 05:40

Un approccio semplice utilizzando Bubble Sort, che accetta O (n 2 ), sarebbe questo:

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;
    }
}