Suppose I have n distinct integers. I want to place these integers in an "array". However, between each element in the "array" is an inequality sign. So, the numbers need to be entered in a fashion that satisfies the inequality. The n distinct integers are in random order. So, how could I do this? Would pre-sorting the integers help, and is so how, because the inequalities could be in any order.

Thanks.

Thanks.

Do more with

EXPERT OFFICE^{®} is a registered trademark of EXPERTS EXCHANGE^{®}

You will typically find several local minima and maxima, and the run lengths between them.

If you do that, and presort the integers, the filling-in algorithm may be come clear.

c and e are local maxima. They are not less than anything. One of them has to be the absolute maximum.

a d and j are local minima. They are not greater than anything. One of them has to be the absolute minimum.

You have to work several examples by hand to see what's going on.

Do you need to find a solution, or find out how many solutions there are?

>> recursive function to arrange the array in every possible order

For an n-element array, that would take on the order of n! operations.

But sorting the integers only takes on the order of n*log(n) operations.

And the analysis of the inequalities takes on the order of n operations.

but at that point the solution is not yet solved, or is it? In your simple example you said that there are two local maxima, and that one of these is the absolute maxima, but how to determine which?

I agree that to attempt a solution for a sufficiently large n, something more sophisticated than all combinations is required.

but at that point the solution is not yet solved, or is it?

It is solved. Once you have analyzed the array and sorted the list of integers, there are a number of O=n strategies to finish.

If you have n integers, then you will have (n-1) inequalities and 2^(n-1) possible array configurations.

Note that the number of maxima and minima are constrained: every local maxima is

associated with exactly one or two local minima, and vice versa.

So Number of Max = Number of Min +/- 1 for all configurations.

If all the inequalities are the same, there will be one max and one min and only one way

to fill in the numbers -- the sorted list in order.

If the direction of the inequalities changes in every position, then every location will be

either a local max or min. One strategy to fill in the numbers is to fill in all the max's

from the high side of the list and the min's from low side. Order doesn't matter.

There will be something like ((n/2)!)^2 possible solutions.

For the intermediate cases, where there are local max and minima with some runs

in between, you can fill in the max and minima as before, and then fill in the rest

top-down or bottom up in a straight forward fashion.

## Premium Content

You need an Expert Office subscription to comment.Start Free Trial