Matematyczny sposób porównywania pary 3 zmiennych

Przydzielono mi zadanie porównania pary 3 pozytywnych zmiennych podwójnych, ignorując ich kolejność w Javie. Zrobiłem następujące:

if ((a1 == a2 && b1 == b2 && c1 == c2) ||
    (a1 == a2 && b1 == c2 && c1 == b2) ||
    (a1 == b2 && b1 == a2 && c1 == c2) ||
    (a1 == b2 && b1 == c2 && c1 == a2) ||
    (a1 == c2 && b1 == a2 && c1 == b2) ||
    (a1 == c2 && b1 == b2 && c1 == a2))
    // if true

Słyszałem od nauczyciela, że ​​istnieje matematyczny sposób porównywania tej pary 3 liczb.

Do tej pory próbowałem porównać ich dodawanie, odejmowanie, sumę ich mocy o 2, ale zawsze znalazłem przypadek, w którym para była inna, a stwierdzenie było prawdziwe.

Jakieś pomysły?

EDYTOWAĆ:

Wysłałem już zadanie, a nauczyciel powiedział, że moja odpowiedź jest prawdziwa. Pytam z ciekawości.

TL; DR

Porównaj sumę każdej trójki, iloczyn każdej trójki i sumę iloczynu wszystkich możliwych kombinacji każdej trójki.

Nitty Gritty

Zgodnie z podstawowym twierdzeniem algebry dla wielomianu stopnia N musimy mieć N pierwiastków.

Korzystając z tego faktu, pozwalamy naszym zerom być a1, a2, and a3. Teraz znajdujemy współczynniki tego wielomianu.

(x - a1) * (x - a2) * (x - a3)
(x^2 - (a1 + a2) * x + a1a2) * (x - a3) 
x^3 - (a1 + a2) * x^2 + (a1a2) * x - a3 * x^2 + (a1a3 + a2a3) * x - a1a2a3

x^3 + (-1 * (a1 + a2 + a3)) * x^2 + (a1a2 + a1a3 + a2a3) * x + (-1 * a1a2a3)

Jeśli dwa wielomiany są równoważne, muszą mieć te same pierwiastki (ponownie według umowy o wolnym handlu). Dlatego wszystko, co musimy zrobić, to porównać współczynniki wygenerowanych wielomianów.

Więc jeśli,

(-1 * (a1 + a2 + a3) == (-1 * (b1 + b2 + b3))
      ---equivalently---
a1 + a2 + a3 == b1 + b2 + b3

I

(a1a2 + a1a3 + a2a3) == (b1b2 + b1b3 + b2b3)

I

-1 * a1a2a3 == -1 * b1b2b3
      ---equivalently---
a1a2a3 == b1b2b3

Następnie możemy zawrzeć trojaczki a1, a2, a3i b1, b2, b3są one równoważne.

Czy warto?

Z praktycznego punktu widzenia zobaczmy, czy jest to rzeczywiście bardziej wydajne niż sprawdzanie siły, jak pokazano w PO.

Pierwsza kontrola: Sumuj i porównaj. Wymaga to 4 dodatków i 1 sprawdzenia równości.

Sprawdź łącznie = 5; Całkowity bieg = 5

Druga kontrola: produkt, suma i porównanie. Wymaga to 6 całkowitych pomnożeń, 4 całkowitych dodatków i 1 sprawdzenia równości.

Sprawdź łącznie = 11; Całkowity bieg = 16

Trzecia kontrola: produkt i porównanie. Wymaga to 4 całkowitych mnożenia i 1 sprawdzenia równości.

Sprawdź łącznie = 5; Całkowity bieg = 21

Dodając dwie logiczne operacje AND, całkowita liczba operacji binarnych dla „współczynników wygenerowanego podejścia wielomianowego” wymaga tylko:

23 operacje binarne

Kontrola brutalnej siły wymaga 18 całkowitych kontroli równości, 12 logicznych porównań ORAZ 5 logicznych porównań ORAZ dla:

35 operacji binarnych

Tak więc, ściśle mówiąc , odpowiedź brzmi tak, „współczynniki wygenerowanego podejścia wielomianowego” są rzeczywiście bardziej wydajne. Jednak, jak @WJS zaznacza, podejście brute force ma o wiele więcej możliwości zwarcia , a tym samym wykonać jako / bardziej efektywnie niż podejścia matematycznego.

Dla pełnej dokładności

Nie możemy pominąć sprawdzania sumy produktów wszystkich możliwych kombinacji każdej trojaczki. Jeśli pominiemy to, istnieje niezliczona liczba przykładów, w których to się nie udaje. Rozważ (23, 32, 45)i (24, 30, 46)^* :

23 + 32 + 45 = 100
24 + 30 + 46 = 100

23 * 32 * 45 = 33120
24 * 30 * 46 = 33120

Nie są równoważne, ale dają tę samą sumę i produkt. Nie dają jednak takiej samej sumy produktów wszystkich możliwych kombinacji:

23 * 32 + 23 * 45 + 32 * 45 = 3211
24 * 30 + 24 * 46 + 30 * 46 = 3204

^* Jeśli ktoś jest ciekawy, jak uzyskać przykład podobny do powyższego, najpierw wygeneruj wszystkie partycje całkowite liczby całkowitej M o długości 3, weź ich produkt, znajdź duplikaty i wybierz parę.

Jeśli możesz sortować (a1 <= b1 <= c1 i a2 <= b2 <= c2), spróbuj porównać 2 ^ a1 * 3 ^ b1 * 5 ^ c1 z 2 ^ a2 * 3 ^ b2 * 5 ^ c2 (używając liczb pierwszych 2, 3, 5 jako podstawy)