Programa Php para contar inversiones de tamaño tres en una array dada

Dada una array arr[] de tamaño n. Tres elementos arr[i], arr[j] y arr[k] forman una inversión de tamaño 3 si a[i] > a[j] >a[k] e i < j < k. Encuentre el número total de inversiones de tamaño 3.
Ejemplo: 
 

Input:  {8, 4, 2, 1}
Output: 4
The four inversions are (8,4,2), (8,4,1), (4,2,1) and (8,2,1).

Input:  {9, 6, 4, 5, 8}
Output:  2
The two inversions are {9, 6, 4} and {9, 6, 5}

Ya hemos discutido el conteo de inversión del tamaño dos por ordenación por fusión , Self Balancing BST y BIT .
Enfoque simple: haga un bucle para todos los valores posibles de i, j y k y compruebe la condición a[i] > a[j] > a[k] e i < j < k.
 

<?php
// A O(n^2) PHP program to 
// count inversions of size 3
  
// Returns count of 
// inversions of size 3
function getInvCount($arr, $n)
{
      
    // Initialize result
    $invcount = 0; 
  
    for ($i = 1; $i < $n - 1; $i++)
    {
          
        // Count all smaller elements 
        // on right of arr[i]
        $small = 0;
        for($j = $i + 1; $j < $n; $j++)
            if ($arr[$i] > $arr[$j])
                $small++;
  
        // Count all greater elements 
        // on left of arr[i]
        $great = 0;
        for($j = $i - 1; $j >= 0; $j--)
            if ($arr[$i] < $arr[$j])
                $great++;
  
        // Update inversion count by 
        // adding all inversions
        // that have arr[i] as 
        // middle of three elements
        $invcount += $great * $small;
    }
  
    return $invcount;
}
  
    // Driver Code
    $arr = array(8, 4, 2, 1);
    $n = sizeof($arr);
    echo "Inversion Count : "
        , getInvCount($arr, $n);
  
// This code is contributed m_kit
?>

Producción:

Inversion Count : 4 

La complejidad temporal de este enfoque es: O (n ^ 3)
Mejor enfoque: 
podemos reducir la complejidad si consideramos cada elemento arr [i] como elemento medio de inversión, encuentre todos los números mayores que a [i] cuyo índice es menor que i, encuentra todos los números que son menores que a[i] y el índice es mayor que i. Multiplicamos el número de elementos mayores que a[i] por el número de elementos menores que a[i] y lo sumamos al resultado. 
A continuación se muestra la implementación de la idea.
 

<?php
// A O(n^2) PHP program to count
// inversions of size 3
  
// Returns count of 
// inversions of size 3
function getInvCount($arr, $n)
{
    // Initialize result
    $invcount = 0; 
  
    for ($i = 1; $i < $n - 1; $i++)
    {
        // Count all smaller elements
        // on right of arr[i]
        $small = 0;
        for ($j = $i + 1; $j < $n; $j++)
            if ($arr[$i] > $arr[$j])
                $small++;
  
        // Count all greater elements
        // on left of arr[i]
        $great = 0;
        for ($j = $i - 1; $j >= 0; $j--)
            if ($arr[$i] < $arr[$j])
                $great++;
  
        // Update inversion count by 
        // adding all inversions that
        // have arr[i] as middle of 
        // three elements
        $invcount += $great * $small;
    }
  
    return $invcount;
}
  
// Driver Code
$arr = array (8, 4, 2, 1);
$n = sizeof($arr);
echo "Inversion Count : " , 
      getInvCount($arr, $n);
      
// This code is contributed by m_kit
?>

Producción :

Inversion Count : 4 

Complejidad temporal de este enfoque: O (n ^ 2)
Enfoque de árbol indexado binario: 
Al igual que las inversiones de tamaño 2, podemos usar el árbol indexado binario para encontrar inversiones de tamaño 3. Se recomienda encarecidamente consultar primero el artículo a continuación.
Contar inversiones de tamaño dos Usando BIT
La idea es similar al método anterior. Contamos el número de elementos mayores y elementos menores para todos los elementos y luego multiplicamos mayor[] por menor[] y lo sumamos al resultado. 
Solución :

1. Para averiguar el número de elementos más pequeños para un índice iteramos de n-1 a 0. Para cada elemento a[i] calculamos la función getSum() para (a[i]-1) que da el número de elementos hasta a[i]-1.
2. Para averiguar el número de elementos mayores para un índice, iteramos de 0 a n-1. Para cada elemento a[i] calculamos la suma de números hasta a[i] (suma menor o igual a a[i]) por getSum() y lo restamos de i (ya que i es el número total de elementos hasta ese punto ) para que podamos obtener un número de elementos mayor que a[i].

¡ Consulte el artículo completo sobre inversiones de conteo de tamaño tres en una array dada para obtener más detalles!