Programa Python3 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.
 

# Python program to print all 
# triplets in given array 
# that form Arithmetic 
# Progression
  
# Function to print
# all triplets in
# given sorted array 
# that forms AP
def printAllAPTriplets(arr, n) :
  
    s = [];
    for i in range(0, n - 1) :
      
        for j in range(i + 1, n) :
          
            # Use hash to find if
            # there is a previous 
            # element with difference
            # equal to arr[j] - arr[i]
            diff = arr[j] - arr[i];
  
            if ((arr[i] - diff) in arr) :
                print ("{} {} {}" . 
                        format((arr[i] - diff),
                                arr[i], arr[j]), 
                                    end = "
");
          
    s.append(arr[i]);
      
# Driver code
arr = [2, 6, 9, 12, 17, 
       22, 31, 32, 35, 42];
n = len(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. 
 

# python 3 program to print all triplets in given 
# array that form Arithmetic Progression
   
# Function to print all triplets in
# given sorted array that forms AP
def printAllAPTriplets(arr, n):
   
    for i in range(1, n - 1): 
   
        # Search other two elements of
        # AP with arr[i] as middle.
        j = i - 1
        k = i + 1
        while(j >= 0 and k < n ): 
   
            # if a triplet is found
            if (arr[j] + arr[k] == 2 * arr[i]): 
                print(arr[j], "", arr[i], "", arr[k])
   
                # Since elements are distinct,
                # arr[k] and arr[j] cannot form
                # any more triplets with arr[i]
                k += 1
                j -= 1
               
   
            # If middle element is more move to 
            # higher side, else move lower side.
            elif (arr[j] + arr[k] < 2 * arr[i]): 
                k += 1     
            else:
                j -= 1     
           
# Driver code
arr = [ 2, 6, 9, 12, 17, 
        22, 31, 32, 35, 42 ]
n = len(arr) 
printAllAPTriplets(arr, n)
   
# This article is contributed 
# by Smitha Dinesh Semwal

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.