popping numbers from an array...to make it sorted

[gregorynoob]

the problem is to find the minimum numbers to be popped from an array to make it sorted.
so for example 12534756, you can pop all but one, but it's best to pop 5 and 7 cause it's the least needed to make it sorted.
I'm having difficulties finding a good algorithm that doesn't try every possible way...
i tried splitting the array into sub-arrays, and putting them into a table indexed by the first and last indexes of the sub-array. so i'd give 0 to all sub-arrays of length 1 and 1 to those of length 2 where the first element is larger than the second..

for( int i = 0; i < n; ++i )
         for( int j = i+1; j <= n; ++j )

this is the idea how to go through the table but adding the values of two sub-arrays of a larger one resulted with huge numbers...
the table for the given example would look like this if i made it:
(for the first 4 numbers...i'm lazy)
[0] 0 0 1
0 [0] 0 1
0 0 [0] 1
0 0 0 [0]
the bracketed zeros are the ones with sub-array length 1..
the table actually gives the right result in this example, but for many others it's wrong
so all put in 4 words.. my algorithm skills suck! Help!! :)

[VernonDozier]

the problem is to find the minimum numbers to be popped from an array to make it sorted.
so for example 12534756, you can pop all but one, but it's best to pop 5 and 7 cause it's the least needed to make it sorted.
I'm having difficulties finding a good algorithm that doesn't try every possible way...
i tried splitting the array into sub-arrays, and putting them into a table indexed by the first and last indexes of the sub-array. so i'd give 0 to all sub-arrays of length 1 and 1 to those of length 2 where the first element is larger than the second..

for( int i = 0; i < n; ++i )
         for( int j = i+1; j <= n; ++j )

this is the idea how to go through the table but adding the values of two sub-arrays of a larger one resulted with huge numbers...
the table for the given example would look like this if i made it:
(for the first 4 numbers...i'm lazy)
[0] 0 0 1
0 [0] 0 1
0 0 [0] 1
0 0 0 [0]
the bracketed zeros are the ones with sub-array length 1..
the table actually gives the right result in this example, but for many others it's wrong
so all put in 4 words.. my algorithm skills suck! Help!! :)

This is not a trivial problem due to the fact that you must make an algorithm that works for any possible list. You definitely need to be drawing out all sorts of scenarios on paper, not jumping right into the coding. Here's one semi-brute-force, but not completely brute-force solution. You have a list. Attack it from both ends till you find two elements out of order (see green and red):

6 7 8 1 2 3 4 5

6 7 8 1 2 3 4 5

6 7 8 1 2 3 4 5

8 and 1 are out of order, so one of them needs to be eliminated, but which one? Try deleting each, then picking the one that ends up requiring fewer deletions in the resulting smaller list.

6 7 1 2 3 4 5

vs.

6 7 8 2 3 4 5

In this case deleting 8 is better, so start again with this list:

6 7 1 2 3 4 5

Rinse and repeat as necessary with successively smaller lists till you end up with an ordered list:

1 2 3 4 5

The nice thing about this is that if you code it well, you may not have to figure out the best way to solve:

6 7 1 2 3 4 5

after 8 was deleted since you may have already solved it before (i.e. you had to figure out how many deletions were required in the process of deciding whether to delete the 1 or the 8). So to optimize it, you can try to keep track of earlier calculations/solutions so you won't have to recalculate.

I imagine that this may not be the best solution in the world, but it's somewhat intelligent as far as leaving already sorted parts of the list alone and zoning in on the out of order elements and might be useful to help get you started.

[VernonDozier]

Here's an improvement on the previous algorithm. In the following list:

6 7 8 1 2 3 4 5

you need to definitely delete 8 or 1, but to figure out which to delete you shouldn't compare
the resulting lists of

6 7 8 2 3 4 5

vs.

6 7 1 2 3 4 5

but rather these lists:

6 7 8

vs.

1 2 3 4 5

You don't need to only delete one element per decision. If you keep 8, anything to the right of 8 that is less than 8 needs to be deleted. If you keep 1, anything to the left of 1 that is greater than 1 needs to be deleted, so you may as well delete them all at once rather than one at a time.

You should also consider deleting both, so you should really be comparing

6 7 8  (keep 8)

vs.

1 2 3 4 5 (keep 1)

vs.

6 7 2 3 4 5 (keep neither)

and picking the best of the three.

[gregorynoob]

