How to determine if a sequence is bitonic?

A sequence is bitonic if it monotonically increases and then monotonically de- creases, or if it can be circularly shifted to monotonically 开发者_如何转开发increase and then monotonically decrease. For example the sequences (1, 4, 6, 8, 3, −2) , (9, 2, −4, −10, −5) , and (1, 2, 3, 4) are bitonic, but (1, 3, 12, 4, 2, 10) is not bitonic.

How can it be determined if given sequence is bitonic?

I have the following opinion. We can walk till n/2, where n is the length of the array, and check if

(a[i] < a[i + 1]) and (a[n - i - 1] < a[n-1 - (i + 1)])

Is this correct?

A bitonic sequence:

 /\
/  \
    \/

Not a bitonic sequence:

 /\    
/  \  / (higher than start)
    \/

Obviously if the direction changes more than two times we cannot have a bitonic sequence.
If the direction changes less than two times, we must have a bitonic sequence.

If there are two changes in direction, we MAY have a bitonic sequence. Consider the two ascii images above. Clearly a sequence with two changes in direction will match one of the patterns (allowing for a reflection). Thus, we set the initial direction by comparing the first and last elements. Since these can be the same, we use the first element that is not equal to the last element.

Here is an implementation in Java:

    public static Boolean bitonic(int[] array) {
        if (array == null) return false;
        if (array.length < 4) return true;
        Boolean dir;// false is decreasing, true is increasing
        int pos = 0, switches = 0;
        while (pos < array.length) {
            if (array[pos] != array[array.length - 1])
                break;
            pos++;
        }
        if (pos == array.length) return true;
        //pos here is the first element that differs from the last
        dir = array[pos] > array[array.length - 1];
        while (pos < array.length - 1 && switches <= 2) {
            if ((array[pos + 1] != array[pos]) &&
               ((array[pos + 1] <= array[pos]) == dir)) {
                dir ^= true;
                switches++;
            }
            pos++;
        }
        return switches <= 2;
    }

• Traverse the array forwards, wrapping around when you hit the end (code below)
• Count the total number of inflection points you find, if num_inflection_points==2 then your array is bitonic.
• The runtime of this should be O(n).

Here's a working example in c++:

bool is_bitonic(const vector<int>& v) {
  bool was_decreasing = v.back() > v.front();
  int num_inflections = 0;
  for (int i = 0; i < v.size() && num_inflections <= 2; i++) {
    bool is_decreasing = v[i] > v[(i+1)%v.size()];
    // Check if this element and next one are an inflection.
    if (was_decreasing != is_decreasing) {
      num_inflections++;
      was_decreasing = is_decreasing;
    }
  }
  return 2 == num_inflections;
}

• Notes, depending on your implementation:

Note 1: Here's the basic idea for traversing an array circularly:

for (int i = ip_index; i < array_length; i++) {
   int index = (i + 1) % array_length;  // wraps around to beginning
   // Retrieve the value with
   DoSomethingWithValue(array[index];)
}

Note 2: It might simplify the code to circularly loop length + 1 elemnts, which will guarantee you find both inflection points.

Note 3: Or, it might simplify the code if you always look for the first inflection point that goes increasing to decreasing (before searching for other inflection points). That way, your scan only has to take worry about finding exactly one other inflection point with the opposite flip.

Note 4: As for your example, you can't use N/2, because the inflection point doesn't necessarily occur at the midpoint of the array.

Here is an efficient and simple implementation in Java. It traverses the array only once to determine whether the array is bitonic or not. It uses a variable reversal that counts the number of direction reversals of monotonicity in the array (including the circular wrapping around).

The variable trend can have three values:

• 0, if the values are the same;
• 1, if the array is monotonically increasing;
• -1, if the array is monotonically decreasing.

public static boolean bitonic(int[] arr) {
  int reversal = 0;
  int len = arr.length;
  int trend = 0; // 0 means any, 1 means increasing, -1 means decreasing 
  for (int i= 0; i < len ; i++) {
    if(arr[i%len] < arr[(i+1)%len]){
      if (trend == 0) trend = 1;
      else if ( trend == -1) {
        reversal ++;
        trend = 1;
      }
    }
    else if(arr[i%len] > arr[(i+1)%len]){
      if (trend == 0) trend = -1;
      else if ( trend == 1) {
        reversal ++;
        trend = -1;
      }
    }
    if(reversal > 2) return false;
  }
  return true;
}

You can look for the peak, i.e. when a[i-1] < a[i] && a[i] > a[i+1], then a[i] is the local peak (taking care of wrap around with modulus operator).

In a bitonic sequence, there can only be one such peak. Once you found the peak, then you can walk downhill to the left (wrapping around as necessary, again using modulus) until you found an uphill. Then you go back to the peak, walk downhill to the right, until you found another uphill. Now, if a sequence is bitonic, then you will have covered the whole sequence by going downhill on both sides.

btw, do I misunderstood the question, or is your first example not bitonic?

There need to be exactly two (or, depending on how your definition deals with degeneracy, exactly 0) transitions between rising and falling. Don't forget to check the transition between a[n] and a[0].