Вычислить минимальное количество свопов, чтобы упорядочить последовательность

Ответ 1

Я смог доказать это с помощью graph-theory. Может быть, хотите добавить этот тег в :)

Создайте граф с n вершинами. Создайте ребро от узла n_i до n_j если элемент в позиции i должен быть в позиции j в правильном порядке. Теперь у вас будет график, состоящий из нескольких непересекающихся циклов. Я утверждаю, что минимальное количество перестановок, необходимое для правильного упорядочения графика,

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

Потратьте секунду, чтобы убедить себя в этом... если два элемента находятся в цикле, один обмен может просто позаботиться о них. Если в цикле три элемента, вы можете поменять пару, чтобы поместить один в правильное место, а двухтактный цикл останется и т.д. Если в цикле n элементов, вам нужно n-1 обменов. (Это всегда так, даже если вы не поменялись местами с ближайшими соседями.)

Учитывая это, теперь вы можете понять, почему ваш алгоритм оптимален. Если вы выполните обмен, и хотя бы один элемент находится в правильном положении, он всегда будет уменьшать значение M на 1. Для любого цикла длины n рассмотрите возможность перестановки элемента в правильное место, занимаемое его соседом. Теперь у вас есть правильно упорядоченный элемент и цикл длиной n-1.

Поскольку M - это минимальное количество свопов, а ваш алгоритм всегда уменьшает M на 1 для каждого свопа, он должен быть оптимальным.

Ответ 2

Для вашей справки, вот алгоритм, который я написал, чтобы сгенерировать минимальное количество свопов, необходимых для сортировки массива. Он находит циклы, описанные @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;
}

Ответ 3

Эмм, весь цикл счета очень сложно держать в голове. Есть способ, который намного проще запомнить.

Во-первых, давайте бросим образец дела вручную.

• Последовательность: [7, 1, 3, 2, 4, 5, 6]
• Перечислим это: [(0, 7), (1, 1), (2, 3), (3, 2), (4, 4), (5, 5), (6, 6)]
• Сортировать перечисление по значению: [(1, 1), (3, 2), (2, 3), (4, 4), (5, 5), (6, 6), (0, 7)]
• Начните с самого начала. Хотя индекс отличается от нумерованного индекса, продолжайте менять элементы, определенные индексом и перечисляемым индексом. Помните: swap(0,2);swap(0,3) аналогичен 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) ]

Т.е. семантически вы сортируете элементы, а затем выясняете, как перевести их в исходное состояние, переключая крайний левый элемент, который не на своем месте.

Алгоритм Python настолько прост:

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

Таким образом, вам не нужно запоминать посещенные узлы и вычислять некоторую длину цикла.

Ответ 4

Нам не нужно менять местами фактические элементы, просто найдите, сколько элементов не в нужном индексе (цикл). Мин. Свопами будет цикл - 1; Вот код...

static int minimumSwaps(int[] arr) {
        int swap=0;
        boolean visited[]=new boolean[arr.length];

        for(int i=0;i<arr.length;i++){
            int j=i,cycle=0;

            while(!visited[j]){
                visited[j]=true;
                j=arr[j]-1;
                cycle++;
            }

            if(cycle!=0)
                swap+=cycle-1;
        }
        return swap;


    }

Ответ 5

Версия 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
}

Ответ 6

Красивое решение от @bekce. Если вы используете С#, начальный код настройки измененного массива ar может быть кратко выражен как:

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

затем используйте origIndexes вместо ar в остальной части кода.

Ответ 7

//Предполагая, что мы имеем дело только с последовательностью, начинающейся с нуля

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
}

Ответ 8

Это пример кода на С++, который находит минимальное количество свопов для сортировки перестановки последовательности (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;
}

Ответ 9

Реализация на целых числах с примитивными типами в Java (и тесты).

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

тесты

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

Ответ 10

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
}

Ответ 11

Код Python

A = [4,3,2,1]
count = 0
for i in range (len(A)):
    min_idx = i
    for j in range (i+1,len(A)):
        if A[min_idx] > A[j]:
            min_idx = j
    if min_idx > i:
        A[i],A[min_idx] = A[min_idx],A[i]
        count = count + 1
print "Swap required : %d" %count

Ответ 12

В JavaScript

Если счетчик массива начинается с 1

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 + 1) {
                j = arr[j] - 1
                visitedarr[j] = true
                cycleNode++
            }
            swap += cycleNode - 1
        }
    }
    return swap
}

еще

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
}

Просто расширяем код Даршана Путтасвами для текущих входных данных стекового потока