Podział tablicy na mniejsze: pomoc w zrozumieniu kodu źródłowego i algorytmu

Question

Hej.

Mam do rozwiązania problem dotyczący podziału tablicy n-elementowej na mniejsze tablice, ale z kilkoma warunkami (niepuste podtablice, itd.) Na przykład mając tablicę [1,2,3,4] jako argument, powinien zwrócić:

[
[[1, 2, 3, 4]],
[[1, 2, 3], [4]],
[[1, 2], [3, 4]],
[[1, 2], [3], [4]],
[[1], [2, 3, 4]],
[[1], [2, 3], [4]],
[[1], [2], [3, 4]],
[[1], [2], [3], [4]]     ]

 

Zamiast odkrywać koło na nowo, poszukałem trochę, ale znalazłem tylko ten wątek na jakiejś pochodnej stackoverflow, który idealnie opisuje to, czego szukam. Problem polega na tym, że rozwiązanie tego jest zapisane w jakichś chorych językach programowania, których za nic nie ogarniam, a nawet rozwiązanie w Pythonie używa konstrukcji, o której wcześniej nie miałem pojęcia.

Czy mógłby mi ktoś rozjaśnić co tam się dzieje i jak krok po kroku można osiągnąć dokładnie to, co jest opisane w tamtym wątku?

Answer 1

blem polega na tym, że rozwiązanie tego jest zapisane w jakichś chorych językach programowania, których za nic nie ogarniam

Celem codegolf.stackexchange jest zazwyczaj wyprodukowanie jak najkrótszego kodu generującego dany wynik, ignorując czytelność :)

Jest prosty algorytm rekurencyjny generujący taki wynik: dla danej listy, weź pierwsze X elementów, po czym wykonaj algorytm na pozostałych elementach i połącz pierwszą listę z wynikami rekurencyjnego wywołania.

W Twoim przykładzie: podziel np listę przy pierwszym elemencie. Pierwsza część to [1], druga to [2, 3, 4]. Wywołując algorytm na drugiej części, dostaniesz:

[[2, 3, 4]],
[[2, 3], [4]],
[[2], [3, 4]],
[[2], [3], [4]]    

Dodaj [1] do każdego z nich i dostaniesz:

[[1], [2, 3, 4]],
[[1], [2, 3], [4]],
[[1], [2], [3, 4]],
[[1], [2], [3], [4]]

Podobnie dzieląc listę [1, 2, 3, 4] na drugim elemencie dostaniesz [1, 2] i [3, 4]. Wywołując algorytm na [3, 4] dostałbyś:

[[3, 4]]
[[3], [4]]

Dodając [1, 2] do każdego z nich dostaniesz:

[[1, 2], [3, 4]],
[[1, 2], [3], [4]],

Powtarzając to dla każdego podziału dostaniesz pełny zbiór rozwiązań.

(Na oko, ten 4-punktowy oneliner pythonowy z codegolf.stackexchange robi dokładnie ten algorytm, tylko wywołuje się rekurencyjnie na pierwszej połówce podziału, nie na drugiej)

Naklepałem czytelniejszy kawałek Pythona implementującego to, ale nie wiem czy chcesz gotowca, więc na razie go nie dam :)