Programa Php para imprimir todos los tripletes en una array ordenada que forman AP

Dada una array ordenada de enteros positivos distintos, imprima todos los tripletes que forman
ejemplos AP (o progresión aritmética): 
 

Input : arr[] = { 2, 6, 9, 12, 17, 22, 31, 32, 35, 42 };
Output :
6 9 12
2 12 22
12 17 22
2 17 32
12 22 32
9 22 35
2 22 42
22 32 42

Input : arr[] = { 3, 5, 6, 7, 8, 10, 12};
Output :
3 5 7
5 6 7
6 7 8
6 8 10
8 10 12

Una solución simple es ejecutar tres bucles anidados para generar todos los tripletes y, para cada triplete, verificar si forma AP o no. La complejidad de tiempo de esta solución es O(n ³ )
Una mejor solución es usar hashing. Recorremos la array de izquierda a derecha. Consideramos cada elemento como medio y todos los elementos posteriores como elemento siguiente. Para buscar el elemento anterior, usamos una tabla hash.
 

<?php
// PHP program to pr$all 
// triplets in given array 
// that form Arithmetic 
// Progression
  
// Function to print
// all triplets in
// given sorted array 
// that forms AP
function printAllAPTriplets($arr, $n)
{
    $s = array();
    for ($i = 0; $i < $n - 1; $i++)
    {
        for ($j = $i + 1; 
             $j < $n; $j++)
        {
            // Use hash to find if
            // there is a previous 
            // element with difference
            // equal to arr[j] - arr[i]
            $diff = $arr[$j] - $arr[$i];
  
            if (in_array($arr[$i] -
                         $diff, $arr))
                echo(($arr[$i] - $diff) . 
                         " " . $arr[$i] . 
                         " " . $arr[$j] . "
");
        }
    array_push($s, $arr[$i]);
    }
}
  
// Driver code
$arr = array(2, 6, 9, 12, 17, 
            22, 31, 32, 35, 42);
$n = count($arr);
printAllAPTriplets($arr, $n);
  
// This code is contributed by 
// Manish Shaw(manishshaw1)
?>

Producción :  

6 9 12
2 12 22
12 17 22
2 17 32
12 22 32
9 22 35
2 22 42
22 32 42

Complejidad temporal: O(n ² ) 
Espacio auxiliar: O(n)
Una solución eficiente se basa en el hecho de que la array está ordenada. Usamos el mismo concepto que se discutió en la pregunta del triplete GP . La idea es comenzar desde el segundo elemento y fijar cada elemento como un elemento medio y buscar los otros dos elementos en un triplete (uno más pequeño y otro más grande). 
A continuación se muestra la implementación de la idea anterior. 
 

<?php
// PHP implementation to print
// all the triplets in given array
// that form Arithmetic Progression
  
// Function to print all triplets in
// given sorted array that forms AP
function findAllTriplets($arr, $n)
{
    for ($i = 1; $i < $n - 1; $i++) 
    {
  
        // Search other two elements 
        // of AP with arr[i] as middle.
        for ($j = $i - 1, $k = $i + 1; 
                   $j >= 0 && $k < $n😉
        {
              
            // if a triplet is found
            if ($arr[$j] + $arr[$k] == 2 * 
                           $arr[$i]) 
            {
                echo $arr[$j] ." " .
                     $arr[$i]. " " . 
                     $arr[$k] . "
";
  
                // Since elements are distinct,
                // arr[k] and arr[j] cannot form
                // any more triplets with arr[i]
                $k++;
                $j--;
            }
  
            // If middle element is more move to 
            // higher side, else move lower side.
            else if ($arr[$j] + $arr[$k] < 2 * 
                                     $arr[$i]) 
                $k++;         
            else
                $j--;         
        }
    }
}
  
// Driver code
$arr = array(2, 6, 9, 12, 17, 
             22, 31, 32, 35, 42);
               
$n = count($arr);
findAllTriplets($arr, $n);
  
// This code is contributed by Sam007
?>

Producción :  

6 9 12
2 12 22
12 17 22
2 17 32
12 22 32
9 22 35
2 22 42
22 32 42

Complejidad de tiempo: O(n ² ) 
Espacio auxiliar: O(1)
Consulte el artículo completo sobre Imprimir todos los tripletes en una array ordenada que forman AP para obtener más detalles.