Strona główna Polish Python Coders Group
   Strona główna   Pomoc Zaloguj się Rejestracja  
Witamy, Gość. Zaloguj się lub zarejestruj.
Czy dotarł do Ciebie email aktywacyjny?

Zaloguj się podając nazwę użytkownika, hasło i długość sesji

Aktualności: PyData Warsaw :: https://pydata.org/warsaw2018/
Szukaj Szukaj
Strony: [1]   Do dołu
Drukuj
Wątek: Wyszukiwanie trójek arytmetycznych.  (Przeczytany 2979 razy)
« : 12:42 13/02/18 »
SomeOne3103 Offline
Hello World!

Zobacz profil
*

Reputacja: 0
Wiadomości: 2


Witam, jestem początkującym programistą, programuję dopiero do kilku miesięcy. W jednym z zadań natrafiłem na problem.

Treść zadania:
Cytuj
Rozważmy posortowaną rosnąco listę L co najmniej trzyelementową liczb całkowitych. W tej liście znajdź wszystkie trzyelementowe podlisty, które tworzą ciąg arytmetyczny. Oznacza to, że różnica pomiędzy dwoma pierwszymi elementami danej podlisty musi być taka sama jak pomiedzy dwoma ostatnimi.

Przykładowo

*w liście [1, 2, 3, 4, 8, 12] będziemy mieli trzy takie tryplety: [1, 2, 3], [2, 3, 4] oraz [4, 8, 12]
*w liście [1, 2, 3, 4, 6, 7, 9] będziemy mieli ich pięć: [1, 2, 3], [1, 4, 7], [2, 3, 4], [2, 4, 6] oraz [3, 6, 9]
Waszym zadaniem będzie napisanie programu znajdz_trojki_arytmetyczne(L), który wyszukuje wszytskie trzyelementowe ciągi arytmetyczne z posortowanej listy L.

Mój problem polega na tym, że nie mam pomysłu jak można znaleźć te trójki, które nie występują obok siebie w liście.

Oto mój kod:
Kod
def znajdz_trojki_arytmetyczne(L):
 
   a=[]
   i=0
   while (i<(len(L)-2)):
       if (L[i+1]-L[i]==L[i+2]-L[i+1]):
           a.append([L[i],L[i+1],L[i+2]])
       i=i+1
   return a
Byłbym wdzięczny za każdą pomoc.
Pozdrawiam.
Zapisane
« Odpowiedz #1 : 15:13 13/02/18 »
hydeparkk Offline
Hello World!

Zobacz profil
*

Reputacja: 13
Płeć: Mężczyzna
Wiadomości: 46


W pythonie jest moduł itertools, w nim znajdziesz taką metodę jak combinations, który wygeneruję Ci listę wszystkich kombinacji (jak sama nazwa wskazuje) bez powtórzeń, twoim zadaniem pozostanie sprawdzenie czy taka trójka jest ciągiem arytmetycznym.
Zapisane
« Odpowiedz #2 : 19:34 13/02/18 »
sig Offline
Professional Python User

Zobacz profil
***

Reputacja: 84
Wiadomości: 387


Lista wejściowa jest posortowana, a zwykle robi się takowe w celu wyszukiwania binarnego, które akurat tutaj będzie przydatne. Ja zrobił bym to tak:
pierwsza pętla - po kolei przez wszystkie elementy listy - nazwijmy go tab
druga pętla - od następnego po aktualnym z pierwszego do końca nazwijmy go tab[j]
i w końcu szukanie binarne czy istnieje wartość równa tab[j] + (tab[j] - tab). Jeśli tak, masz poszukiwaną trójkę. Będzie dużo szybsze od itertools-a
Zapisane
« Odpowiedz #3 : 23:12 14/02/18 »
DJangoL Offline
Professional Python User

Zobacz profil
***

Reputacja: 27
Wiadomości: 377


Napisałem coś takiego (z pewnością to nienajszybszy kod i być może trzeba w nim coś poprawić, ale powinien być OK):

Kod
tab0 = [2, 6, 7, 8, 10, 12, 14, 15, 18, 33]
tab1 = [2, 6, 7, 8, 10, 11, 15, 16, 22, 24, 26, 27, 28, 30, 32, 33]
 
