algorithm - pitagorica - ¿Cómo encontrar trillizos pitagóricos en un arreglo más rápido que O(N ^ 2)?

que dijo pitagoras

Question

¿Alguien puede sugerir un algoritmo que encuentre todos los trillizos pitagóricos entre números en una matriz dada? Si es posible, por favor, sugiera un algoritmo más rápido que O (n ² ).

El triplete pitagórico es un conjunto {a, b, c} tal que a ² = b ² + c ² . Ejemplo: para la matriz [9, 2, 3, 4, 8, 5, 6, 10] la salida del algoritmo debe ser {3, 4, 5} y {6, 8, 10} .

Answer 1

A algunos de mis compañeros de trabajo se les preguntó sobre el mismo problema en un curso de Java que tomaron, la solución que encontramos fue O (N ^ 2). Eliminamos la mayor parte del espacio problemático que pudimos, pero no pudimos encontrar una manera de reducir la complejidad a N Log N o mejor.

    public static List<int[]> pythagoreanTripplets(int[] input) {
    List<int[]> answers = new ArrayList<int[]>();
    Map<Long, Integer> map = new HashMap<Long, Integer>();

    for (int i = 0; i < input.length; i++) {
        map.put((long)input[i] * (long)input[i], input[i]);
    }

    Long[] unique = (Long[]) map.keySet().toArray(new Long[0]);
    Arrays.sort(unique);
    long comps =0;
    for(int i =  1 ; i < unique.length;i++)
    {
        Long halfC = unique[i]/2;
        for(int j = i-1 ; j>= 0 ; j--)
        {

            if(unique[j] < halfC) break;
            if(map.containsKey(unique[i] - unique[j]))
            {
                answers.add(new int[]{map.get(unique[i] - unique[j]),map.get(unique[j]),map.get(unique[i])});
            }
        }
    }
    return answers;
}

Answer 2

Aquí está la implementación en Java:

/**
 * Step1: Square each of the elements in the array [O(n)]
 * Step2: Sort the array [O(n logn)]
 * Step3: For each element in the array, find all the pairs in the array whose sum is equal to that element [O(n2)]
 * 
 * Time Complexity: O(n2) 
 */
public static Set<Set<Integer>> findAllPythogoreanTriplets(int [] unsortedData) {

    // O(n) - Square all the elements in the array
    for (int i = 0; i < unsortedData.length; i++)
        unsortedData[i] *= unsortedData[i];

    // O(n logn) - Sort
    int [] sortedSquareData = QuickSort.sort(unsortedData);

    // O(n2)
    Set<Set<Integer>> triplets = new HashSet<Set<Integer>>();

    for (int i = 0; i < sortedSquareData.length; i++) {

        Set<Set<Integer>> pairs = findAllPairsThatSumToAConstant(sortedSquareData, sortedSquareData[i]);

        for (Set<Integer> pair : pairs) {
            Set<Integer> triplet = new HashSet<Integer>();
            for (Integer n : pair) {
                triplet.add((int)Math.sqrt(n));
            }
            triplet.add((int)Math.sqrt(sortedSquareData[i])); // adding the third element to the pair to make it a triplet
            triplets.add(triplet);
        }
    }

    return triplets;
}


public static Set<Set<Integer>> findAllPairsThatSumToAConstant(int [] sortedData, int constant) {

    // O(n)
    Set<Set<Integer>> pairs = new HashSet<Set<Integer>>();
    int p1 = 0; // pointing to the first element
    int p2 = sortedData.length - 1; // pointing to the last element
    while (p1 < p2) {
        int pointersSum = sortedData[p1] + sortedData[p2];
        if (pointersSum > constant)
            p2--;
        else if (pointersSum < constant)
            p1++;
        else {
            Set<Integer> set = new HashSet<Integer>();
            set.add(sortedData[p1]);
            set.add(sortedData[p2]);
            pairs.add(set);
            p1++;
            p2--;
        }
    }
    return pairs;
}

Answer 3

