Partycja wektorowa dzieli wektor na serię wektorów, tak że ich suma jest oryginalna. Oto kilka partycji:

[3, 1, 2] = [3, 1, 2]
[3, 1, 2] = [0, 0, 1] + [0, 0, 1] + [0, 1, 0] + [1, 0, 0] + [2, 0, 0]
[3, 1, 2] = [1, 1, 2] + [2, 0, 0]

Tutaj dodawanie wektorów odbywa się elementarnie. Prawidłowa partycja nie zawiera żadnych wektorów z ujemnymi liczbami całkowitymi lub całkowicie zerowym wektorem.

Teraz wyzwaniem jest napisanie programu lub funkcji, która generuje wszystkie możliwe partycje wektorowe na podstawie wektora docelowego. To może brzmieć stosunkowo łatwo ...

... ale jest zwrot. Jeśli wektor wejściowy ma rozmiar L, a największa generowana partycja ma M elementów, nie można użyć więcej niż pamięci O (L * M).

Możesz założyć, że liczba całkowita używa pamięci O (1). Oznacza to, że musisz generować partycje podczas ich generowania. Ponadto każdą partycję należy wypisać tylko raz. Na przykład są to ta sama partycja:

[3, 1, 2] = [3, 0, 2] + [0, 1, 0]
[3, 1, 2] = [0, 1, 0] + [3, 0, 2]

Jeśli miałbyś wypisać, Twoja odpowiedź jest nieprawidłowa.

Wszystkie partycje dla [3, 2]:

[3, 2]
[0, 1] + [3, 1]
[0, 1] + [0, 1] + [3, 0]
[0, 1] + [0, 1] + [1, 0] + [2, 0]
[0, 1] + [0, 1] + [1, 0] + [1, 0] + [1, 0]
[0, 1] + [1, 0] + [2, 1]
[0, 1] + [1, 0] + [1, 0] + [1, 1]
[0, 1] + [1, 1] + [2, 0]
[0, 2] + [3, 0]
[0, 2] + [1, 0] + [2, 0]
[0, 2] + [1, 0] + [1, 0] + [1, 0]
[1, 0] + [2, 2]
[1, 0] + [1, 0] + [1, 2]
[1, 0] + [1, 1] + [1, 1]
[1, 1] + [2, 1]
[1, 2] + [2, 0]

Aby przetestować swoją odpowiedź, uruchom ją [3, 2, 5, 2]. Powinien wygenerować 17939 partycji, z których wszystkie są sumowane [3, 2, 5, 2]i wszystkie są unikalne (możesz przetestować unikalność, najpierw sortując każdą partycję leksykograficznie).

Najkrótszy kod w bajtach wygrywa.

Python 2, 289 bajtów

Prosty algorytm brutalnej siły. Traktuje całą listę jako liczbę w bazie max(input)+1( b) i sprawdza każdą „liczbę” w zakresie, [0, b**(L*M))aby sprawdzić, czy:

1. Sumy do właściwej kwoty
2. Jest w kolejności alfabetycznej (zapewnia wyjątkowość)

Jeśli lista spełnia te kryteria, program wysyła ją z usuniętymi wszystkimi wektorami zerowymi.

Zużycie pamięci

Największą strukturą danych, której używam w tym programie, jest podwójnie zagnieżdżona lista o długości listy Mzawierającej długość liss Ldla zapewnienia O(L*M)pamięci.

Dla moich innych struktur danych mam 3 globalne liczby całkowite O(3), 1 długość listy L( O(L)), 1 długość tablicy M( O(M)) i kopię największej tablicy podczas wyświetlania ( O(L*M)).

W sumie daje mi to użycie pamięci, O(2*L*M + L + M + 3)które upraszcza O(L*M), spełniając kryteria.

Złożoność czasowa

Jako algorytm brutalnej siły, ten algorytm jest bardzo wolny. Aby pętla while została zamknięta, musi być ostatnim intem w tablicy b-1. Pętla musi zostać uruchomiona b**(L*M)zanim to nastąpi.

Ponadto za każdym razem, gdy lista jest uruchamiana, musi sprawdzić oba warunki i wydrukować listę w najgorszym przypadku, używając L*M+L+Miteracji. Upraszcza to przedstawienie całości O(L*M * b**(L*M)). Próbowałem przetestować program [3, 2, 5, 2], ale poddałem się po 45 minutach.

Program w golfa

v=input()
L=len(v)
M=sum(v)
b=max(v)
R=range
t=[L*[0]for i in R(M)]
def A(l,i):
 if i<L*M-1and~-b<l[i/L][i%L]:A(l,i+1)
 l[i/L][i%L]=-~l[i/L][i%L]%-~b
while t[-1][-1]<b:
 if v==[sum(q[i]for q in t)for i in R(L)]and all(`t[i]`>=`t[i+1]`for i in R(M-1)):print[x for x in t if[0]*L!=x]
 A(t,0)

Być może będę w stanie zagrać w golfa trochę więcej, szczególnie część przyrostową. Nadchodzi nieznany kod.