R1H29951BTS43
Obraz wygenerowany przez sztuczną inteligencję. Przedstawia szachownicę z ustawionymi figurami. Tło jest czarne, a figury w odcieniach koloru niebieskiego.

PYI_R_W14_M42 Ciekawe algorytmy rekurencyjne

Obraz wygenerowany przez sztuczną inteligencję Canva.ai
Źródło: domena publiczna.

Implementacja generatora permutacji w Pythonie

Linia 1. def permutacje otwórz nawias okrągły lista przecinek indeks znak równości 0 zamknij nawias okrągły dwukropek. Linia 2. if indeks znak równości znak równości len otwórz nawias okrągły lista zamknij nawias okrągły dwukropek. Linia 3. print otwórz nawias okrągły lista zamknij nawias okrągły. Linia 4. return. Linia 6. for i in range otwórz nawias okrągły indeks przecinek len otwórz nawias okrągły lista zamknij nawias okrągły zamknij nawias okrągły dwukropek. Linia 7. lista otwórz nawias kwadratowy indeks zamknij nawias kwadratowy przecinek lista otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości lista otwórz nawias kwadratowy i zamknij nawias kwadratowy przecinek lista otwórz nawias kwadratowy indeks zamknij nawias kwadratowy kratka zamiana. Linia 8. permutacje otwórz nawias okrągły lista przecinek indeks plus 1 zamknij nawias okrągły. Linia 9. lista otwórz nawias kwadratowy indeks zamknij nawias kwadratowy przecinek lista otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości lista otwórz nawias kwadratowy i zamknij nawias kwadratowy przecinek lista otwórz nawias kwadratowy indeks zamknij nawias kwadratowy kratka cofnięcie zamiany. Linia 12. kratka Przykładowe dane otwórz nawias okrągły 9 elementów zamknij nawias okrągły. Linia 13. dane znak równości otwórz nawias kwadratowy 1 przecinek 2 przecinek 3 przecinek 4 przecinek 5 przecinek 6 zamknij nawias kwadratowy. Linia 14. permutacje otwórz nawias okrągły dane zamknij nawias okrągły.

Jak działa algorytm:

  • Na pierwszej pozycji próbujemy ustawiać kolejno wszystkie 6 elementów.

  • Dla każdej takiej decyzji rekurencyjnie ustawiamy element na kolejnej pozycji.

  • Proces trwa aż do momentu, gdy wszystkie pozycje są obsadzone.

  • Każda pełna konfiguracja jest jedną permutacją.

Podsumowanie:

  • Dla 6 elementów liczba permutacji jest bardzo duża, dlatego w praktyce często:

    • nie wypisuje się wszystkich permutacji,

    • lub przerywa algorytm po znalezieniu konkretnego rozwiązania.

  • Problem ten jest klasycznym przykładem rekurencji i cofania (backtrackingu) oraz doskonałym ćwiczeniem algorytmicznego myślenia.