Как найти минимальное количество переключателей для сортировки данной перестановки (скажем, от 1 до 10) в порядке возрастания - PullRequest
Новая
       47

Как найти минимальное количество переключателей для сортировки данной перестановки (скажем, от 1 до 10) в порядке возрастания

3 голосов
/ 01 августа 2020

У короля Артура есть полка с 10 книгами с номерами 1,2,3, ..., 10. С годами объемы стали беспорядочными. Артур пытается расположить книги в порядке возрастания, меняя позиции сразу двух книг. Поскольку книги тяжелые, он может менять только два тома каждый день. Помогите Мерлину упорядочить книги.

Например, если перестановка равна 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, то нам нужно всего 5 переключателей, чтобы отсортировать их в порядке возрастания

Примечание: в худшем случае будет 9 переключателей

Q1. Найдите перестановку, соответствующую худшему случаю

Q2. Как найти минимальное количество переключателей, необходимых для данной перестановки. (Алгоритм и, если возможно, код в любом из C, C ++, python)

PS: Я смог решить это вручную, лучше сказать, ошибка Trial N (ответ на Q1. 10, 1, 2 , 3, 4, 5, 6, 7, 8, 9). но я должен sh знать алгоритм

Ответы [ 2 ]

3 голосов
/ 01 августа 2020

Минимальное необходимое количество перестановок равно общему количеству элементов, вычтенному на количество циклов перестановки . В худшем случае может быть один цикл. Мы можем получить для него перестановку, сдвинув естественный порядок вниз или вверх один раз (например, 1 2 3 -> 2 3 1 или 3 1 2).

Например: 

1 2 3 4 5
2 5 4 3 1

Start with 1 and follow the cycle:
1 down to 2, 2 down to 5, 5 down to 1.

1 -> 2 -> 5 -> 1
3 -> 4 -> 3

Нам нужно поменять местами индекс 1 на 5, а затем индекс 5 на 2; а также индекс 3 с индексом 4. Всего 3 свопа или n - 2.

Мы вычитаем n на количество циклов, так как элементы цикла вместе составляют n, и каждый цикл представляет собой своп меньше, чем количество элементов в нем.

Например: 

 1 2 3 4 5 6 7 8 9 10
10 9 8 7 6 5 4 3 2 1

1 -> 10 -> 1
2 -> 9 -> 2
3 -> 8 -> 8
4 -> 7 -> 4
5 -> 6 -> 5

Циклы перестановки: 

(10 1)(9 2)(8 3)(7 4)(6 5)

Q1 = num_elements - num_cycles
   = 10 - 5
   = 5

Чтобы получить наихудший случай (Q2), сдвиньте естественный порядок вниз или до одного раза. Например, сдвиг на 1 вниз: 

1  2  3  4  5  6  7  8  9 10
2  3  4  5  6  7  8  9 10  1

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 1

Permutation cycles (just one):

(2 3 4 5 6 7 8 9 10 1)

Или сдвиг на 1 вверх: 

 1  2  3  4  5  6  7  8  9 10
10  1  2  3  4  5  6  7  8  9

1 -> 10 -> 9 -> 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1

Permutation cycles (just one):

(10 9 8 7 6 5 4 3 2 1)

Результат: 

Q2 = num_elements - num_cycles
   = 10 - 1
   = 9
3 голосов
/ 01 августа 2020

Используя 1-индексированный список,

Взяв список, содержащий те же элементы, что и в примере, приведенном в вопросе:

[0,10,9,8,7,6, 5,4,3,2,1] # Добавлен 0 впереди, чтобы сделать список 1-проиндексированным

Step1: взять последний индекс списка ... как итератор

Step2: Выполняется некоторое время l oop, пока значение итератора не станет больше 0

Step3: Если элемент в итераторе совпадает с value, то мы должны уменьшить значение итератора, так как нет необходимости выполнять операцию свопинга.

Step4: Если элемент не совпадает, поменяйте местами элемент со значением его индекса и увеличиваем количество операций на 1. Нет необходимости уменьшать значение итератора, поскольку это может быть случай, когда значение, которое мы получили в позиции итератора, может не совпадать с его индексом ...

Время Сложность решения: O (2 * N) ~~ O (N) . 

arr = [0,10, 1, 2, 3, 4, 5, 6, 7, 8, 9]
iterator = 10
count_of_operations = 0
while(iterator>0):
    index_to_swap = arr[iterator]
    if(index_to_swap == iterator):
        iterator = iterator - 1
    else:
        arr[iterator],arr[index_to_swap] = arr[index_to_swap],arr[iterator]
        count_of_operations = count_of_operations + 1
        
print(count_of_operations)
...