Wprowadzenie
Zobaczmy następującą sekwencję (nieujemne liczby całkowite):
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, ...
Weźmy na przykład pierwsze trzy liczby. To są 0, 1, 2
. Liczby użyte w tej sekwencji można uporządkować na sześć różnych sposobów:
012 120
021 201
102 210
Powiedzmy, że F (3) = 6 . Innym przykładem jest F (12) . Zawiera liczby:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11
Lub konkatenowana wersja:
01234567891011
Aby znaleźć liczbę sposobów na zmianę tego, najpierw musimy spojrzeć na długość tego ciągu. Długość tego ciągu wynosi 14
. Obliczamy więc 14! . Jednak na przykład te mogą wymieniać miejsca bez zakłócania końcowego ciągu. Są 2 zera, więc są 2! sposoby na zmianę zer bez zakłócania porządku. Są też 4, więc są 4! sposoby na zmianę tych. Dzielimy sumę przez te dwie liczby:
To ma 14! / (4! × 2!) = 1816214400 sposobów na uporządkowanie ciągu 01234567891011
. Możemy zatem stwierdzić, że F (12) = 1816214400 .
Zadanie
Biorąc pod uwagę N , wyjście F (N) . Dla tych, którzy nie potrzebują wprowadzenia. Aby obliczyć F (N), najpierw konkatenujemy pierwsze N nieujemnych liczb całkowitych (np. Dla N = 12 łączący ciąg byłby 01234567891011
) i obliczamy liczbę sposobów ułożenia tego ciągu.
Przypadki testowe
Input: Output:
0 1
1 1
2 2
3 6
4 24
5 120
6 720
7 5040
8 40320
9 362880
10 3628800
11 119750400
12 1816214400
13 43589145600
14 1111523212800
15 30169915776000
Uwaga
Obliczenie odpowiedzi musi zostać obliczone w terminie 10 sekund , brutalne wymuszanie jest niedozwolone .
To jest golf golfowy , więc wygrywanie z najmniejszą ilością bajtów wygrywa!
10
prawidłowe? Wydaje się, że powinno być mniej niż 10 !, ponieważ od tego zaczynają się powtarzające się cyfry.10
cyfry to0, 1, 2, 3, 4, 5, 6, 7, 8, 9
. Dziesięć różnych cyfr, więc wynik to 10 !.0
sprawa odrzuciła moje odliczanie (głupie puste struny).F(N)
nie jestO(N!)
i żelog F(N)
jestO(log N!)
, ale to są tylko garbi ...Odpowiedzi:
Galaretka,
1715 bajtówWypróbuj online! lub zweryfikuj wszystkie przypadki testowe jednocześnie .
Jak to działa
źródło
ES6,
1188178 bajtówKtoś musi mi powiedzieć, że istnieje krótszy sposób łączenia liczb do
n
.Zaoszczędź 37 bajtów, biorąc pomysł @ edc65 i uruchamiając go na sterydach. (Zapisz dodatkowy bajt, używając „|” zamiast,
&&
ale to ogranicza wynik do 31 bitów.)Edycja: Zapisano 3 kolejne bajty dzięki @ edc65.
źródło
reduce
:n=>[...[...Array(n).keys()].join``].reduce((r,c,i)=>r*++i/(o[c]=-~o[c]),1,o=[])
n=>[...[...Array(n).keys()].join``].map(c=>r/=(o[c]=-~o[c])/i++,o=[],i=r=1)&&r
r/=(...)/i++
jest dokładniejszy niżr*=i++/(...)
? To najbardziej absurdalny golf, jaki kiedykolwiek widziałem!APL (Dyalog Extended) , 13 bajtów
Wypróbuj online!
Pełny program. Zastosowania
⎕IO←0
.Jak to działa
Obliczenia wielomianowe pochodzą z następującego faktu:
źródło
MATL , 21 bajtów
Wypróbuj online!
Wyjaśnienie
źródło
Python 2,
14213710197 bajtów(Dzięki @adnan za sugestię dotyczącą
input
)(Zastosował obliczenia przyrostowe z wersji C )
Oryginalna wersja wykorzystująca silnię
Naprawdę, jedyne w golfa powyżej to sprawdzanie
math.factorial
F
sprawdzanie i pomijanie niektórych spacji, więc prawdopodobnie istnieje krótsze rozwiązanie python.Jeśli potrzebne jest wyjaśnienie,
v
utrzymuje liczbę częstotliwości każdej cyfry; liczba jest aktualizowana dla każdej cyfry w każdej liczbie we wskazanym zakresie.W oryginalnej wersji obliczamy liczbę permutacji przy użyciu standardowej formuły (if i )! / Π (f i !). W przypadku bieżącej wersji obliczenia te są wykonywane przyrostowo poprzez dystrybucję mnożników i podziałów, tak jak widzimy cyfry. To może nie być oczywiste, że podział całkowitą zawsze będzie dokładny, ale jest to łatwe do udowodnienia, opiera się na obserwacji, że każdy podział przez
k
muszą przestrzegaćk
mnożeniu kolejnych liczb całkowitych, więc jeden z tych mnożeń musi być podzielny przezk
. (To intuicja, a nie dowód.)Oryginalna wersja jest szybsza dla dużych argumentów, ponieważ dzieli tylko 10 bignum. Chociaż dzielenie bignum przez małą liczbę całkowitą jest szybsze niż dzielenie bignum przez bignum, gdy masz tysiące podziałów bignum, robi się nieco powolny.
źródło
Python 2, 197 Bytes (edycja: zapisano 4 bajty, dzięki Thomas Kwa!)
Nie golfowany:
źródło
range(0,10)
może byćrange(10)
.CJam,
2119 bajtówSprawdź to tutaj.
Wyjaśnienie
źródło
JavaScript (ES6), 100
Test
źródło
k[c]=~-k[c]
synonimem--k[c]
?Pyth, 18 bajtów
Wypróbuj online: demonstracja
źródło
Haskell, 92 bajty
Przykład użycia:
h 12
->1816214400
.Jak to działa
źródło
C
236174138121 121 bajtówOgromne uznanie dla rici za ogromną redukcję bajtów.
Nie golfił
Wypróbuj tutaj .
źródło
#define L long long L d;i,j,k,m,n,s=1,b[10]={1};L f(n){return n?n*f(n-1):1;}main(d){for(scanf("%d",&n);i<n;)for(j=i++;j;j/=10)++b[j%10],++s;for(;m<10;)d*=f(b[m++]);printf("%Ld",f(s)/d);}
for(;m<10;)s+=b[m],d*=f(b[m++])
ale myślę, że to jeszcze kilka bajtów.C / bc,
233121112 bajtów (zakładając karę za 3 bajty|bc
)Zainspirowany przez Cole'a Camerona, usunął zuchwałe manipulacje postaciami i po prostu wykonał arytmetykę wartości argumentu.
Zmieniono na scanf z używania wektora arg.
Wymagania
bc
faktycznie wykonać dowolne obliczenie precyzji.Bez golfa i bez ostrzeżenia:
Ilustrowany (który ufam pokazuje algorytm):
A wraz z potokiem przechodzącym przez bc (i dodając obliczenia F (1000):
Ten wyliczony F (5000) - liczba 18 592 cyfr - w mniej niż 10 sekund.
źródło
Perl 6, 117 bajtów
i w bardziej czytelnej fascynacji
źródło
Perl 5, 108 bajtów
Ogromne podziękowania dla dev-null za uratowanie mi 17 bajtów i za sprytny pomysł na czynnik.
źródło
05AB1E ,
131211 bajtówWypróbuj online!
źródło
Python 2 , 123 bajty
Wypróbuj online!
range
wejściowe na pojedynczy ciągźródło
PowerShell, 125 bajtów
Pobiera dane wejściowe
$args[0]
, odejmuje1
, buduje zakres liczb całkowitych z0..
tej liczby,-join
które razem tworzą ciąg i zapisuje jako$b
. Bierzemy.Length
ten ciąg, budujemy kolejny zakres z1..
tej długości,-join
te liczby całkowite razem*
, a następnie potokujemy to doInvoke-Expression
(podobnie jakeval
). Innymi słowy, skonstruowaliśmy silnię długości sekwencji liczb na podstawie danych wejściowych. To jest nasz licznik.Dzielimy to
/
przez ...Nasz mianownik, który jest konstruowany przez pomiar zasięgu
0..9
i wysyłanie go przez pętlę for|%{...}
. Każda iteracja, ustawiamy zmienną pomocnik$c
równa liczbie razy prąd cyfra$_
pojawia się wewnątrz$b
dzięki .NET[regex]::matches
rozmowy w połączeniu z.count
atrybutem. Następnie konstruujemy nowy zakres od1..
tej wartości, o ile jest ona niezerowa. Tak, w wielu przypadkach spowoduje to zasięg1..1
, który zostanie oceniony na just1
. Bierzemy wszystkie i-join
je wszystkie razem*
, a potemInvoke-Expression
ponownie przesyłamy. Innymi słowy, skonstruowaliśmy iloczyn silni liczby wystąpień każdej cyfry.NB
Obsługuje dane wejściowe do
90
bez problemu i znacznie krócej niż sekundę.... poza tym daje
Infinity
jako wynik, ponieważ długość dopuszczalnego ciągu powoduje, że170!
pasuje dodouble
typu danych (7.25741561530799E+306
), ale171!
nie. PowerShell ma ... dziwactwo ... które automatycznie przesyła w górę od[int]
do[double]
w przypadku przepełnienia (pod warunkiem, że nie rzuciłeś jawnie zmiennej na początek). Nie, nie wiem, dlaczego nie chodzi[long]
o wartości całkowite.Gdybyśmy dokonali jawnego rzutowania i manipulacji (np. Przy użyciu
[uint64]
, dla liczb całkowitych bez znaku 64-bitowych), moglibyśmy uzyskać wyższą wartość, ale znacznie zwiększyłoby to rozmiar kodu, ponieważ musielibyśmy osiągnąć zasięg do 170-długości z warunkami warunkowymi, a następnie przekształcić od tego momentu każde pomnożenie. Ponieważ wyzwanie nie określa górnego zakresu, zakładam, że jest to wystarczające.źródło
Perl6
W tej chwili raczej nie golfisty - potrzebuję teraz snu.
źródło
Groovy, 156 bajtów
Moje pierwsze skromne rozwiązanie Code Golf. Możesz to przetestować tutaj.
A oto bardziej czytelna wersja:
Całkiem proste, ale było dla mnie kilka najważniejszych rzeczy:
Wykonanie iniekcji / redukcji z tablicy
chars
doMap<Character, Integer>
. Wciąż było to nieco skomplikowane z powodu braku domyślnej wartości dla wartości mapy. Wątpliwość jest to możliwe, ale jeśli mapa domyślnie wyzeruje wszystkie wartości na 0, mógłbym uniknąć trójskładnika, który jest konieczny, aby uniknąć NPE.Operator rozkładania Groovy (np.
}*.value
) Jest zawsze przyjemny w użyciuNa irytującą cechą była jednak konieczność zadeklarowania funkcji silni z typem zwracanym
BigInteger
. Miałem wrażenie, że Groovy zawarł wszystkie cyfry wBigInteger
lubBigDecimal
, ale może nie być tak w przypadku typów zwracanych. Będę musiał więcej eksperymentować. Bez tego typu zwrotu wyraźnie otrzymujemy niepoprawne wartości silni.źródło
J, 33 bajty
Konwertuje zakres na ciąg cyfr, liczy każdą cyfrę i stosuje współczynnik wielomianowy do obliczenia wyniku.
Stosowanie
źródło
R, 118 bajtów
Około 8 miesięcy spóźnienia na imprezę, ale pomyślałem, że spróbuję, bo wyglądało to na ciekawe wyzwanie.
Wypróbuj na skrzypcach R.
Wyjaśniono
0 ... n-1
i zwiń go do ciągu:paste(1:n-1,collapse="")
x
):x=as.numeric(el(strsplit(...,"")))
factorial(sum(1|x))
to, co jest sprawiedliwe#digits!
Aby obliczyć mianownik, używamy
table
do zbudowania tabeli awaryjnej, która zawiera częstotliwości. W przypadku F (12) wygenerowana tabela to:Co oznacza, że możemy skorzystać z użycia
factorial()
(które przy okazji jest wektoryzowane) na licznik i po prostu wziąć produkt:prod(factorial(table(x)))
Uwaga: kroki 4 i 5 są przeprowadzane tylko wtedy, gdy
n>0
wrócą inaczej1
.źródło
Mathematica, 65 bajtów
Prawdopodobnie można by dalej grać w golfa.
źródło
Rubinowy , 64 bajty
Wypróbuj online!
źródło
Stax , 12 bajtów
Uruchom i debuguj na staxlang.xyz!
Rozpakowane (14 bajtów) i objaśnienie:
źródło
Galaretka , 11 bajtów
15-bajtowa odpowiedź Jelly na golfa Dennisa ...
Monadyczny link akceptujący nieujemną liczbę całkowitą, która daje dodatnią liczbę całkowitą.
Wypróbuj online! Lub zobacz pakiet testowy .
W jaki sposób?
źródło
Python 2 , 190 bajtów
Wypróbuj online!
źródło
Python 2 , 134 bajty
Wypróbuj online!
Alternatywne podejście ...
źródło