Zbiór potęgowy listy

Zadanie 5 z 10 · rozdział 24Trudność: 3 z 3listsubsetscombinatoricsrekurencja

Treść zadania

Otrzymujesz listę liczb całkowitych (mogą się powtarzać). Wypisz wszystkie różne podzbiory tej listy, łącznie ze zbiorem pustym i całą listą.

Kolejność elementów w podzbiorze nie ma znaczenia: z listy 1 2 1 podzbiór złożony z 1 i 2 powstaje na dwa sposoby, ale wypisujemy go tylko raz.

Dane wejściowe

  • 1. linia: n — długość listy
  • 2. linia: n liczb całkowitych oddzielonych spacjami

Dane wyjściowe

Każdy podzbiór w osobnej linii, zapisany jak lista w Pythonie (tak wypisuje ją print(lista)):

  • elementy podzbioru w kolejności niemalejącej, w nawiasach kwadratowych, oddzielone przecinkiem i spacją, np. [1, 1, 2]; pusty podzbiór to [],
  • podzbiory uporządkowane leksykograficznie: porównujemy pierwsze elementy (jako liczby, więc 9 jest przed 10), przy remisie drugie itd.; podzbiór, który jest początkiem dłuższego, stoi przed nim (np. [1] przed [1, 1]). Tak porównuje listy Python, więc sorted() na liście list daje dokładnie tę kolejność.

Ograniczenia

  • 1 ≤ n ≤ 10
  • elementy listy są z przedziału $[-100, 100]$

Uwagi

  • Wygodnie jest najpierw posortować listę, a potem generować podzbiory rekurencyjnie (dla każdego elementu: bierzemy go albo nie). Aby uniknąć powtórzeń, na danym poziomie rekurencji pomijaj element równy poprzedniemu.

Przykład

Wejście
3
1 2 1
Wyjście
[]
[1]
[1, 1]
[1, 1, 2]
[1, 2]
[2]

Potrzebujesz teorii?

Zasady obowiązujące w rozdziale 24

Trudniejsze zadania na listach: przekształcenia w miejscu, sumy prefiksowe, kopiec i programowanie dynamiczne. Liczy się nie tylko poprawny wynik, ale też dobry algorytm — w testach są także długie listy, na których rozwiązanie „sprawdzające wszystkie możliwości” nie zdąży się wykonać.

Konwencje wspólne:

  • Każde zadanie to osobny program: czyta standardowe wejście i wypisuje wynik na standardowe wyjście.
  • Program nie wypisuje komunikatów typu „Podaj liczbę:”. Tekst podany w input("…") jest ignorowany przez sprawdzarkę.
  • Lista liczb jest podawana w dwóch liniach: w pierwszej jest liczba elementów n, w drugiej n liczb całkowitych oddzielonych spacjami (o ile zadanie nie mówi inaczej).
  • Listę wynikową wypisuj w jednej linii, a jej elementy oddzielaj pojedynczą spacją (o ile zadanie nie mówi inaczej).
  • Indeksy liczymy od 0.

Zadanie pochodzi z otwartego zbioru Nauka-Programowania (z rozwiązaniami wzorcowymi). Zgłoś błąd w treści lub testach.

Python uruchomi się w przeglądarce przy pierwszym teście.

Kod zapisuje się automatycznie w tej przeglądarce. Tab wstawia wcięcie; aby opuścić edytor klawiaturą, naciśnij Esc, a potem Tab.

Testy

Program dostaje „Wejście” przez input() i musi wypisać „Oczekiwane wyjście”. Liczby porównywane są z tolerancją 0,01, a tekst podany w input("…") nie jest sprawdzany.

Test 1

Nie uruchomiono
Wejście
1
7
Oczekiwane wyjście
[]
[7]

Test 2

Nie uruchomiono
Wejście
2
10 9
Oczekiwane wyjście
[]
[9]
[9, 10]
[10]

Test 3

Nie uruchomiono
Wejście
3
5 5 5
Oczekiwane wyjście
[]
[5]
[5, 5]
[5, 5, 5]

Test 4

Nie uruchomiono
Wejście
3
3 1 2
Oczekiwane wyjście
[]
[1]
[1, 2]
[1, 2, 3]
[1, 3]
[2]
[2, 3]
[3]

Test 5

Nie uruchomiono
Wejście
4
2 1 2 1
Oczekiwane wyjście
[]
[1]
[1, 1]
[1, 1, 2]
[1, 1, 2, 2]
[1, 2]
[1, 2, 2]
[2]
[2, 2]

Test 6

Nie uruchomiono
Wejście
5
0 4 4 0 4
Oczekiwane wyjście
[]
[0]
[0, 0]
[0, 0, 4]
[0, 0, 4, 4]
[0, 0, 4, 4, 4]
[0, 4]
[0, 4, 4]
[0, 4, 4, 4]
[4]
[4, 4]
[4, 4, 4]

Test 7

Nie uruchomiono
Wejście
10
5 5 5 5 5 5 5 5 5 5
Oczekiwane wyjście
[]
[5]
[5, 5]
[5, 5, 5]
[5, 5, 5, 5]
[5, 5, 5, 5, 5]
[5, 5, 5, 5, 5, 5]
[5, 5, 5, 5, 5, 5, 5]
[5, 5, 5, 5, 5, 5, 5, 5]
[5, 5, 5, 5, 5, 5, 5, 5, 5]
[5, 5, 5, 5, 5, 5, 5, 5, 5, 5]
Uruchom z własnymi danymi