hmmm, okay, so i've tried doing this with a recursive function...no success really, but it looks correct to me:

#include <cstdio>
#include <vector>
#include <algorithm>
#define MAX 1024

using namespace std;

int n; vector<int>nums;

int rec( vector<int> nums ) {
    if( nums.size() == 1 ) return 0;
    for( int i = 0; i < nums.size()-1; ++i ) {
         if( nums[i] > nums[i+1] ) {
             //printf( "%d\n%d\n", nums[i], nums[i+1] );
             vector<int> numsX( nums ), numsY( nums );
             numsX.erase( nums.begin()+i );
             numsY.erase( nums.begin()+i+1 );
             return min( rec( numsX )+1, rec( numsY )+1 );
         }
    }
    return 0;
}

int main( void )
{
    scanf( "%d", &n );
    for( int i = 0; i < n; ++i ) {
         int k; scanf( "%d", &k );
         nums.push_back( k );
    }
    
    printf( "%d\n", rec( nums ) );
    
    scanf( "\n" );
    return 0;
}

oops, i see the mistake in my for loop :P fixing it now...

[gregorynoob]

okay...recoded all...without vectors. it works now! but i don't know if my optimization is right, it kinda uses a lot of space! someone please take a look:

#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAX 100

using namespace std;

int n, nums[ MAX ], memo[ MAX ][ MAX ][ MAX ];
void ccopy( int a[], int b[], int n, int k ) {
     int j = 0;
     for( int i = 0; i < n; ++i ) {
          if( i != k ) b[j++] = a[i];
     }
}

int rec( int nums[], int n ){
    if( n == 1 ) return 0;
    for( int i = 0; i < n-1; ++i )
         if( nums[i] > nums[i+1] ) {
             int numsX[ MAX ], numsY[ MAX ];
             ccopy( nums, numsX, n, i );
             ccopy( nums, numsY, n, i+1 );
             if( memo[i][n][nums[i]] )return memo[i][n][nums[i]];
             if( memo[i+1][n][nums[i+1]] )return memo[i+1][n][nums[i+1]];
             memo[i][n][nums[i]] = memo[i+1][n][nums[i+1]] = min( rec( numsX, n-1 )+1, rec( numsY, n-1 )+1 );
             return memo[i][n][nums[i]];
         }
    return 0;
}

int main( void )
{
    memset( memo, 0, sizeof memo );
    scanf( "%d", &n );
    for( int i = 0; i < n; ++i ) scanf( "%d", &nums[i] );
    
    printf( "%d\n", rec( nums, n ) );
    
    scanf( "\n" );
    return 0;
}

[ArkM]

It's a slow O(n*n*n) with not optimal implementation solution.
It works (I have a proof of the algorithm correctness):

int setRank(const int* a, int n, int* b)
{
    int tot = 0;
    for (int v, s, k = 0; k < n; ++k)
    {
        if (b[k] >= 0)
        {
            s = 0;
            v = a[k];
            for (int i = 0; i < k; ++i)
                if (b[i] >= 0 && a[i] > v)
                    ++s;
            for (int i = k + 1; i < n; ++i)
                if (b[i] >= 0 && a[i] < v)
                    ++s;
            tot += (b[k] = s);
        }
    }
    return tot;
}

int idxMax(const int* b, int n)
{
    if (!b || n <= 1)
        return 0;
    int idx;
    for (idx = 0; idx < n && b[idx] < 0; ++idx)
        ;
    if (idx >= n)
        return -1;
    int val = b[idx];
    for (int i = idx + 1; i < n; ++i)
        if (b[i] >= 0 && b[i] > val)
            val = b[idx=i];
    return idx;
}

int makeOrder(const int* a, int n)
{
    if (!a || n <= 1)
        return 0;
    int *b = new int[n];
    for (int i = 0; i < n; ++i)
        b[i] = 0;

    int idx;
    while (setRank(a,n,b))
    {
        idx = idxMax(b,n);
        b[idx] = -1;
    }

    int skp = 0;
    for (int i = 0; i < n; ++i)
        if (b[i] < 0)
        {
            std::cout << '[' << i << "]:(" << a[i] << ")\n";
            ++skp;
        }
    std::cout << "\nRemoved:" << skp << std::endl;

    delete []b;
    return skp;
}

const int a[] = { 1, 2, 5, 3, 4, 7, 5, 6 };
const int n   = sizeof a/sizeof a[0];

int main()
{
    makeOrder(a,n);

    return 0;
}

