Najpierw kilka definicji:
- Biorąc pod uwagę
n
ik
, rozważ posortowaną listę multisetów , gdzie dla każdego multisetu wybieramyk
liczby{0, 1, ..., n-1}
z powtórzeniami.
Na przykład dla n=5
i k=3
mamy:
[(0, 0, 0), (0, 0, 1), (0, 0, 2), (0, 0, 3), (0, 0, 4), (0, 1, 1), ( 0, 1, 2), (0, 1, 3), (0, 1, 4), (0, 2, 2), (0, 2, 3), (0, 2, 4), (0, 3, 3), (0, 3, 4), (0, 4, 4), (1, 1, 1), (1, 1, 2), (1, 1, 3), (1, 1, 4), (1, 2, 2), (1, 2, 3), (1, 2, 4), (1, 3, 3), (1, 3, 4), (1, 4, 4) , (2, 2, 2), (2, 2, 3), (2, 2, 4), (2, 3, 3), (2, 3, 4), (2, 4, 4), ( 3, 3, 3), (3, 3, 4), (3, 4, 4), (4, 4, 4)]
- Częścią jest lista multisets z własności, że wielkość przecięcia wszystkich multisets w części wynosi co najmniej
k-1
. To znaczy, że bierzemy wszystkie multisety i przecinamy je (używając przecięcia multiset) jednocześnie. Jako przykład,[(1, 2, 2), (1, 2, 3), (1, 2, 4)]
jest częścią, ponieważ jej przecięcie ma rozmiar 2, ale[(1, 1, 3),(1, 2, 3),(1, 2, 4)]
nie jest, ponieważ jego przecięcie ma rozmiar 1.
Zadanie
Twój kod powinien przyjąć dwa argumenty n
i k
. Następnie powinien łapczywie przejrzeć te multisety w posortowanej kolejności i wypisać części listy. W takim przypadku n=5, k=3
poprawne partycjonowanie to:
(0, 0, 0), (0, 0, 1), (0, 0, 2), (0, 0, 3), (0, 0, 4)
(0, 1, 1), (0, 1, 2), (0, 1, 3), (0, 1, 4)
(0, 2, 2), (0, 2, 3), (0, 2, 4)
(0, 3, 3), (0, 3, 4)
(0, 4, 4)
(1, 1, 1), (1, 1, 2), (1, 1, 3), (1, 1, 4)
(1, 2, 2), (1, 2, 3), (1, 2, 4)
(1, 3, 3), (1, 3, 4)
(1, 4, 4)
(2, 2, 2), (2, 2, 3), (2, 2, 4)
(2, 3, 3), (2, 3, 4)
(2, 4, 4)
(3, 3, 3), (3, 3, 4)
(3, 4, 4), (4, 4, 4)
Oto kolejny przykład n = 4, k = 4
.
(0, 0, 0, 0), (0, 0, 0, 1), (0, 0, 0, 2), (0, 0, 0, 3)
(0, 0, 1, 1), (0, 0, 1, 2), (0, 0, 1, 3)
(0, 0, 2, 2), (0, 0, 2, 3)
(0, 0, 3, 3)
(0, 1, 1, 1), (0, 1, 1, 2), (0, 1, 1, 3)
(0, 1, 2, 2), (0, 1, 2, 3)
(0, 1, 3, 3)
(0, 2, 2, 2), (0, 2, 2, 3)
(0, 2, 3, 3), (0, 3, 3, 3)
(1, 1, 1, 1), (1, 1, 1, 2), (1, 1, 1, 3)
(1, 1, 2, 2), (1, 1, 2, 3)
(1, 1, 3, 3)
(1, 2, 2, 2), (1, 2, 2, 3)
(1, 2, 3, 3), (1, 3, 3, 3)
(2, 2, 2, 2), (2, 2, 2, 3)
(2, 2, 3, 3), (2, 3, 3, 3)
(3, 3, 3, 3)
Wyjaśnienie, co oznacza chciwość : Z kolei dla każdego zbioru wielosetowego sprawdzamy, czy można go dodać do istniejącej części. Jeśli tak, możemy to dodać. Jeśli nie, zaczniemy nową część. Patrzymy na multisety w posortowanej kolejności, jak w przykładzie podanym powyżej.
Wynik
Możesz wydzielić partycjonowanie w dowolnym rozsądnym formacie, jaki ci się podoba. Jednak multisety powinny być zapisywane poziomo w jednym wierszu. Oznacza to, że pojedynczy multiset nie powinien być zapisywany w pionie ani rozłożony na kilka wierszy. Możesz wybrać sposób oddzielenia reprezentacji części na wyjściu.
Założenia
Możemy to założyć n >= k > 0
.
źródło
(0, 4, 4)
sam? Biorąc pod uwagę twój opis, sądzę, że będzie to jego „część”(0, 4, 4), (1, 4, 4), (2, 4, 4), (3, 4, 4), (4, 4, 4)
. Podobnie(0, 0, 3, 3)
w drugim przypadku testowym.Odpowiedzi:
Galaretka ,
2625 bajtówPełny program, który wyświetla reprezentację listy list, z których każda jest częścią, np. Dla n = 5, k = 3:
Uwaga: zastosowana reprezentacja usuwa zbędne
[
i]
wokół list długości 1.Wypróbuj online! lub zobacz ładną wersję do wydruku (koszt 3 bajtów)
W jaki sposób?
źródło
MATLAB, 272 bajty
Wynik:
Dwie puste linie między różnymi częściami.
Nie golfowany:
Wyjaśnienie:
Najpierw znajdujemy wszystkie multisety z brutalną siłą:
repmat(0:n-1, 1, k)
powtarza wektor wartości od0
don-1
k
czasu.nchoosek(x, k)
zwraca macierz zawierającą wszystkie kombinacje k powtórzonego wektora.sort(x, 2)
sortuje wszystkie kombinacje k, a następnieunique(x, 'rows')
usuwa wszystkie duplikaty.p=zeros(0,k);
tworzy pustą macierz zk
kolumnami. Użyjemy go jako stosu. Przy każdej iteracji najbardziej zewnętrznejfor
pętli najpierw dodajemy bieżący multiset do wspomnianego stosu:p=[p;l(i,:)];
.Następnie sprawdzamy, czy przecięcie wszystkich multiset w stosie jest co najmniej
k-1
długie za pomocą następującego kodu (nie możemy użyćintersect
polecenia MATLAB do sprawdzenia przecięć, ponieważ zwraca zestaw, ale potrzebujemy multisetu):Teraz, jeśli skrzyżowanie jest wystarczająco długie
a == 0
, w przeciwnym raziea == 1
.Jeśli przecięcie nie jest wystarczająco długie, wypisujemy nowy wiersz i opróżniamy stos:
Następnie drukujemy tylko bieżący multiset:
źródło
MATL , 34 bajty
Części są oddzielone linią zawierającą białe znaki.
Wypróbuj online!
Wyjaśnienie
Uwaga: ta metoda wydaje się działać (i działa w przypadkach testowych), ale nie mam dowodu, że zawsze działa
Multisety są sortowane, zarówno wewnętrznie (tj. Każdy multiset ma nie zmniejszające się wpisy), jak i zewnętrznie (tj. Multiset M występuje przed multisetem N, jeśli M poprzedza N leksykograficznie).
Aby obliczyć przecięcie wielosetowe, posortowane multisety są ułożone jako rzędy macierzy, a kolejne różnice są obliczane wzdłuż każdej kolumny. Jeśli wszystkie kolumny oprócz co najwyżej jednej mają wszystkie różnice równe zero, multisety należą do tej samej części.
Ten test dałby wynik fałszywie ujemny w przypadku multisetów takich jak
(1,2,3)
i(2,3,4)
: nawet jeśli2
,3
są wspólne wpisy, nie będzie wykrywany jako taki, ponieważ są one w niedopasowanych kolumn.Nie wydaje się to jednak problemem, przynajmniej w przypadkach testowych. Wygląda na to, że test między multisetami jak
1,2,3
i2,3,4
nigdy tak naprawdę nie musi być wykonany, ponieważ niektóre pośrednie multisety dały wynik ujemny, a więc już są w różnych częściach. Jeśli jest to rzeczywiście prawda, powód niewątpliwie ma związek z faktem, że multisety są sortowane.Ale nie mam na to dowodu. To po prostu wydaje się działać.
źródło
n=k=4
przypadku, gdy zaczynamy od nowej części(0, 0, 3, 3)
, wektoryzowana kolejna różnica tego i poprzedniego zestawu wielu elementów(0, 0, 2, 3)
ma tylko jedną różnicę, więc w jaki sposób „jak dotąd część” sprawia, że to działa? (lub równoważnie jaki był wynik z poprzedniego kroku, który został zastosowany zamiast(0, 0, 2, 3)
?)PHP, 245 bajtów
Wypróbuj online!
Rozszerzony
Dane wyjściowe jako ciąg
n> 15 dla większej precyzji
źródło
0
do(16**16-1)%16
i wersja długa praca tylko z precyzją, która jest potrzebna don>15
bcmod(bcsub(bcpow(16,16),1),16)
jest15
php.net/manual/en/ref.bc.php