Aquí hay una solución que puede escalar mejor para grandes listas de números pequeños. Al menos es diferente; v).

De acuerdo con Wikipedia ,

a = m^2 - n^2, b = 2mn, c = m^2 + n^2 

b ve bien, eh?

• Ordene la matriz en tiempo O (N log N).
• Para cada elemento b , encuentre la factorización prima. El uso ingenuo de una tabla de números primos hasta la raíz cuadrada del mayor valor de entrada M tomaría O (sqrt M / log M) tiempo y espacio * por elemento.
• Para cada par (m,n), m > n, b = 2mn (saltar impar b ), busque m^2-n^2 y m^2+n^2 en la matriz ordenada. O (registro N) por par, O (2 ^ ((M))) = O (registro M) ** pares por elemento, O (N (registro N) (registro M)) en total.

Análisis final: O (N ((sqrt M / log M) + (log N * log M)), N = tamaño de matriz, M = magnitud de los valores.

(* Para aceptar una entrada de 64 bits, hay aproximadamente 203M primos de 32 bits, pero podemos usar una tabla de diferencias en un byte por primo, ya que todas las diferencias son iguales, y quizás también generen grandes primos en secuencia a pedido. Para aceptar una entrada de 32 bits, se necesita una tabla de números primos de 16 bits, que es lo suficientemente pequeña como para caber en el caché L1. El tiempo aquí es una sobrestimación, suponiendo que todos los factores primos son solo menores que la raíz cuadrada.

(** Límite real inferior debido a factores primos duplicados).

Answer 4

Entiendo esta pregunta como

Dada una matriz, encuentre todos esos tripletes i , j y k , de modo que a [i] ² = a [j] ² + a [k] ²

La idea clave de la solución es:

• Cuadrar cada elemento . (Esto toma O (n) tiempo). Esto reducirá la tarea original de "encontrar tres números en una matriz, uno de los cuales es la suma de otros dos".

Ahora que ya sabe cómo resolver dicha tarea en menos de O (n ² ), use dicho algoritmo. De mi mente solo sale la siguiente solución O (n ² ):

1. Ordena la matriz en orden ascendente. Esto toma O (n log n).

2. Ahora considera cada elemento a [i]. Si a [i] = a [j] + a [k], entonces, dado que los números son positivos y la matriz ahora está ordenada, k <i y j <i.

   Para encontrar dichos índices, ejecute un bucle que aumente j de 1 a i , y disminuya k de i a 0 al mismo tiempo, hasta que se encuentren. Aumente j si a[j]+a[k] < a[i] , y disminuya k si la suma es mayor que a[i] . Si la suma es igual, esa es una de las respuestas, imprímala y desplace ambos índices.

   Esto toma O (i) operaciones.

3. Repita el paso 2 para cada índice i . De esta manera, necesitará totalmente O (n ² ) operaciones, que serán la estimación final.

Answer 5

Este es el que yo había implementado ...

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;


/**
 * 
 * @author Pranali Choudhari ([email protected])
 */
public class PythagoreanTriple {

/
    //I hope this is optimized



    public static void main(String[] args) {

        Map<Long,Set<Long>> triples = new HashMap<Long,Set<Long>>();
        List<Long> l1 = new ArrayList<Long>();
        addValuesToArrayList(l1);
        long n =0;        
        for(long i : l1){
            //if its side a.
             n = (i-1L)/2L;
             if (n!=0 && n > 0){
                  putInMap(triples,n,i);
                  n=0;
             }
             //if its side b 

             n = ((-1 + Math.round(Math.sqrt(2*i+1)))/2);
             if (n != 0 && n > 0){
                 putInMap(triples,n,i);
                  n=0;
             }
             n=  ((-1 - Math.round(Math.sqrt(2*i+1)))/2);
             if (n != 0 && n > 0){
                 putInMap(triples,n,i);
                  n=0;
             }
             //if its side c

             n = ((-1 + Math.round(Math.sqrt(2*i-1)))/2);
             if (n != 0 && n > 0){
                 putInMap(triples,n,i);
                  n=0;
             }
             n=  ((-1 - Math.round(Math.sqrt(2*i-1)))/2);
             if (n != 0 && n > 0){
                 putInMap(triples,n,i);
                  n=0;
             }


        }
        for(Map.Entry<Long, Set<Long>> e : triples.entrySet()){
            if(e.getValue().size() == 3){
                System.out.println("Tripples" + e.getValue());
            }
            //need to handle scenario when size() > 3 
            //even those are tripples but we need to filter the wrong ones
        }


    }

    private static void putInMap( Map<Long,Set<Long>> triples, long n,  Long i) {
        Set<Long> set = triples.get(n);
        if(set == null){
            set = new HashSet<Long>();
            triples.put(n, set);
        }
        set.add(i);
    }

    //add values here 
    private static void addValuesToArrayList(List<Long> l1) {
        l1.add(1L);
        l1.add(2L);
        l1.add(3L);
        l1.add(4L);
        l1.add(5L);
        l1.add(12L);
        l1.add(13L);

    }
}

Answer 6

Nadie sabe cómo hacerlo significativamente mejor que el cuadrático para el problema 3SUM estrechamente relacionado ( http://en.wikipedia.org/wiki/3SUM ). Consideraría improbable la posibilidad de una solución rápida a su problema.

El problema de 3SUM es encontrar a + b + c = 0. Sea PYTHTRIP el problema de encontrar a ^ 2 + b ^ 2 = c ^ 2 cuando las entradas son números algebraicos reales. Aquí está la reducción del tiempo O (n log n) de 3SUM a PYTHTRIP. Como señala ShreevatsaR, esto no excluye la posibilidad de un truco de la teoría de números (o una solución a 3SUM!).

Primero reducimos 3SUM a un problema al que llamaré 3SUM-ALT. En 3SUM-ALT, queremos encontrar a + b = c donde todas las entradas de la matriz son no negativas. La reducción de acabado de 3SUM-ALT a PYTHTRIP solo está tomando raíces cuadradas.

Para resolver 3SUM utilizando 3SUM-ALT, primero elimine la posibilidad de triples cuando uno de a, b, c sea cero (O (n log n)). Ahora, cualquier triple satisfactorio tiene dos números positivos y uno negativo, o dos negativos y uno positivo. Sea w un número mayor que tres veces el valor absoluto de cualquier número de entrada. Resuelva dos instancias de 3SUM-ALT: una donde todos los x negativos se asignan a w - x y todos los x positivos se asignan a 2w + x; donde todos los x negativos se asignan a 2w - x y todos los x positivos se asignan a w + x. El resto de la prueba es sencillo.

Answer 7

No estoy seguro de si esto es mejor, pero puede calcularlos en un tiempo proporcional al valor máximo en la lista simplemente calculando todos los triples posibles menores o iguales a ellos. El siguiente código Perl hace. La complejidad del tiempo del algoritmo es proporcional al valor máximo, ya que la suma de los cuadrados inversos 1 + 1/2 ^ 2 + 1/3 ^ 3 .... es igual a Pi ^ 2/6, una constante.

Acabo de utilizar la fórmula de la página de Wikipedia para generar tripletas únicas.

my $list = [9, 2, 3, 4, 8, 5, 6, 10];
pythagoreanTriplets ($list);

sub pythagoreanTriplets
{
  my $list = $_[0];
  my %hash;
  my $max = 0;
  foreach my $value (@$list)
  {
    $hash{$value} = 1;
    $max = $value if ($value > $max);
  }
  my $sqrtMax = 1 + int sqrt $max;

  for (my $n = 1; $n <= $sqrtMax; $n++)
  {
    my $n2 = $n * $n;
    for (my $m = $n + 1; $m <= $sqrtMax; $m++)
    {
      my $m2 = $m * $m;
      my $maxK = 1 + int ($max / ($m2 + $n2));
      for (my $k = 1; $k <= $maxK; $k++)
      {
        my $a = $k * ($m2 - $n2);
        my $b = $k * (2 * $m * $n);
        my $c = $k * ($m2 + $n2);
        print "$a $b $c/n" if (exists ($hash{$a}) && exists ($hash{$b}) && exists ($hash{$c}));
      }
    }
  }
}

Answer 8

Se puede hacer en O (n) tiempo. Primero hash los elementos en el mapa para verificar la existencia. después de eso aplique el siguiente algoritmo

Escanee la matriz y si el elemento es un número par, (n, n ^ 2/2 +1, n ^ 2/2 -1) se encuentra el triplete. simplemente compruebe si existe existencia mediante la función de búsqueda de mapa hash. si todos los elementos en el triplete existen, imprima el triplete.

Answer 9

Si (a, b, c) es un triple pitagórico, entonces también lo es (ka, kb, kc) para cualquier entero positivo.

así que simplemente encuentre un valor para a, byc y luego podrá calcular tantos nuevos como desee.

Pseudo código:

a = 3
b = 4
c = 5
for k in 1..N:
  P[k] = (ka, kb, kc)

Avísame si esto no es exactamente lo que estás buscando.

Answer 10

Solución en O (N).

1. averiguar el elemento mínimo en la matriz. min O (n).
2. descubre el elemento máximo en el conjunto. max O (n).
3. Haz una lista de elementos para que el elemento pueda ser buscado en O (1).
4. m ^ 2-1 = min .... ponga min desde el paso 1. averigüe m en esta ecuación.O (1)
5. 2m = min .... ponga min desde el paso 1. averigüe m en esta ecuación.O (1)

6. m ^ 2 + 1 = máx .... ponga máx en el paso 2. averigüe m en esta ecuación.O (1)

7. Elija piso de min de (pasos 4,5,6) digamos minValue.O (1)

8. elija un máximo de (pasos 4, 5, 6) digamos maxValue.O (1)

9. bucle de j = minValue a maxValue. maxvalue-minvalue será menor que la raíz de N. 9.a calcular tres números j ^ 2-1,2j, j ^ 2 + 1. 9.b busca estos números en hashtable. si se encuentra, devuelve el éxito.

10. falla de retorno

Answer 11

Tengo una solución más,

//sort the array in ascending order 
//find the square of each element in the array

//let ''a'' be the array containing square of each element in ascending order 

for(i->0 to (a.length-1))
  for (j->i+1 to  (a.length-1))
    //search the a[i]+a[j] ahead in the array from j+1 to the end of array
      //if found get the triplet according to sqrt(a[i]),sqrt(a[j]) & sqrt(a[i]+a[j])
  endfor
endfor

Answer 12

si el problema es el único "Para una matriz de enteros, encuentre todos los triples tal que a ^ 2 + b ^ 2 = c ^ 2

Ordenar la matriz en orden ascendente

Establecer tres punteros p1, p2, p3 en las entradas 0,1,2 establecer pEnd para pasar la última entrada en la matriz

while (p2 <pend-2) {

sum = (*p1 * *p1 + *p2 * *p2)


while ((*p3 * *p3) < sum && p3 < pEnd -1)
   p3++;

if ( *p3 == sum) 
   output_triple(*p1, *p2, *p3);

p1++;
p2++;

}

está moviendo 3 punteros hacia arriba en la matriz, por lo que O (sort (n) + n) no es n2 porque la siguiente pasada comienza en el siguiente número más grande y no se reinicia. Si el último número era demasiado pequeño para el triple, es demasiado pequeño cuando pasas a los siguientes a y b más grandes.

Answer 13

Encontrar trillizos pitagóricos en O (n)

Algoritmo:

1. Para cada elemento en la matriz, verifique que sea primo o no
2. si es primo, calcule otros dos números como ((n ^ 2) +1) / 2 y ((n ^ 2) -1) / 2 y verifique si estos dos números calculados están en la matriz
3. si no es primo, calcule otros dos números como se menciona en caso contrario en el código que figura a continuación

4. Repita hasta que se alcance el final de la matriz

    int arr[]={1,2,3,4,5,6,7,8,9,10,12,13,11,60,61};
    int prim[]={3,5,7,11};//store all the prime numbers
    int r,l;
    List<Integer> prime=new ArrayList<Integer>();//storing in list,so that it is easy to search
    for(int i=0;i<4;i++){
     prime.add(prim[i]);
    }
    List<Integer> n=new ArrayList<Integer>();
    for(int i=0;i<arr.length;i++)
    {
           n.add(arr[i]);
    }
    double v1,v2,v3;
    int dummy[]=new int[arr.length];
    for(int i=0;i<arr.length;i++)
       dummy[i]=arr[i];
   
    Integer x=0,y=0,z=0;
    List<Integer> temp=new ArrayList<Integer>();
    for(int i=0;i<arr.length;i++)
    {
        temp.add(arr[i]);
    }
   
    for(int j:n){
       if(prime.contains(j)){//if it is prime
           double a,b; 
           v1=(double)j;
           v2=Math.ceil(((j*j)+1)/2);
           v3=Math.ceil(((j*j)-1)/2);
           if(n.contains((int)v2) && n.contains((int)v3)){
             System.out.println((int)v1+" "+(int)v2+" "+(int)v3);
           }
       }
       else//if it is not prime
       {
            if(j%3==0){
               x=j;
               y=4*(j/3);
               z=5*(j/3);
               if(temp.contains(y) && temp.contains(z)){
                       System.out.println(x+" "+y+" "+z);
                       //replacing those three elements with 0
                       dummy[temp.indexOf(x)-1]=0;
                       dummy[temp.indexOf(y)-1]=0;
                       dummy[temp.indexOf(z)-1]=0;
               }
            }   
       }//else end
   }//for end

Complejidad: O (n)

Answer 14

    import java.io.*;
import java.lang.*;
import java.util.*;

class PythagoreanTriplets
{
 public static void main(String args[])throws IOException
 {
  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

  int n = Integer.parseInt(br.readLine());
  int arr[] = new int[n];
  int i,j,k,sum;
  System.out.println("Enter the numbers ");
  for(i=0;i<n;i++)
   {
    arr[i]=Integer.parseInt(br.readLine());
    arr[i]=arr[i]*arr[i];
   }
Arrays.sort(arr);
  for(i=n-1;i>=0;i--)
   {
     for(j=0,k=i-1;j<k;)
        {  
          sum=arr[j]+arr[k];
          if(sum==arr[i]){System.out.println((int)Math.sqrt(arr[i]) +","+(int)Math.sqrt(arr[j])+","+(int)Math.sqrt(arr[k]));break;}
          else if(sum>arr[i])k--;
          else j++;

        }
   }

}
}

Answer 15

public class FindPythagorusCombination {

    public static void main(String[] args) {
        int[] no={1, 5, 3, 4, 8, 10, 6 };
        int[] sortedno= sorno(no);
        findPythaComb(sortedno);
    }

    private static void findPythaComb(int[] sortedno) {
        for(int i=0; i<sortedno.length;i++){

            int lSum=0, rSum=0;
            lSum= sortedno[i]*sortedno[i];
            for(int j=i+1; j<sortedno.length; j++){
                for(int k=j+1; k<sortedno.length;k++){
                    rSum= (sortedno[j]*sortedno[j])+(sortedno[k]*sortedno[k]);
                    if(lSum==rSum){
                        System.out.println("Pythagorus combination found: " +sortedno[i] +" " +sortedno[j]+" "+sortedno[k]);
                    }else
                        rSum=0;
                }

            }
        }
    }

    private static int[] sorno(int[] no) {

        for(int i=0; i<no.length;i++){

            for(int j=i+1; j<no.length;j++){
                if(no[i]<no[j]){
                    int temp= no[i];
                    no[i]= no[j];
                    no[j]=temp;
                }
            }

        }

        return no;

    }



}