[VernonDozier]

okay...recoded all...without vectors. it works now! but i don't know if my optimization is right, it kinda uses a lot of space! someone please take a look:

#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAX 100

using namespace std;

int n, nums[ MAX ], memo[ MAX ][ MAX ][ MAX ];
void ccopy( int a[], int b[], int n, int k ) {
     int j = 0;
     for( int i = 0; i < n; ++i ) {
          if( i != k ) b[j++] = a[i];
     }
}

int rec( int nums[], int n ){
    if( n == 1 ) return 0;
    for( int i = 0; i < n-1; ++i )
         if( nums[i] > nums[i+1] ) {
             int numsX[ MAX ], numsY[ MAX ];
             ccopy( nums, numsX, n, i );
             ccopy( nums, numsY, n, i+1 );
             if( memo[i][n][nums[i]] )return memo[i][n][nums[i]];
             if( memo[i+1][n][nums[i+1]] )return memo[i+1][n][nums[i+1]];
             memo[i][n][nums[i]] = memo[i+1][n][nums[i+1]] = min( rec( numsX, n-1 )+1, rec( numsY, n-1 )+1 );
             return memo[i][n][nums[i]];
         }
    return 0;
}

int main( void )
{
    memset( memo, 0, sizeof memo );
    scanf( "%d", &n );
    for( int i = 0; i < n; ++i ) scanf( "%d", &nums[i] );
    
    printf( "%d\n", rec( nums, n ) );
    
    scanf( "\n" );
    return 0;
}

I don't know what the rec function is supposed to do. I assume it's the number of deletions and if it is, there's a problem. When I type in this list of ten numbers:

43 82 20 4 64 13 3 1 36 45

I get a result of 7, which I assume means 7 deletions. However, I can get at least this solution:

4 13 36 45

and that is 6 deletions.

[gregorynoob]

i think the memoization is the problem...do you know a better way perhaps, cause mine is silly... it works on short examples just as a recursion
//edit
yea, confirmed...memoization causes the problem, if i use the plain recursion:

int rec( int nums[], int n ){
    if( n == 1 ) return 0;
    for( int i = 0; i < n-1; ++i )
         if( nums[i] > nums[i+1] ) {
             int numsX[ MAX ], numsY[ MAX ];
             ccopy( nums, numsX, n, i );
             ccopy( nums, numsY, n, i+1 );
             return min( rec( numsX, n-1 ) + 1, rec( numsY, n-1 ) + 1 );
         }
    return 0;
}

i get the right answers...
could you please help me optimize it? and thanks for the help you've already given me!

[VernonDozier]

i think the memoization is the problem...do you know a better way perhaps, cause mine is silly... it works on short examples just as a recursion

A better algorithm or a better way to code it? As far as algorithms go, the two algorithms I listed earlier can be improved on, but I think they are better than the one you are using, which I don't understand. I don't think you need the 3-dimensional vector. One-dimensional should do you fine, though you may need a few of them, and I think you can keep the recursion in there. You're passing the function two arrays in the first example, three in the second. You're taking the one with the fewest deletions as your answer and throwing out the other two. You're continually calling it with smaller arrays. The second algorithm I listed is getting rid of more elements each pass, so it should be better. Might be easier to code if you use vectors. There's less to keep track of when you delete elements and copy the vectors, along with more efficient use of space. You can always, after you solve it with vectors, change it to arrays.

[ArkM]

Let a is an array of comparable items.
Let's define functions inv(i,j), inv(i):

{ 1 if a[k] < a[m], k > m
inv{k,m) = |  1 if a[i] > a[m], k < m
                 { 0 otherwise
            
inv(k)   = sum of inv(k,i), i != k

Obviously, sum of inv(i), i = [0..n) (let it named as an array defect, or inv(a) ) is equal to 0 if and only if an array is ordered. In this terms we can reformulate the task specification now:

Find the shortest element by element removing sequence a => a' => ... =>a* where inv(a*) == 0.

If we remove k-th element from the array (transform a => a')

inv(a') = inv(a) - 2*inv(k)

So the step of (optimal) algorithm is:

select k: inv(k) == max of inv(i), i = [0..n')
 remove a'[k] (a' => a")
 recalculate inv(i) for all elements of a"

Taking into account that inv'(k') <= inv(k) for every leaved array element, we may conclude:
1. It's true optimal algorithm.
2. There are several possible solutions in common case.