def znajdz_trojki(tab):
   trojki = []
   size = len(tab)
   for i in range(size - 2):
       for j in range(i + 1, size - 1):
           if j>i:  # [b]edit[/b]: ten warunek jest już niepotrzebny
               r = tab[j] - tab[i]
               n = tab[j] + r
               if n in tab:
                   idx = tab.index(n, j + 1, size )
                   if idx > j:
                        trojki.append( (tab[i], tab[j], tab[idx]) )
   return trojki
 
 
res = znajdz_trojki(tab0)
for trojka in res:
   print( trojka )
print("-----------")
res = znajdz_trojki(tab1)
for trojka in res:
   print( trojka )

EDIT: Oczywiście tablica musi być już posortowana rosnąco, inaczej kiszka.
Zapisane
« Odpowiedz #4 : 02:06 15/02/18 »
Guaz Offline
Professional Python User

Zobacz profil
***

Reputacja: 41
Płeć: Mężczyzna
Wiadomości: 310


Przykład z użyciem itertools'a i wyżej wspomnianego modułu combinations:
Kod
from itertools import combinations
 
 
def main():
   tab0 = [2, 6, 7, 8, 10, 12, 14, 15, 18, 33]
   tab1 = [2, 6, 7, 8, 10, 11, 15, 16, 22, 24, 26, 27, 28, 30, 32, 33]
   wyn = trojki_arytmetyczne(tab0)
   print("\n".join(str(i) for i in wyn))
   print("~~"*10)
   wyn = trojki_arytmetyczne(tab1)
   print("\n".join(str(i) for i in wyn))
 
 
def trojki_arytmetyczne(tablica):
   #~ Zmienna magazynująca znalezione trójki
   wszystkie_trojki = []
 
   #~ Kombinacje cyfr:
   for wybrane in combinations(tablica, 3):
       #~ wybrane = list(wybrane) # Jeśli zakładamy że lista nie będzie uporządkowana rosnąco.
       #~ wybrane.sort()
       if wybrane[1] - wybrane[0] == wybrane[2] - wybrane[1]:
           wszystkie_trojki.append(wybrane)
   #~ Wynik funkcji
   return wszystkie_trojki
 
 
if __name__ == "__main__":
   main()
 
Pozwoliłem sobie użyć list wśród których szukano, aby można było łatwo przyrównać poprawność Uśmiech. Sposób sig'a już pokazał przedmówca, więc mój post jest tylko w ramach ciekawostki, skoro jest wolniejszy.
Zapisane

Python 3.5.2 / Mint
« Odpowiedz #5 : 03:06 15/02/18 »
DJangoL Offline
Professional Python User

Zobacz profil
***

Reputacja: 27
Wiadomości: 377


Wykonałem pomiar czasu wykonania kodu dla takiej tablicy:

Kod
tab2 = [2, 6, 7, 8, 10, 11, 15, 16, 18, 20, 22, 24, 26, 27, 28, 30, 32, 33, 40, 44, 48, 50, 52, 56, 58, 59, 62, 64, 67, 68, 69, 72, 75, 80, 81, 82, 84, 85, 88, 92, 100]

Kod na itertools rzeczywiście jest wolniejszy, różnica jest spora (razy ~3):

Czas wykonania: 0.015625715255737305 - pierwszy przykład
190 "trójek"
~~~~~~~~~~~~~~~~~~~~
Czas wykonania: 0.04687643051147461 - drugi przykład użytkownika Guaz na itertools
190 "trójek"
Zapisane
« Odpowiedz #6 : 03:42 15/02/18 »
Guaz Offline
Professional Python User

Zobacz profil
***

Reputacja: 41
Płeć: Mężczyzna
Wiadomości: 310


