Zbiór n
liczb dodatnich ma 2^n
podzbiory. Nazwiemy zestaw „ładnym”, jeśli żaden z tych podzbiorów nie ma takiej samej sumy. {2, 4, 5, 8}
to jeden taki fajny zestaw. Ponieważ żaden z podzbiorów nie ma takiej samej sumy, możemy sortować podzbiory według sumy:
[{}, {2}, {4}, {5}, {2, 4}, {2, 5}, {8}, {4, 5}, {2, 8}, {2, 4, 5}, {4, 8}, {5, 8}, {2, 4, 8}, {2, 5, 8}, {4, 5, 8}, {2, 4, 5, 8}]
Jeśli oznaczymy liczby [2, 4, 5, 8]
symbolami [a, b, c, d]
w porządku rosnącym, otrzymamy następującą abstrakcyjną kolejność:
[{}, {a}, {b}, {c}, {a, b}, {a, c}, {d}, {b, c}, {a, d}, {a, b, c}, {b, d}, {c, d}, {a, b, d}, {a, c, d}, {b, c, d}, {a, b, c, d}]
Kolejny ładny zestaw liczb dodatnich może mieć tę samą abstrakcyjną kolejność lub inną. Na przykład [3, 4, 8, 10]
jest ładny zestaw z innym abstrakcyjnym uporządkowaniem:
[{}, {a}, {b}, {a, b}, {c}, {d}, {a, c}, {b, c}, {a, d}, {b, d}, {a, b, c}, {a, b, d}, {c, d}, {a, c, d}, {b, c, d}, {a, b, c, d}]
W tym wyzwaniu musisz policzyć liczbę odrębnych abstrakcyjnych porządków ładnych zbiorów n
liczb dodatnich. Sekwencja ta to OEIS A009997 , a znane wartości, począwszy od n=1
, są następujące:
1, 1, 2, 14, 516, 124187, 214580603
Na przykład, dla n=3
następujących są dwa możliwe abstrakcyjne porządki:
[{}, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}]
[{}, {a}, {b}, {a, b}, {c}, {a, c}, {b, c}, {a, b, c}]
Dla n=4
dodaje to 14 możliwych abstrakcyjne uporządkowania, plus przykładem ładny zestaw z tym zamawiającego:
[{}, {a}, {b}, {a, b}, {c}, {a, c}, {b, c}, {a, b, c}, {d}, {a, d}, {b, d}, {a, b, d}, {c, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [8, 4, 2, 1]
[{}, {a}, {b}, {a, b}, {c}, {a, c}, {b, c}, {d}, {a, b, c}, {a, d}, {b, d}, {a, b, d}, {c, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [10, 6, 3, 2]
[{}, {a}, {b}, {a, b}, {c}, {a, c}, {d}, {b, c}, {a, d}, {a, b, c}, {b, d}, {a, b, d}, {c, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [10, 7, 4, 2]
[{}, {a}, {b}, {a, b}, {c}, {a, c}, {d}, {a, d}, {b, c}, {a, b, c}, {b, d}, {a, b, d}, {c, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [8, 6, 4, 1]
[{}, {a}, {b}, {a, b}, {c}, {d}, {a, c}, {b, c}, {a, d}, {b, d}, {a, b, c}, {a, b, d}, {c, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [10, 8, 4, 3]
[{}, {a}, {b}, {a, b}, {c}, {d}, {a, c}, {a, d}, {b, c}, {b, d}, {a, b, c}, {a, b, d}, {c, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [8, 7, 4, 2]
[{}, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}, {d}, {a, d}, {b, d}, {c, d}, {a, b, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [10, 4, 3, 2]
[{}, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {d}, {a, b, c}, {a, d}, {b, d}, {c, d}, {a, b, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [8, 4, 3, 2]
[{}, {a}, {b}, {c}, {a, b}, {a, c}, {d}, {b, c}, {a, d}, {a, b, c}, {b, d}, {c, d}, {a, b, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [8, 5, 4, 2]
[{}, {a}, {b}, {c}, {a, b}, {a, c}, {d}, {a, d}, {b, c}, {a, b, c}, {b, d}, {c, d}, {a, b, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [10, 7, 6, 2]
[{}, {a}, {b}, {c}, {a, b}, {d}, {a, c}, {b, c}, {a, d}, {b, d}, {a, b, c}, {c, d}, {a, b, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [8, 6, 4, 3]
[{}, {a}, {b}, {c}, {a, b}, {d}, {a, c}, {a, d}, {b, c}, {b, d}, {a, b, c}, {c, d}, {a, b, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [10, 8, 6, 3]
[{}, {a}, {b}, {c}, {d}, {a, b}, {a, c}, {b, c}, {a, d}, {b, d}, {c, d}, {a, b, c}, {a, b, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [8, 6, 5, 4]
[{}, {a}, {b}, {c}, {d}, {a, b}, {a, c}, {a, d}, {b, c}, {b, d}, {c, d}, {a, b, c}, {a, b, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [7, 6, 5, 3]
Poniższe informacje nie są prawidłowym porządkiem abstrakcyjnym:
{}, {a}, {b}, {c}, {d}, {a,b}, {e}, {a,c}, {b,c}, {a,d}, {a,e}, {b,d}, {b,e}, {c,d}, {a,b,c}, {a,b,d}, {c,e}, {d,e}, {a,b,e}, {a,c,d}, {a,c,e}, {b,c,d}, {b,c,e}, {a,d,e}, {b,d,e}, {a,b,c,d}, {c,d,e}, {a,b,c,e}, {a,b,d,e}, {a,c,d,e}, {b,c,d,e}, {a,b,c,d,e}
To zamówienie oznacza, że:
d < a + b
b + c < a + d
a + e < b + d
a + b + d < c + e
Podsumowanie tych nierówności daje:
2a + 2b + c + 2d + e < 2a + 2b + c + 2d + e
co jest sprzecznością. Twój kod nie może liczyć tego zamówienia. Takie kontrprzykłady pojawiają się po raz pierwszy w n=5
. Przykład z tego artykułu , przykład 2.5 na stronie 3.
To zamówienie jest nieważne, mimo że A < B
implikuje to A U C < B U C
, że w przypadku C
rozłączenia z A
i B
.
Twój kod lub program musi być wystarczająco szybki, abyś mógł go uruchomić do końca n=4
przed przesłaniem.
Zgłoszenia mogą być jak zwykle programami, funkcjami itp.
Standardowe luki są jak zawsze zabronione. To jest kod golfowy, więc wygrywa najkrótsza odpowiedź w bajtach. Zapraszam do zadawania wyjaśnień w komentarzach.
źródło
Odpowiedzi:
Python 3 + SciPy,
396390385351336355 bajtówWypróbuj online!
Działa to teraz przez n = 5 za około 5 sekund.
if~-(v in u):
Mogą być usunięte do -18 bajtów ale ogromne kary wydajności.Jeśli chcesz wydrukować wszystkie abstrakcyjne uporządkowania w takiej postaci, w jakiej są znalezione, zamiast je tylko zliczać, dodaj
if c:print(s.x.round(),y)
przedfor
pętlą. (Podzbiory są reprezentowane przez binarne liczby całkowite, przy czym każdy bit odpowiada obecności lub nieobecności jednego elementu: { a , c , d } ↔ 1101₂ = 13.)Jak to działa
f
rekurencyjnie zlicza uporządkowania abstrakcyjne spełniające daną listę ograniczeń. Zaczynamy od ograniczeń n ≤ a , a + n ≤ b , b + n ≤ c , c + n ≤ d . Stosując programowanie liniowe, znajdujemy rozwiązanie dla ograniczeń (lub zwracamy 0, jeśli nie ma takiego) - w tym przypadku otrzymujemy a = 4, b = 8, c = 12, d = 16. Zaokrąglamy rozwiązanie do liczb całkowitych , a następnie oblicz porządkowanie referencji, sortując wszystkie jego podzbiory według ich sumy:{ a }, { b }, { c }, { a , b }, { d }, { a , c }, { a , d }, { b , c }, { b , d }, { a , b , c }, { c , d }, { a , b , d }, { a , c , d }, { b , c , d }, {a , b , c , d }
Zaokrąglenie nie może powodować naruszenia żadnych ograniczeń o więcej niż n / 2, dlatego dodaliśmy margines n .
Ponieważ Python
sorted
jest stabilny, wszelkie powiązania między podzbiorami są zrywane w tej samej kolejności odwrotnej leksykografii, w której je wygenerowaliśmy. Więc możemy sobie wyobrazić zastąpienie { a , b , c , d } przez { a · 2 ^ n + 2 ^ 0, b · 2 ^ n + 2 ^ 1, c · 2 ^ n + 2 ^ 2, d · 2 ^ n + 2 ^ 3}, aby uzyskać to samo zamówienie bez żadnych powiązań.Planuje się kategoryzowanie wszystkich innych abstrakcyjnych porządków według analizy przypadków w oparciu o to, gdzie najpierw nie zgadzają się z porządkiem referencyjnym:
Albo { a }> { b },
albo { a } <{ b }> { c },
lub { a } <{ b } <{ c }> { a , b }
lub { a } <{ b } < { c } <{ a , b }> { d },
⋮
W każdym przypadku dodajemy nowe ograniczenia z marginesem n i rekurencyjnie wywołujemy je
f
z dodanymi nowymi ograniczeniami.Notatki
Przez pewien czas przypuszczałem (ale nie zakładałem), że rozwiązania programu liniowego z marginesem 1 na ograniczeniach zawsze będą liczbami całkowitymi. To okazuje się fałszywe: kontrprzykład n = 7 to {2,5, 30, 62,5, 73,5, 82, 87,5, 99,5}.
Python, 606 bajtów (szybszy, brak bibliotek zewnętrznych)
Wypróbuj online!
Działa to przez n = 5 za kwadrans, a n = 6 za 230 sekund (75 sekund w PyPy).
Zawiera ręcznie zakodowane narzędzie do programowania liniowego z wykorzystaniem matematyki liczb całkowitych w jednorodnych współrzędnych, aby uniknąć problemów z zaokrąglaniem zmiennoprzecinkowym.
źródło
options={'tol':.1}
, co wydaje się rozwiązywać problem.Rubinowy, 308 bajtów, znacznie szybciej
Uruchamia obudowę 4 w ~ 150ms. Nie jest używana specjalistyczna biblioteka.
Na przykład rekurencyjnie przeplata wynik drobnego przypadku
z odpowiednimi podzbiorami z dodanym dodatkowym elementem - muszą zachować tę samą względną kolejność. Zapewnia również dodanie nowego singletonu po wszystkich poprzednich singletonach.
Część sprawdzająca zgodność jest taka sama jak poprzednio, ale nie kombinacje do testowania są znacznie mniejsze.
Wersja rozszerzona i komentowana:
Rubinowy, 151 bajtów, dość wolny
(przypadek trzech elementów zajmuje << 1s, przypadek czterech nadal trwa)
Działa na reprezentacji pól bitowych podzbiorów, więc w razie potrzeby konieczne może być masowanie danych wyjściowych, aby wyświetlić same podzbiory.
sformatowany:
źródło
...x-1
=>..x-2
,.select{...}.count
=>.count{...}
,|(x,y)|
=>|x,y|
,x&~y==0||y&~x!=0
=>x&~y<1||y&~x>0
ponieważa&~b
nie mogę być negatywny, jeśli się nie mylęn=5
właśnie dodany kontrprzykład. Jeśli się nie mylę, twój kod by to zaakceptował.P
, więc nie może być anonimowa. Sądzę też, że nadal się nie udaje z powodu opublikowanego przez nas kontrprzykładu.P=
). Myślę też, że musisz zwrócić liczbę, więc być może będziesz musiał.size
gdzieś tam wpisać.