Algorithm to count the number of valid blocks in a permutation

Question

Possible Duplicate:
Finding sorted sub-sequences in a permutation

Given an array A which holds a permutation of 1,2,...,n. A sub-block A[i..j]
of an array A is called a valid block if all the numbers appearing in A[i..j]
are consecutive numbers (may not be in order）.

Given an array A= [ 7 3 4 1 2 6 5 8] the valid blocks are [3 4], [1,2], [6,5],
[3 4 1 2], [3 4 1 2 6 5], [7 3 4 1 2 6 5], [7 3 4 1 2 6 5 8]

So the count for above permutation is 7.

Give an O( n log n) algorithm to count the number of valid blocks.

Answer 1

My proposition

STEP = 2 // amount of examed number

B [0,0,0,0,0,0,0,0]

B [1,1,0,0,0,0,0,0]

VALID(A,B) - if not valid move one

B [0,1,1,0,0,0,0,0]

VALID(A,B) - if valid move one and step

B [0,0,0,1,1,0,0,0]

VALID (A,B)

B [0,0,0,0,0,1,1,0]

STEP = 3

B [1,1,1,0,0,0,0,0] not ok

B [0,1,1,1,0,0,0,0] ok

B [0,0,0,0,1,1,1,0] not ok

STEP = 4

B [1,1,1,1,0,0,0,0] not ok

B [0,1,1,1,1,0,0,0] ok

.....

CON <- 0
STEP <- 2
i <- 0
j <- 0
WHILE(STEP <= LEN(A)) DO
 j <- STEP
 WHILE(STEP <= LEN(A) - j) DO
  IF(VALID(A,i,j)) DO
   CON <- CON + 1
   i <- j + 1
   j <- j + STEP
  ELSE
   i <- i + 1
   j <- j + 1
  END
 END
 STEP <- STEP + 1
END

The valid method check that all elements are consecutive

Never tested but, might be ok

Answer 2

Ok, I am down to 1 rep because I put 200 bounty on a related question: http://stackoverflow.com/questions/1824388/finding-sorted-sub-sequences-in-a-permutation so I cannot leave comments for a while.

I have an idea: 1) Locate all permutation groups. They are: (78), (34), (12), (65). Unlike in group theory, their order and position, and whether they are adjacent matters. So, a group (78) can be represented as a structure (7, 8, false), while (34) would be (3,4,true). I am using Python's notation for tuples, but it is actually might be better to use a whole class for the group. Here true or false means contiguous or not. Two groups are "adjacent" if (max(gp1) == min(gp2) + 1 or max(gp2) == min(gp1) + 1) and contigous(gp1) and contiguos(gp2). This is not the only condition, for union(gp1, gp2) to be contiguous, because (14) and (23) combine into (14) nicely. This is a great question for algo class homework, but a terrible one for interview. I suspect this is homework.

Answer 3

(This is an attempt to do this N.log(N) worst case. Unfortunately it's wrong -- it sometimes undercounts. It incorrectly assumes you can find all the blocks by looking at only adjacent pairs of smaller valid blocks. In fact you have to look at triplets, quadruples, etc, to get all the larger blocks.)

You do it with a struct that represents a subblock and a queue for subblocks.

  struct
c_subblock
{
  int           index   ;  /* index into original array, head of subblock */
  int           width   ;  /* width of subblock > 0 */
  int           lo_value;
  c_subblock *  p_above ;  /* null or subblock above with same index */
};

Alloc an array of subblocks the same size as the original array, and init each subblock to have exactly one item in it. Add them to the queue as you go. If you start with array [ 7 3 4 1 2 6 5 8 ] you will end up with a queue like this:

queue: ( [7,7] [3,3] [4,4] [1,1] [2,2] [6,6] [5,5] [8,8] )

The { index, width, lo_value, p_above } values for subbblock [7,7] will be { 0, 1, 7, null }.

Now it's easy. Forgive the c-ish pseudo-code.

loop {
  c_subblock * const p_left      = Pop subblock from queue.
  int          const right_index = p_left.index + p_left.width;
  if ( right_index < length original array ) {
    // Find adjacent subblock on the right.
    // To do this you'll need the original array of length-1 subblocks.
    c_subblock const * p_right = array_basic_subblocks[ right_index ];
    do {
      Check the left/right subblocks to see if the two merged are also a subblock.
        If they are add a new merged subblock to the end of the queue.
      p_right = p_right.p_above;
    }
    while ( p_right );
  }
}

This will find them all I think. It's usually O(N log(N)), but it'll be O(N^2) for a fully sorted or anti-sorted list. I think there's an answer to this though -- when you build the original array of subblocks you look for sorted and anti-sorted sequences and add them as the base-level subblocks. If you are keeping a count increment it by (width * (width + 1))/2 for the base-level. That'll give you the count INCLUDING all the 1-length subblocks.

After that just use the loop above, popping and pushing the queue. If you're counting you'll have to have a multiplier on both the left and right subblocks and multiply these together to calculate the increment. The multiplier is the width of the leftmost (for p_left) or rightmost (for p_right) base-level subblock.

Hope this is clear and not too buggy. I'm just banging it out, so it may even be wrong. [Later note. This doesn't work after all. See note below.]

