Python program to find Largest Derangement of Sequence in Heap

In this tutorial, we are going to find the largest Derangement of Sequence using the heap data structure in Python. We will be given a sequence S of length n. The Derangement means the shuffling of items from its original position in the sequence. The largest Derangement can be obtained by shifting the maximum element of the remaining sequence to the first position and so on.

Using Heap in Python

The default heap in python “heapq” library is min-heap. The insertion and deletion take O(logn) time complexity. But it is beneficial to us as we get the maximum heap build in O(nlogn) time complexity. Rather than using the naive approach of traversing the sequence and finding the maximum in the remaining sequence which takes O(n^2) time complexity.

Here we have to use a little trick to use Min Heap as Max – Heap. We multiply each element by -1 and then insert them in heap. When popping elements multiply then with -1 and get the respective element.

nums = [4,5,3,9,1,6]
pq = []
heapify(pq)
for i in range(len(nums)):
    heappush(pq, -1* nums[i])

// pq = [-9, -6, -5, -4, -3, -1]

for i in range(len(nums)):
    print(-1 * heappop(pq), end = ' ')

// output = 9 6 5 4 3 2 1

We need to consider the possibility that derangementSequence[ n – 1 ] = sequence[ n – 1 ] in case of decresing sequence is given.

Find Largest Derangement of Sequence in Heap in Python

Let us move to code in Python.

from heapq import heappop, heappush, heapify 

n = 7
sequence = [11,80,62,88,2,70,13]
derangedSeq = []
pq = []
heapify(pq)

for i in range(n):
    heappush(pq, -1 * sequence[i])

for curr in range(n):
    x = heappop(pq) * -1
    if (curr+1 == n or x != sequence[curr]):
        derangedSeq.append(x)
    else:
        y = heappop(pq) * -1   # if the largest element to be placed is at curr position
        derangedSeq.append(y)  # we get the next largest element from heap
        heappush(pq, -1 * x)


# Swapping the last two elements if the sequence is in descending order 
if (derangedSeq[n-1] == sequence[n-1]) :
    derangedSeq[n-1] , derangedSeq[n-2] = derangedSeq[n-2], derangedSeq[n-1]

print("Largest Derangement Sequence");
for i in range(n):
    print(derangedSeq[i], end = " ")
Input :
sequence = [11,80,62,88,2,70,13]
Output :
Largest Derangement Sequence
88 70 80 62 13 11 2

In the code above, we have simply created a Priority Queue(Max Heap) in Python and pushed all elements of the given sequence to it. Then the elements in the priority_queue are sorted in decreasing order. We just pop elements one by one and check that the position of this element we popped is not the same as in the given sequence. If the position is the same, we pop the next element in PQ and put it in the derangedSeq and push the earlier popped element back because now it will not match the position in the given sequence ever and can be pushed in the next iteration.

In the end, we check if the end elements of the given sequence and derangedSeq are equal or not. If equal, then we swap the last two elements in the deranged sequence.

Another example is here:

Below is the code explanation:

  1. We simply initialize 2 empty lists one of size n and the other will be appended with n elements.
  2. then we traverse through the list and always adding the max element of the appended list to a variable and then removing the particular element from the list.
  3. we then check if the element is not equal to the position of current i value in the list.
  4. if the element is not equal to the current value we then add it to the empty list and if it is the current value we then append the next highest value and append the value to the list.
  5. In this way, we find out the largest derangement of the sequence.

The time complexity is of O(n).

 

def la(s,n):
    res=[None]*n
    pq=[]
    for i in range(n):
        pq.append(s[i])
    for i in range(n):
        d=max(pq)
        pq.remove(d)
        if(d!=s[i] or i==n-1):
            res[i]=d
        else:
            res[i]=max(pq)
            pq.remove(res[i])
            pq.append(d)
    if(res[n-1]==s[n-1]):
        res[n-1]=res[n-2]
        res[n-2]=s[n-1]
    print("Largest Derangement of this of the elements is:")
    for i in res:
        print(i)
n=list(map(int,input().strip().split(' ')))
la(n,len(n))

 

Leave a Reply

Your email address will not be published. Required fields are marked *