Определить минимальное количество перестановок, нужных для упорядочивания последовательности - C#

Формулировка задачи:

Есть перемешанная последовательность чисел от 1 до n. Нужно определить минимальное количество перестановок, которые нужно сделать, чтобы все числа были на своих местах. Одна перестановка - это взять число с одного места и переставить его на другое (то, что для этого нужно будет двигать другие числа не учитывается). Нашел такой способ решения, но он не всегда работает правильно. Например: если взять 1243, получаем 1-1, 2-2, 3-4-3 то есть нужно 3-е число поставить на место 4-го, а четвёртое, в свою очередь, на место 3-го. И здесь всё правильно, но если взять 4123, получаем 1-4-3-2-1 то есть 4 перестановки, хотя хватило бы и одной (самой первой. четвёрку поставить в конец). Или ещё хуже. Возьмём 12453. Получаем 1-1, 2-2, 3-4-5-3 То есть, нужно сделать 3 перестановки, хотя опять же хватило бы и одно, но на этот раз её вообще нет в списке. (переставить тройку на место после двойки). Так что этот способ не работает. Пожалуйста, можете подсказать работающий алгоритм?

Решение задачи: «Определить минимальное количество перестановок, нужных для упорядочивания последовательности»

textual
                            Листинг программы 
                        
 
                            
                        
using System;
using System.Collections.Generic;
 
namespace ConsoleApp1
{
    class Program
    {
        static int MinReplaces(int[] a)
        {
            int[] aux = new int[a.Length + 1];
 
            for (int i = 0; i < a.Length; ++i)
            {
                int j = a[i];
                int val = aux[j] + 1;
 
                while (j < aux.Length && val > aux[j])
                    aux[j++] = val;
            }
 
            return a.Length - aux[aux.Length - 1];
        }
 
        static void Main()
        {
            List<int[]> list = new List<int[]>();
            list.Add(new int[] { 1, 2, 3 }); // 0
            list.Add(new int[] { 3, 2, 1 }); // 2
            list.Add(new int[] { 1, 2, 4, 3 }); // 1 
            list.Add(new int[] { 2, 3, 4, 1 }); // 1
            list.Add(new int[] { 4, 1, 2, 3 }); // 1
            list.Add(new int[] { 1, 2, 4, 5, 3 }); // 1
            list.Add(new int[] { 1, 3, 2, 4, 6, 5 }); // 2
            list.Add(new int[] { 1, 6, 3, 4, 5, 2 }); // 2
            list.Add(new int[] { 6, 4, 1, 3, 2, 5 }); // 3
            list.Add(new int[] { 3, 5, 6, 4, 2, 1 }); // 3
            list.Add(new int[] { 4, 1, 3, 2, 5, 6 }); // 2
            list.Add(new int[] { 3, 6, 4, 5, 2, 1 }); // 3
            list.Add(new int[] { 4, 5, 6, 7, 1, 2, 3 }); // 3
            list.Add(new int[] { 1, 2, 9, 3, 8, 4, 5, 6, 7 }); // 2
            list.Add(new int[] { 10, 1, 6, 7, 2, 4, 8, 9, 5, 3 }); // 5
 
            foreach (int[] a in list)
                Console.WriteLine("{0} ({1})", String.Join(" ", a), MinReplaces(a));
        }
    }
}