¿Cómo determinar si una secuencia es bitónica?

Question

Una secuencia es bitónica si aumenta monótonamente y luego monótonamente de- pliegues, o si se puede desplazar circularmente para aumentar monótonamente y luego disminuir monótonamente. Por ejemplo, las secuencias (1, 4, 6, 8, 3, -2), (9, 2, -4, -10, -5) y (1, 2, 3, 4) son bitónicas, pero (1, 3, 12, 4, 2, 10) no es bitonic.

¿Cómo se puede determinar si la secuencia dada es bitónica?

Tengo la siguiente opinión. Podemos caminar hasta n/2, donde n es la longitud de la matriz, y comprobar si

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

¿Es esto correcto?

Answer 1

Una secuencia bitónica:

/\ 
/\ 
    \/ 

No es una secuencia bitónica:

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

Obviamente, si la dirección cambia más de dos veces que no puede tener una secuencia bitónica.
Si la dirección cambia menos de dos veces, debemos tener una secuencia bitónica.

Si hay dos cambios en la dirección, PODEMOS tener una secuencia bitónica. Considera las dos imágenes ascii arriba. Claramente, una secuencia con dos cambios de dirección coincidirá con uno de los patrones (lo que permite una reflexión). Por lo tanto, establecemos la dirección inicial comparando el primero y el último elemento. Dado que estos pueden ser iguales, usamos el primer elemento que no es igual al último elemento.

Aquí es una implementación en 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; 
} 

Answer 2

• Traverse los delanteros de matriz, envolviéndose alrededor cuando llegue el final (código de abajo)
• contar el número total de puntos de inflexión a encontrar, si num_inflection_points==2 entonces su matriz es bitónica.
• El tiempo de ejecución de esto debería ser O(n).

-

Aquí está un ejemplo de trabajo en 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; 
} 

• Notas, dependiendo de su aplicación:

Nota 1: Esta es la idea básica para atravesar una matriz circularmente:

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];) 
} 

Nota 2: Puede simplificar el código para circular circularmente length + 1 elemnts, lo que le garantizará encontrar ambos puntos de inflexión.

Nota 3: O bien, podría simplificar el código si siempre busca el primer punto de inflexión que aumenta o disminuye (antes de buscar otros puntos de inflexión). De esta forma, su escaneo solo tiene que preocuparse de encontrar exactamente otro punto de inflexión con el reverso opuesto.

Nota 4: En cuanto a su ejemplo, no puede usar N/2, porque el punto de inflexión no ocurre necesariamente en el punto medio de la matriz.

Answer 3

Usted puede mirar para el pico, es decir, cuando a [i-1] < a [i] & & a [i]> a [i + 1], y luego a [i] es el pico local (teniendo cuidado de ajuste con el operador de módulo).

En una secuencia bitónica, solo puede haber uno de esos picos. Una vez que haya encontrado el pico, puede caminar cuesta abajo hacia la izquierda (envolviendo todo lo necesario, nuevamente usando el módulo) hasta que encuentre una cuesta arriba. Luego vuelves al pico, caminas cuesta abajo hacia la derecha, hasta que encuentres otro cuesta arriba. Ahora, si una secuencia es bitónica, habrás cubierto toda la secuencia yendo cuesta abajo en ambos lados.

por cierto, ¿he entendido mal la pregunta, o es su primer ejemplo no bitónico?

Answer 4

Tiene que haber exactamente dos (o, según cómo su definición tenga que ver con la degeneración, exactamente 0) transiciones entre subidas y bajadas. No olvides verificar la transición entre a [n] y a [0].

Answer 5

Aquí es una implementación eficiente y simple en Java. Atraviesa la matriz solo una vez para determinar si la matriz es bitónica o no. Utiliza una variable reversal que cuenta el número de inversiones de dirección de la monotonía en la matriz (incluida la envoltura circular).

La variable trend puede tener tres valores:

• 0, si los valores son los mismos;
• 1, si la matriz aumenta monótonamente;
• -1, si la matriz disminuye monótonamente.

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; 
}