Python program to find Smallest Derangement of Sequence in Heap

In this tutorial, we will go through a program to compute the lexicographically smallest (earliest in dictionary order) derangement of a sequence in Python.

Given a sequence: S = 1,2,3….n, a derangement of S is any permutation of S such that no two elements in S and its permutation occur at the same position. For example, if S = {1,2,3}, one of its derangement could be its reversed sequence i.e. {3,2,1}. But, it might not necessarily be the smallest derangement.

We will be using a min-heap where we can successively get the least element and place them in more significant positions (minimum index positions). We will execute this algorithm while maintaining the property of derangement.

In the function call, we will have the given sorted_sequence as the parameter. The output we will get is the smallest derangement sequence list which doesn’t have any common element with the sorted_sequence list.

Program for Smallest Derangement of Sequence in Python

import copy

def lexicographical_smallest_derangement_sequence(sorted_sequence):
    length = len(sorted_sequence)
    derangement_sequence = [-1] * length
    min_heap = copy.deepcopy(sorted_sequence)

    for i in range(length):
        min_heap.sort() # used for heapifying min heap
        first_min = min_heap[0] # stores first minimum value of heap

        if first_min != sorted_sequence[i] or len(min_heap) == 1:
            derangement_sequence[i] = first_min
            del min_heap[0] # removing first minimum
        else:
            second_min = min_heap[1] # stores second minimum value of heap 
            derangement_sequence[i] = second_min
            del min_heap[1] # removing second minimum

    if derangement_sequence[length - 1] == sorted_sequence[length - 1] and length >= 2:
        temp = derangement_sequence[length - 2]
        derangement_sequence[length - 2] = derangement_sequence[length - 1]
        derangement_sequence[length - 1] = temp
    return derangement_sequence

sorted_sequence = [1, 2, 3, 4, 5, 6, 7]
print(lexicographical_smallest_derangement_sequence(sorted_sequence))

Output:

[2, 1, 4, 3, 6, 7, 5]

We will begin by getting the length of the given sequence. Then we will create a list for storing the derangement sequence with the same length as the given sequence.

Using the copy module, we will apply deepcopy() method on the sorted sequence to get the min_heap. This we will need for removing the first minimum or second minimum based on the match with the given sorted_sequence.

Using a for loop, we will call sort() method on min_heap for heapifying the min-heap. We will also store the first minimum value of the heap in the first_min variable.

Within the for loop, if there is no match between the first minimum value from heap and ith element at sorted_sequence after removing i-1 elements from the heap, we will remove only the first minimum from the heap and consider this value in the derangement sequence. Otherwise, we will remove only the second minimum from the heap and consider it in the derangement sequence.

Finally, if the last element is the same for given sorted_sequence and derangement_sequence, we will swap the last two elements of derangement_sequence. The time complexity of the program is O(N * log N).

Read More: Python program to find Largest Derangement of Sequence in Heap