Yup, to jest związane ze złożonością więc nawet nie trzeba testować bo widać gołym okiem Uśmiech. Ale też sprawdzałem jak duża jest ta przebitka Chichot
Przy poszukiwaniu trójek, mamy znacząco więcej kombinacji niż przy szukaniu pary i dopasowywaniu do listy. Da się przedstawić to za pomocą równania dla n elementów. (aktualnie jest za późno abym sobie to przypomniał, ale jest to jak najbardziej do wyliczenia jak wykładniczo się zwiększy dla większej ilości kombinacji)
Przykład combinations zoptymalizowanego do tego przykładu:
Kod
def trojki_arytmetyczne(tablica):
   #~ Zmienna magazynuj&#261;ca znalezione tr&#243;jki
   wszystkie_trojki = []
 
   #~ Kombinacje cyfr:
   for wybrane in combinations(tablica, 2):
       #~ wybrane = list(wybrane) # Je&#347;li zak&#322;adamy &#380;e lista nie b&#281;dzie uporz&#261;dkowana rosn&#261;co.
       #~ wybrane.sort()
       domniemana = wybrane[1] + (wybrane[1] - wybrane[0])
       if domniemana in tablica:
           wszystkie_trojki.append((wybrane[0],wybrane[1],domniemana))
   #~ Wynik funkcji
   return wszystkie_trojki
Mniej jasno pokazujący możliwości, ale odpowiedniejszy w tym przypadku. Jedyne co robi, to zastępuje dwie pętle (tam zastępował w sumie 3, więc co się dziwić że był wolniejszy Chichot). Dopiero teraz w sumie wpadłem na to pisząc o złożoności. Co więcej, okazuje się że wcale nie koniecznie combinations jest wolniejszy. W zależności od obciążenia i innych pierdół, wyniki się rozmijają raz jeden, raz drugi pod względem szybkości na większych listach Uśmiech

To nie combinations był zły, tylko mój pomysł Chichot


@Edit: Ah, jbc. przyrównywałem do tego kodu, nie do twojego.
Kod
def trojki_wg_siga(tablica):
   wszystkie_trojki = []
 
   for i in range(len(tablica)-1):
       for j in range(i+1, len(tablica)):
           domniemany = tablica[j] + (tablica[j] - tablica[i])
           if domniemany in tablica:
               wszystkie_trojki.append((tablica[i], tablica[j], domniemany))
   return wszystkie_trojki
Ale jest to dokładnie to samo działanie, obydwa pokrywają się z twoim Uśmiech.
Zapisane

Python 3.5.2 / Mint
« Odpowiedz #7 : 08:08 15/02/18 »
sig Offline
Professional Python User

Zobacz profil
***

Reputacja: 84
Wiadomości: 387


To może jeszcze z szukaniem binarnym, powinien być jeszcze szybszy ale nie wiem czy przy takiej tablicy będzie widać różnice

Kod
tab = [2, 6, 7, 8, 10, 11, 15, 16, 18, 20, 22, 24, 26, 27, 28, 30, 32, 33, 40,
   44, 48, 50, 52, 56, 58, 59, 62, 64, 67, 68, 69, 72, 75, 80, 81, 82, 84,
   85, 88, 92, 100]
 
 
def szukbin(pocz, szuk):
   kon = len(tab) - 1
   while pocz < kon:
       srod = int((pocz + kon) / 2)
       if tab[srod] < szuk:
           pocz = srod + 1
       if tab[srod] > szuk:
           kon = srod
       if tab[srod] == szuk:
           return True
   return  False
 
 
wyniki = []
for i in range(len(tab)):
   for j in range(i + 1, len(tab)):
       oczek = tab[j] + (tab[j] - tab[i])
       if szukbin(j + 1, oczek) is True:
           wyniki.append([tab[i], tab[j], oczek])
print(wyniki)
 
Zapisane
« Odpowiedz #8 : 10:31 15/02/18 »
DJangoL Offline
Professional Python User

Zobacz profil
***

Reputacja: 27
Wiadomości: 377


Co do czasu wykonania (powtórzone 1000 razy dla bardziej miarodajnego wyniku) dla tab2:

Mój:    1.515681266784668

Guaz:  4.60954475402832

Sig:     3.500128746032715


Dla tablicy większej tabd:

tabd = [2, 6, 7, 8, 10, 11, 15, 16, 18, 20, 22, 24, 26, 27, 28, 30, 32, 33, 40, 44, 48, 50, 52, 56, 58, 59, 62, 64, 67, 68, 69, 72, 75, 80, 81, 82, 84, 85, 88, 92, 100, 102, 108, 110, 112, 114, 120, 122, 124, 126, 128, 130, 132, 134, 136, 138, 140, 144, 150, 160, 163, 165, 170, 171, 172, 173, 174, 175, 176, 177, 180, 184, 185, 191, 193, 197, 200]


