2
$\begingroup$

Array $P$ of length $n$ is a permutations of $\{0, ..., n-1\}$

Write a code, which would in $O(n)$ create an array $R$ of length $n$, so for values $x_i, x_j \in P$, $R[x_i] < R[x_j]$ if $x_i$ is on the left of $x_j$ ($i<j$).

This is a algorithmization problem that's recurring in the final's test each year and I'm stuck with it for weeks. I know that I'm supposed to show my work before asking here, but I didn't know how to start.

Could you at least point me to the right direction? What technique do I use, dynamic programming? Is this a problem for a specific algorithm?

$\endgroup$
  • $\begingroup$ "Value $x$ in array $P$ is on a lower index than value $y$ in array $P$". Does it mean "the index of value $x$ in array $P$ is smaller than the index of value $y$ in array $P$"? $\endgroup$ – Apass.Jack May 19 at 12:17
  • $\begingroup$ Have you tried to find which element of $R$ should be mapped to 0? Then which element of $R$ should be mapped to 1? 2? And so on. $\endgroup$ – Apass.Jack May 19 at 12:25
  • 1
    $\begingroup$ @Apass.Jack Well, it's exactly how I translated it. $\endgroup$ – james F. May 19 at 13:09
1
$\begingroup$

All you're looking for is some mapping between the elements of $P$ and their indexes, that can be found in $O(1)$ for each element of $P$. Suppose given $p_i \in P$, you can use the fact that $p_i \in \{0, \dots n-1\}$, and that no $p_j \in P$ exists s.t $p_j = p_i$ (other than $j=i$).

How will you do it? Set $R[x]$ to the index of element $x \in P$.

  • Since $x$ is unique, no elements of $R$ will be overridden.
  • Suppose $p_i , p_j \in P$, and $p_i$ occures before $p_j$ ($i<j$). Then $R[p_i] = i$ and $R[p_j] = j$, and it holds that $R[p_i]<R[p_j]$

You should be able to take it from here.

$\endgroup$
0
$\begingroup$

Hint, try to determine which element of $R$ should be mapped to 0.

Then try to determine which element of $R$ should be mapped to 1. You will get the idea.


Here is the pseudocode.

Input: array $P[0], P[1], \cdots, P[n-1]$, which is a permutation of $0, 1, \cdots, n-1$.

Output: array $R[0], R[1], \cdots, R[n-1]$, which is a permutation of $0, 1, \cdots, n-1$ such that if $i<j$, then $R[P[i]] < R[P[j]]$.

Procedure: For $i$ in 0 to $n-1$ inclusive, let $R[P[i]]=i$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.