Largest Derangement of a Sequence

Given any sequence $S = {a_1, a_2 dots a_n }$ , find the largest derangement of $S$ .

A derangement $D$ is any permutation of $S$ , such that no two elements at the same position in $S$ and $D$ are equal.

The Largest Derangement is such that $D_i > D_{i+1}, forall i$ .

Examples:

Input : seq[] = {5, 4, 3, 2, 1}
Output : 4 5 2 1 3

Input : seq[] = {56, 21, 42, 67, 23, 74}
Output : 74, 67, 56, 42, 23, 21

Recommended: Please try your approach on {IDE} first, before moving on to the solution.

Since we are interested in generating largest derangement, we start putting larger elements in more significant positions.

Start from left, at any position $i$ place the next largest element among the values of the sequence which have not yet been placed in positions before $i$ .

To scan all positions takes N iteration. In each iteration we are required to find a maximum numbers, so a trivial implementation would be $O(N^2)$ complexity,

However if we use a data structure like max-heap to find the maximum element, then the complexity reduces to $O(N * log{N})$

Below is C++ implementation.

// CPP program to find the largest derangement 
#include <bits/stdc++.h> 
using namespace std; 
  
void printLargest(int seq[], int N) 
{ 
    int res[N]; // Stores result 
  
    // Insert all elements into a priority queue 
    std::priority_queue<int> pq;  
    for (int i = 0; i < N; i++)  
        pq.push(seq[i]);     
  
    // Fill Up res[] from left to right 
    for (int i = 0; i < N; i++) { 
        int d = pq.top(); 
        pq.pop(); 
        if (d != seq[i] || i == N - 1) { 
            res[i] = d; 
        } else { 
  
            // New Element poped equals the element  
            // in original sequence. Get the next 
            // largest element 
            res[i] = pq.top(); 
            pq.pop(); 
            pq.push(d); 
        } 
    } 
  
    // If given sequence is in descending order then  
    // we need to swap last two elements again 
    if (res[N - 1] == seq[N - 1]) { 
        res[N - 1] = res[N - 2]; 
        res[N - 2] = seq[N - 1]; 
    } 
  
    printf("
Largest Derangement
"); 
    for (int i = 0; i < N; i++)  
        printf("%d ", res[i]); 
} 
  
// Driver code 
int main() 
{ 
    int seq[] = { 92, 3, 52, 13, 2, 31, 1 };  
    int n = sizeof(seq)/sizeof(seq[0]); 
    printLargest(seq, n); 
    return 0; 
} 

Output:

Sequence: 
92 3 52 13 2 31 1 
Largest Derangement 
52 92 31 3 13 1 2

Note:
The method can be easily modified to obtain the smallest derangement as well.
Instead of a Max Heap, we should use a Min Heap to consecutively get minimum elements

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

Largest Derangement of a Sequence

Recommended: Please try your approach on {IDE} first, before moving on to the solution.

tags:

leave a comment

0 Comments

Subscribe to Our Newsletter

Top Followed books