------------- Mój ----------------
Czas wykonania: 8.515938520431519
641 trójek

------------- Itertools ----------------
Czas wykonania: 31.29802680015564
641 trójek

------------- Szuk binarnie ----------------
Czas wykonania: 15.094305992126465
618 trójek



Druga sprawa, Twój kod nie znajduje wszystkich trójek, u mnie i Guaza z tablicy tab2 mamy 190 wyników, u Ciebie jest 180 (jakby brakowało jednego przebiegu pętli?). Podobnie w innych.

Dla takiej małej tablicy tabm:

tabm = [4, 5, 6, 8, 10, 12, 15]

Mój kod i kod Guaz daje takie wyniki:

(4, 5, 6)
(4, 6, Spoko
(4, 8, 12)
(5, 10, 15)
(6, 8, 10)
(8, 10, 12)

czyli 6 trójek.

U Ciebie kod nie znajduje jednej, konkretnie: (5, 10, 15).

----

EDIT: Im większa tablica, tym kod sig robi się coraz szybszy! Podejrzewam, że już przy 50-100% większej tablicy kod użytkownika sig będzie najszybszy.

------------- Mój ----------------

Czas wykonania: 27.89165163040161
1344

------------- Itertools ----------------

Czas wykonania: 113.9885721206665
1344

------------- Szuk binarnie ----------------

Czas wykonania: 39.72021222114563
1317


To dla tablicy tabd2:

tabd2 = [2, 6, 7, 8, 10, 11, 15, 16, 18, 20, 22, 24, 26, 27, 28, 30, 32, 33, 40, 44, 48, 50, 52, 56, 58, 59, 62, 64, 67, 68, 69, 72, 75, 80, 81, 82, 84, 85, 88, 92, 100, 102, 108, 110, 112, 114, 120, 122, 124, 126, 128, 130, 132, 134, 136, 138, 140, 144, 150, 160, 163, 165, 170, 171, 172, 173, 174, 175, 176, 177, 180, 184, 185, 191, 193, 197, 200, 202, 203, 204, 205, 206, 207, 209, 211, 212, 222, 231, 234, 235, 236, 237, 238, 239, 244, 245, 249, 251, 255, 257, 259, 260, 265, 270, 271, 275, 279, 280, 281, 282, 283, 286, 288, 290, 291, 292, 295, 300]

Zapisane
« Odpowiedz #9 : 11:57 15/02/18 »
sig Offline
Professional Python User

Zobacz profil
***

Reputacja: 84
Wiadomości: 387


Źle ustawiłem prawy zakres w szukaniu binarnym, poprawiony:
Kod
tab = [4, 5, 6, 8, 10, 12, 15]
 
def szukbin(pocz, szuk):
   kon = len(tab)
   while pocz < kon:
       srod = int((pocz + kon) / 2)
       if tab[srod] < szuk:
           pocz = srod + 1
           continue
       else:
           kon = srod
       if tab[srod] == szuk:
           return True
   return  False
 
 
wyniki = []
for i in range(len(tab)):
   for j in range(i + 1, len(tab)):
       oczek = tab[j] + (tab[j] - tab[i])
       if szukbin(j + 1, oczek) is True:
           wyniki.append([tab[i], tab[j], oczek])
print(wyniki)
 
Zapisane
« Odpowiedz #10 : 14:12 15/02/18 »
Guaz Offline
Professional Python User

Zobacz profil
***

Reputacja: 41
Płeć: Mężczyzna
Wiadomości: 310


@DJangoL zmieniłeś na kod z combinations o mniejszej złożoności?
Kod
def trojki_arytmetyczne(tablica):
   #~ Zmienna magazynująca znalezione trójki
   wszystkie_trojki = []
 
   #~ Kombinacje cyfr:
   for wybrane in combinations(tablica, 2):
       #~ wybrane = list(wybrane) # Jeśli zakładamy że lista nie będzie uporządkowana rosnąco.
       #~ wybrane.sort()
       domniemana = wybrane[1] + (wybrane[1] - wybrane[0])
       if domniemana in tablica:
           wszystkie_trojki.append((wybrane[0],wybrane[1],domniemana))
   #~ Wynik funkcji
   return wszystkie_trojki
Bo u mnie dla listy z masą trójek (poniekąd z lenistwa wygenerowaną)
Kod:
tab = [i for i in range(1, 300)]
Wychodzi że ten combinations jest szybszy od twojego o ~10% Język
(Oczywiście usunąłem otagowany jako zbędny if)
Ten którym ja testowałem o nazwie funkcji 'trojki_wg_siga' jest szybszy jeszcze o kilka % od combinations ;P. Chyba że coś zmodyfikowałeś w swoim kodzie Chichot.
A szukbin sig'a poprawiony jest chyba najszybszy Chichot. Dzięki szukaniu elementu w liście trochę lepszym sposobem niż "coś" w "tablicy" co leci pokolei zamiast wykorzystywać zależność że tablica jest posortowana Uśmiech

Kod:
IterC time: 14.296355724334717 62001
wgSig time: 14.247046947479248 62001
DjFun time: 16.07258701324463 62001
SgFun time: 7.149360656738281 62001
~~~~~~~~~~~~~~~~~~~~
To dla zakresu listy range(1,500) i dziesięciu przebiegów pętli.

Prosty kod którym testowałem ;p
Kod
from itertools import combinations
from time import time
 
 
def main():
   tab = [i for i in range(1,500)]
 
   start = time()
   for i in range(10):
       wyn = trojki_arytmetyczne(tab)
   stop = time() - start
   print("IterC time:", stop, len(wyn))
   start = time()
   for i in range(10):
       wyn = trojki_wg_siga(tab)
   stop = time() - start
   print("wgSig time:", stop, len(wyn))
 
   start = time()
   for i in range(10):
       wyn = znajdz_trojki(tab)
   stop = time() - start
   print("DjFun time:", stop, len(wyn))
 
   start = time()
   for i in range(10):
       wyn = sig_trojki(tab)
   stop = time() - start
   print("SgFun time:", stop, len(wyn))
 
 
def trojki_arytmetyczne(tablica):
   wszystkie_trojki = []
   for wybrane in combinations(tablica, 2):
       domniemana = wybrane[1] + (wybrane[1] - wybrane[0])
       if domniemana in tablica:
           wszystkie_trojki.append((wybrane[0],wybrane[1],domniemana))
   return wszystkie_trojki
 
 
def trojki_wg_siga(tablica):
   wszystkie_trojki = []
 
   for i in range(len(tablica)-1):
       for j in range(i+1, len(tablica)):
           domniemany = tablica[j] + (tablica[j] - tablica[i])
           if domniemany in tablica:
               wszystkie_trojki.append((tablica[i], tablica[j], domniemany))
   return wszystkie_trojki        
 
def znajdz_trojki(tab):
   trojki = []
   size = len(tab)
   for i in range(size - 2):
       for j in range(i + 1, size - 1):
           r = tab[j] - tab[i]
           n = tab[j] + r
           if n in tab:
               idx = tab.index(n, j + 1, size )
               if idx > j:
                    trojki.append( (tab[i], tab[j], tab[idx]) )
   return trojki
 
def sig_trojki(tab):
   def szukbin(pocz, szuk):
       kon = len(tab)
       while pocz < kon:
           srod = int((pocz + kon) / 2)
           if tab[srod] < szuk:
               pocz = srod + 1
               continue
           else:
               kon = srod
           if tab[srod] == szuk:
               return True
       return  False
   wyniki = []
   for i in range(len(tab)):
       for j in range(i + 1, len(tab)):
           oczek = tab[j] + (tab[j] - tab[i])
           if szukbin(j + 1, oczek) is True:
               wyniki.append([tab[i], tab[j], oczek])
   return wyniki
 
if __name__ == "__main__":
   main()
Zapisane

Python 3.5.2 / Mint
« Odpowiedz #11 : 22:53 27/02/18 »
SomeOne3103 Offline
Hello World!

Zobacz profil
*

Reputacja: 0
Wiadomości: 2


Z powodu wyjazdu chwilę mnie nie było, ale chciałbym podziękować wszystkim za podesłane rozwiązania Uśmiech
Zapisane
Strony: [1]   Do góry
Drukuj
Skocz do:  

© 2007 - 2018 Polish Python Coders Group
Powered by SMF 1.1.21 | SMF © 2006-2009, Simple Machines | Theme by PixelSlot