Answer 4

Like everybody else, I'm just throwing this out ... it works for the single example below, but YMMV!

The idea is to count the number of illegal sub-blocks, and subtract this from the total possible number. We count the illegal ones by examining each array element in turn and ruling out sub-blocks that include the element but not its predecessor or successor.

1. Foreach i in [1,N], compute B[A[i]] = i.

2. Let Count = the total number of sub-blocks with length>1, which is N-choose-2 (one for each possible combination of starting and ending index).

3. Foreach i, consider A[i]. Ignoring edge cases, let x=A[i]-1, and let y=A[i]+1. A[i] cannot participate in any sub-block that does not include x or y. Let iX=B[x] and iY=B[y]. There are several cases to be treated independently here. The general case is that iX<i<iY<i. In this case, we can eliminate the sub-block A[iX+1 .. iY-1] and all intervening blocks containing i. There are (i - iX + 1) * (iY - i + 1) such sub-blocks, so call this number Eliminated. (Other cases left as an exercise for the reader, as are those edge cases.) Set Count = Count - Eliminated.

4. Return Count.

The total cost appears to be N * (cost of step 2) = O(N).

WRINKLE: In step 2, we must be careful not to eliminate each sub-interval more than once. We can accomplish this by only eliminating sub-intervals that lie fully or partly to the right of position i.

Example:
A = [1, 3, 2, 4] B = [1, 3, 2, 4]

Initial count = (4*3)/2 = 6

i=1: A[i]=1, so need sub-blocks with 2 in them. We can eliminate [1,3] from consideration. Eliminated = 1, Count -> 5.

i=2: A[i]=3, so need sub-blocks with 2 or 4 in them. This rules out [1,3] but we already accounted for it when looking right from i=1. Eliminated = 0.

i=3: A[i] = 2, so need sub-blocks with [1] or [3] in them. We can eliminate [2,4] from consideration. Eliminated = 1, Count -> 4.

i=4: A[i] = 4, so we need sub-blocks with [3] in them. This rules out [2,4] but we already accounted for it when looking right from i=3. Eliminated = 0.

Final Count = 4, corresponding to the sub-blocks [1,3,2,4], [1,3,2], [3,2,4] and [3,2].

Answer 5

This question does involve a bit of a "math trick" but it's fairly straight forward once you get it. However, the rest of my solution won't fit the O(n log n) criteria.

The math portion:

For any two consecutive numbers their sum is 2k+1 where k is the smallest element. For three it is 3k+3, 4 : 4k+6 and for N such numbers it is Nk + sum(1,N-1). Hence, you need two steps which can be done simultaneously:

1. Create the sum of all the sub-arrays.
2. Determine the smallest element of a sub-array.

The dynamic programming portion

Build two tables using the results of the previous row's entries to build each successive row's entries. Unfortunately, I'm totally wrong as this would still necessitate n^2 sub-array checks. Ugh!

Answer 6

The original array doesn't contain duplicates so must itself be a consecutive block. Lets call this block (1 ~ n). We can test to see whether block (2 ~ n) is consecutive by checking if the first element is 1 or n which is O(1). Likewise we can test block (1 ~ n-1) by checking whether the last element is 1 or n.

I can't quite mould this into a solution that works but maybe it will help someone along...

Answer 7

I posted a worst-case O(n log n) algorithm in the other thread: http://stackoverflow.com/questions/1824388/finding-sorted-sub-sequences-in-a-permutation/3346677#3346677