O serii
Po pierwsze, możesz potraktować to jak każde inne wyzwanie związane z golfem i odpowiedzieć na nie, nie martwiąc się serią. Istnieje jednak tabela wyników dla wszystkich wyzwań. Możesz znaleźć tabelę liderów wraz z kilkoma więcej informacji o serii w pierwszym poście .
Chociaż mam szereg pomysłów w szeregu, przyszłe wyzwania nie są jeszcze ustalone. Jeśli masz jakieś sugestie, daj mi znać w odpowiednim poście z piaskownicą .
Dziura 3: partycje całkowite
Czas trochę zwiększyć trudność.
Partycja o dodatnia n
jest zdefiniowany jako MultiSet liczb całkowitych, które sumują się do pozytywnych n
. Na przykład, jeśli n = 5
istnieją następujące partycje:
{1,1,1,1,1}
{2,1,1,1}
{2,2,1}
{3,1,1}
{3,2}
{4,1}
{5}
Należy pamiętać, że są to multisets, więc nie ma celu nich {3,1,1}
, {1,3,1}
i {1,1,3}
są uważane za identyczne.
Twoim zadaniem jest n
wygenerowanie losowej partycji n
. Oto szczegółowe zasady:
Rozkład produkowanych przegród musi być jednolity . Oznacza to, że w powyższym przykładzie każda partycja powinna zostać zwrócona z prawdopodobieństwem 1/7.
Oczywiście, ze względu na ograniczenia techniczne PRNG, idealna jednolitość będzie niemożliwa. W celu oceny jednolitości przesłanych danych następujące operacje zostaną uznane za zapewniające idealnie jednolite rozkłady:
- Uzyskiwanie numeru z PRNG (w dowolnym zakresie), który jest udokumentowany jako (w przybliżeniu) jednolity.
- Mapowanie równomiernego rozkładu większego zbioru liczb na mniejszy zbiór poprzez modulo lub mnożenie (lub inną operację, która równomiernie rozprowadza wartości). Większy zestaw musi zawierać co najmniej 1024 razy więcej możliwych wartości niż mniejszy zestaw.
Ponieważ partycje są wielosektorowe, możesz zwracać je w dowolnej kolejności, a ta kolejność nie musi być spójna. Jednak dla celów losowego rozkładu kolejność jest ignorowana. Oznacza to, że w powyższym przykładzie
{3,1,1}
,{1,3,1}
a{1,1,3}
razem muszą mieć prawdopodobieństwo 1/7 zwracane.- Twój algorytm musi mieć deterministyczne środowisko wykonawcze. W szczególności nie można generować losowych multiset i odrzucać ich, jeśli się nie sumują
n
. - Złożoność czasowa algorytmu musi być wielomianowa
n
. W szczególności nie można po prostu wygenerować wszystkich partycji i wybrać losowej (ponieważ liczba partycji rośnie wykładniczon
). Możesz założyć, że używany PRNG może zwracać równomiernie rozłożone wartości w O (1) na wartość. - Nie wolno używać żadnej wbudowanej funkcji, która rozwiązuje to zadanie.
Możesz napisać pełny program lub funkcję i pobrać dane wejściowe za pomocą STDIN lub najbliższej alternatywy, argumentu wiersza poleceń lub argumentu funkcji i wygenerować wynik poprzez wartość zwracaną lub drukując do STDOUT (lub najbliższej alternatywy).
Możesz założyć, że n ≤ 65
(tak, że liczba partycji jest mniejsza niż 2 21 ). Dane wyjściowe mogą być w dowolnym dogodnym, jednoznacznym formacie listy lub ciągu.
Jeśli przesyłasz funkcję, zastanów się nad zapewnieniem małego programu testowego, który wywołuje tę funkcję wiele razy i drukuje wyniki. Nie ma potrzeby modyfikowania parametrów w kodzie. Ma to na celu sprawdzenie, czy rozwiązanie jest w przybliżeniu jednolite.
To jest kod golfowy, więc wygrywa najkrótsze przesłanie (w bajtach). I oczywiście najkrótsze zgłoszenie na użytkownika wejdzie również do ogólnej tabeli liderów serii.
Tabela liderów
Pierwszy post z serii generuje tabelę wyników.
Aby upewnić się, że Twoje odpowiedzi się pojawią, zacznij każdą odpowiedź od nagłówka, używając następującego szablonu Markdown:
# Language Name, N bytes
gdzie N
jest rozmiar twojego zgłoszenia. Jeśli poprawić swój wynik, to może zachować stare porachunki w nagłówku, uderzając je przez. Na przykład:
# Ruby, <s>104</s> <s>101</s> 96 bytes
(Język nie jest obecnie wyświetlany, ale fragment go wymaga i analizuje, a w przyszłości mogę dodać tabelę wyników według języków).
źródło
u/\. y
wkrótce dostanie coś takiego jak J.GolfScript, 90 bajtów
Demo online
Jest to adaptacja mojego (prostszego) kodu zliczania partycji, który zamiast śledzić liczbę śledzi zarówno liczbę, jak i jednolicie wybrany jeden z elementów zliczanych.
Bezpośrednie porównanie tych dwóch:
Różnice:
~
wynika z tego, że jest to program, a nie fragment kodu.[1.]
zastąpienia1
odpowiada zmianie o co śledzone.{(\{)}%+}%
zwiększa każdy element w tej partycji i{1+}%
dodaje1
do partycji.0
staje się[0]
(grał w golfa1,
) w ramach zmiany tego, co jest śledzone, ale ponieważ musi pozostać tablicą, gdy zostanie dodana do innej, potrzebuje dodatkowych[ ]
.{+}*
staje się ważonym wyborem z partycji w połączeniu z sumowaniem ich liczby.(;`
Usuwa liczyć od wyjścia i stawia partycji w formacie miły.Ramy testowe
Dostosuj początkową 7000, jeśli chcesz uruchomić inną liczbę prób. Zauważ, że jest to zdecydowanie zbyt wolne, aby można było obejrzeć demo online.
źródło
Java,
285267 bajtówJest to ta sama metoda, co odpowiedź TheBestOne, ale używa prostej tablicy zamiast mapy. Ponadto zamiast zwracać losową partycję jako a
List
, drukuje ją na konsoli.Poniżej znajduje się program testowy, który uruchamia go 100 000 razy. Na przykład
n=5
, wszystkie zestawy znajdowały się w granicach 0,64% idealnej 1/7 w ostatnim biegu.źródło
Math.min
sprowadzić do(k<n?k:n)
, można iść dalej przez wodowania go całkowicie i po prostu robi dwie kontrole:b<k&b++<n
. Możesz również łatwo porzucićn>0
część pętli warunkowej (ponieważn>0&b<n
zmniejsza się dob<n
momentu, w którymb
gwarantowane jest nieujemne).int
deklaracji.CJam,
6456 bajtówMożesz to przetestować za pomocą tego skryptu:
Wyjaśnienie
źródło
Pyth, 64 bajty
Używa /programming//a/2163753/4230423, z wyjątkiem tego, że a) Brak pamięci podręcznej, ponieważ Pyth automatycznie zapamiętuje, b) Drukuje każdą zamiast dołączania do listy, i c) jest tłumaczone na Pyth.
Wyjaśnię to, kiedy będę miał czas, ale oto odpowiedni kod python:
Edycja: W końcu zacząłem wyjaśniać:
źródło
Oktawa, 200
Nie golfowany:
Zbuduj kwadratową macierz, w której każda komórka (m, n) odzwierciedla liczbę partycji,
m
których największa liczba jestn
, zgodnie z uprzejmym cytowaniem wyciągu Knuth @feersum. Na przykład5,2
daje nam 2, ponieważ istnieją dwie prawidłowe partycje2,2,1
i2,1,1,1
.6,3
daje nam do 33,1,1,1
,3,2,1
a3,3
.Teraz możemy deterministycznie znaleźć piąty rozdział. Tutaj generujemy
p
jako liczbę losową, ale możesz nieco zmienić skrypt, więcp
jest parametr:Możemy teraz deterministycznie pokazać, że każdy wynik zależy wyłącznie od p:
Wracając do oryginału, w którym p jest generowane losowo, możemy być pewni, że każdy wynik jest jednakowo prawdopodobny.
źródło
(2,2,1)
i(2,1,1,1,1)
(ponieważ dwie wymienione na liście mają numery większe niż2
).2
. Miałem na myśli to drugie.R 198 bajtów
Nie golfowany:
Ma tę samą strukturę, co świetne rozwiązanie @ dcsohl w Octave , a zatem opiera się również na wyciągu Knuth opublikowanym przez @feersum.
Przeredaguję to później, jeśli uda mi się wymyślić bardziej kreatywne rozwiązanie w R. W międzyczasie wszelkie uwagi są oczywiście mile widziane.
źródło
Java, 392 bajty
Zadzwoń z
a(n)
. Zwraca aList
zInteger
sZębaty:
Zaadaptowano z /programming//a/2163753/4230423 i grał w golfa
Jak to działa: Możemy obliczyć, ile partycji liczby całkowitej n istnieje w czasie O ( n 2 ). Jako efekt uboczny tworzy to tabelę o rozmiarze O ( n 2 ), którą możemy następnie wykorzystać do wygenerowania k- tego podziału n dla dowolnej liczby całkowitej k , w czasie O ( n ).
Niech więc total = liczba partycji. Wybierz losową liczbę k od 0 do całości - 1. Wygeneruj k- tą partycję.
Jak zwykle sugestie są mile widziane :)
źródło
Python 2, 173 bajtów
Rekurencyjnie tworzy słownik
d
, z kluczamik
reprezentującymi parę(n,m)
wedługk=67*n+m
(przy użyciu gwarantowanejn<=65
). Wpis jest krotką liczby podziałówn
nam
części i losową taką partycją. Liczby są obliczane według rekurencyjnej formuły (dzięki feersum za wskazanie tego)f(n,m) = f(n-1,m-1) + f(n,n-m)
,a losowa partycja jest aktualizowana poprzez wybranie jednej z dwóch jej gałęzi z prawdopodobieństwem proporcjonalnym do jej liczby. Aktualizacja odbywa się przez dodanie, poprzez dodanie
1
dla pierwszego oddziału i zwiększenie każdego elementu dla drugiego.Miałem dużo problemów z wydostaniem się poza granice
m
in
zliczaniem zera. Najpierw użyłem słownika, który domyślnie ma wartość 0 i pustą listę. Tutaj używam listy i uzupełniam ją tym domyślnym wpisem. Wskaźniki ujemne powodują, że lista jest odczytywana od końca, co daje domyślny wpis, że nic nie jest blisko końca, jak do tej pory osiągnięto, a obejścia dotykają tylko regionu, w którymm>n
.źródło
Kod maszynowy 80386, 105 bajtów
Hexdump kodu:
Jako funkcja c:
void random_partition(int n, int result[]);
. Zwraca wynik jako listę liczb w dostarczonym buforze; nie oznacza w żaden sposób końca listy, ale użytkownik może odkryć koniec, kumulując liczby - lista kończy się, gdy suma jest równan
.Jak korzystać (w Visual Studio):
Przykładowe dane wyjściowe (przy n = 64):
To wymaga wielu wyjaśnień ...
Oczywiście użyłem algorytmu, którego używali wszyscy inni; nie było wyboru z wymogiem złożoności. Więc nie muszę zbytnio wyjaśniać algorytmu. Tak czy siak:
Mam
f(n, m)
na myśli liczbę podziałówn
elementów wykorzystujących części nie większe niżm
. Przechowuję je w tablicy 2-D (zadeklarowanej w C jakof[65][64]
), gdzie jest pierwszy indeksn
, a drugim-1
. Uznałem, że wsparcien=65
to zbyt duży problem, więc porzuciłem to ...Oto kod C, który oblicza tę tabelę:
Ten kod ma nieco zaciemniony styl, dzięki czemu można go łatwo przekonwertować na język asemblera. Oblicza elementy do
f(n, n)
, czyli liczby podziałówn
elementów. Po zakończeniu tego kodu zmienna tymczasowac
zawiera potrzebny numer, którego można użyć do wybrania losowego podziału na partycje:Później
index
jest on konwertowany do wymaganego formatu (listy liczb) za pomocą wygenerowanej tabeli.Ten kod jest również zoptymalizowany pod kątem konwersji na język asemblera. Istnieje mały „błąd”: jeśli partycjonowanie nie zawiera żadnej
1
liczby na końcu, ostatnia pętla napotykan = 0
i generuje niepotrzebny1
element. Nie szkodzi to jednak, ponieważ kod drukujący śledzi sumę liczby i nie drukuje tej dodatkowej liczby.Po przekonwertowaniu na zestaw wbudowany ten kod wygląda następująco:
Kilka ciekawych rzeczy do zapamiętania:
rdrand
instrukcja)ah
, co daje mi automatyczne mnożenie przez 256. Aby skorzystać z tego, poświęciłem wsparcien = 65
. Mam nadzieję, że mogę być usprawiedliwiony za ten grzech ...Przydział miejsca na stosie jest wykonywany przez odjęcie 0x4100 od rejestru wskaźnika stosu
esp
. To jest instrukcja 6-bajtowa! Dodając ponownie ten numer, udało mi się to zrobić w 5 bajtach:Podczas debugowania tej funkcji w MS Visual Studio dowiedziałem się, że ulega awarii, gdy zapisuje dane do miejsca przydzielonego na stosie! Po kilku kopaniach odkryłem pewien rodzaj ochrony przed przepełnieniem stosu: system operacyjny wydaje się przydzielać tylko bardzo ograniczony zakres adresów wirtualnych dla stosu; jeśli funkcja uzyskuje dostęp do adresu zbyt daleko, system operacyjny zakłada, że jest przekroczony i zabija program. Jeśli jednak funkcja ma wiele zmiennych lokalnych, system operacyjny wykonuje dodatkową „magię”, aby działała. Więc muszę wywołać pustą funkcję, która ma dużą tablicę przydzieloną na stosie. Po powrocie tej funkcji przydzielane są dodatkowe strony maszyn wirtualnych i można z nich korzystać.
źródło