CODEWITHSUNDEEP
arraysalgorithm
Vinodhini Chockalingam
Vinodhini Chockalingam

Reputation: 326

Generate the output array A[] when the number of items greater than a[i] for indices greater than i is given

Given an N-length array B, find the permutation of [1 .. N], A, such that B[i] is the number of elements in A that are greater than A[i] for all indices greater than i.

Example: N = 4, B=[1 1 1 0]

Output : A=[3 2 1 4]

Could anyone help me with an algorithm for this question?

Further explanation: B[i] has the number of items greater than A[i] in array A[] after index i. i.e. for all indices greater than i. for eg : B[2]=1 that means after the 3rd element in A[] there is one element that is greater than A[2].

Thanks in advance

Upvotes: 0

Views: 112

Answers (2)

Jeppe Stig Nielsen
Jeppe Stig Nielsen

Reputation: 61952

This seems to work: Start with a temporary list T := [ N, N-1, N-2, ..., 3, 2, 1 ]. This list is indexed from 0 through N-1 like a List<int> in C#.

Take T[B[0]]. That's you 0th member of the result array, so set A[0] := T[B[0]]. Remove this number from T. The list T now has one element less. It is now indexed 0 through N-2.

Then set A[1] := T[B[1]], and remove that number from T. And so on, A[i] := T[B[i]], where T at any time contains only the until then "unused" numbers.

In pseudo-code:

set T := [ N, N-1, N-2, ..., 3, 2, 1 ]
for (i from 0 through N-1)
    A[i] := T[B[i]]
    T.RemoveAtIndex(B[i])

The example from the question, B=[1 1 1 0], goes like this:

  • T = [ 4, 3, 2, 1 ], A = [ ]

Read and remove at index 1:

  • T = [ 4, 2, 1 ], A = [ 3 ]

Read and remove at index 1:

  • T = [ 4, 1 ], A = [ 3, 2 ]

Read and remove at index 1:

  • T = [ 4 ], A = [ 3, 2, 1 ]

Read and remove at index 0:

  • T = [ ], A = [ 3, 2, 1, 4 ]

Edit: I found out that this is called Lehmer codes.

Upvotes: 3

MNZ
MNZ

Reputation: 865

One of the answers comes in my mind is the algorithm below:

For i = N to 1
   A[i] = N - B[i]
   For j = i+1 to N
      If A[j] <= A[i]
         A[j]--

Upvotes: 0

Related Questions