[Adaslaw]

Jak ktoś lubi rozgrzewki z #algorytmika / #algorytmy to może się rozgrzać na zadaniu:

Mamy tablicę z n liczbami naturalnymi, np.: [1, 2, 3, 5, 6, 8, 11, 1].
Mamy też liczbę k > 0.

Napisz algorytm, który przesunie elementy w tablicy (w prawo lub w lewo - tu nie jest to istotne), o k pozycji.
Naturalnie należy uniknąć alokowania pomocniczej tablicy o rozmiarze n.

Przykład:
Tablica: [1, 2, 3, 4, 5]
k: 2

Wynik: [4, 5, 1, 2, 3]

Udanej zabawy :)

#programowanie

[mk321]

@Adaslaw: daj coś gdzie trzeba pomyśleć, a nie jakąś algorytmikę, gdzie byle ChatGPT to rozwiązuje z palcem w danych.

def rotate_right(arr, k):
    n = len(arr)
    k = k % n  # obsługa k >

[MonsieurLaBoule]

@Adaslaw: to będzie coś w tym stylu?

[groman43]

@Adaslaw: Po prostu zapamiętujesz pierwszy / ostatni element w tablicy, przesuwasz wszyskie pozostałe elementy w tablicy a potem wstawiasz wcześniej zapamiętany element na pierwsze / ostatnie miejsce w tablicy. Powtarzasz odpowiednią liczbę razy. Złożoność obliczeniowa O(n) - liczba kroków algorytmu jest zdominowana przez liczbę przesunięć, a im większa tablica, tym więcej tych przesunięć. Złożoność pamięciowa O(1), zawsze pamiętasz tylko jeden element.
Może można prościej, ale jest środek nocy i wolę

[Adaslaw]

@mk321: całkiem spoko algorytm. Robi 3 przebiegi po tablicy, zamiast jednego przebiegu, ale złożoność czasowa wciąż pozostaje O(n).

[Adaslaw]

jeśli zrobił się cykl i nie wszystkie przepisane to zaczynami początkowe i + 1

@MonsieurLaBoule:
Całkiem spoko algorytm zaproponowałeś.
Jednak nie rozwikłałeś tu jednej kwestii. Napisałeś "to zaczynami początkowe i + 1". OK, ale tak sobie zaczynamy od kolejnych i+1, ale kiedy to kończymy? :) Na którym 'i' kończymy tę zabawę? :)

[mk321]

Robi 3 przebiegi po tablicy, zamiast jednego przebiegu, ale złożoność czasowa wciąż pozostaje O(n).

@Adaslaw: O(n + k + (n - k)) = O(2n) = O(n)

[maroslawxp]

@Adaslaw: Pytanie jaki język. W pythonie wystarczy jenda linijka ;)

rotate = lambda tab, k: tab[-k:] + tab[:-k]

[Adaslaw]

@groman43:
O ile rozumiem Twoją propozycję, to takich przesunięć wszystkich elementów całej tablicy będzie 'k'. To trochę dużo ;)

[MonsieurLaBoule]

@Adaslaw możemy policzyć jaką długość ma cykl przy pierwszej iteracji, potem podzielimy len tablicy przez długość cyklu i wyjdzie ilość iteracji

[Adaslaw]

O(n + k + (n - k)) = O(2n) = O(n)

@mk321: Faktycznie, robi 2 przebiegi po tablicy, a nie jak napisałem wcześniej 3.
Ale jak już się wcześniej zgodziłem, złożoność czasowa pozostaje O(n).

[Adaslaw]

możemy policzyć jaką długość ma cykl przy pierwszej iteracji, potem podzielimy len tablicy przez długość cyklu i wyjdzie ilość iteracji

@MonsieurLaBoule:
Na szybko myślę, że masz rację i to powinno zadziałać poprawnie.

[groman43]

@Adaslaw: Tak jak pisałem - o tej godzinie wolę oglądać filmy dokumentalne ( ͡º ͜ʖ͡º)

[kamikadze97]

Tablica: [1, 2, 3, 4, 5]

k: 2

Wynik: [4, 5, 1, 2, 3]

@Adaslaw: Nie czaje co to znaczy przesunac o k pozycji. Dlaczego jest taki wynik?

[Adaslaw]

@kamikadze97 w tym moim przykładzie widać, że w wynikowej tablicy wszystkie elementy są przesunięte w prawo o 2 pozycję.

[null_ptr]

Po prostu zapamiętujesz pierwszy / ostatni element w tablicy, przesuwasz wszyskie pozostałe elementy w tablicy a potem wstawiasz wcześniej zapamiętany element na pierwsze / ostatnie miejsce w tablicy. Powtarzasz odpowiednią liczbę razy. Złożoność obliczeniowa O(n) - liczba kroków algorytmu jest zdominowana przez liczbę przesunięć, a im większa tablica, tym więcej tych przesunięć. Złożoność pamięciowa O(1), zawsze pamiętasz tylko jeden element.

Może można prościej, ale jest środek nocy i wolę oglądać film dokumentalny

[tomekb1999]

@null_ptr: bo takie przesunięcie elementów to permutacja, a te można reprezentować jako macierze. Ja kombinowałem jeszcze z rozkładem permutacji na transpozycje, wtedy naraz zamieniamy tylko dwa elementy, to chyba też da złożoność czasową O(n).

[walokid]

@maroslawxp w nowoczesnym cpp też jest na to funkcja. Shift czy coś