Zmiana kolejności sekwencji

23

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 , więc wygrywanie z najmniejszą ilością bajtów wygrywa!

Adnan
źródło
Czy dane wyjściowe są 10prawidłowe? Wydaje się, że powinno być mniej niż 10 !, ponieważ od tego zaczynają się powtarzające się cyfry.
Geobits
@Geobits Pierwsze 10cyfry to 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Dziesięć różnych cyfr, więc wynik to 10 !.
Adnan
Ah, tak. Myślę, że 0sprawa odrzuciła moje odliczanie (głupie puste struny).
Geobits
1
Nie musisz się już o to martwić. Propozycja luki była na +4, kiedy opublikowałem komentarz. Jest teraz na +9 .
Dennis
1
Oto interesujące pytanie matematyczne dotyczące tej układanki: Jaka jest wartość F (N) w stosunku do N !? Istnieje wiele wartości N, dla których F (N) / F (N-1) <N, ale zwykle jest nieco większa. Jestem pewien, że F(N)nie jest O(N!)i że log F(N)jest O(log N!), ale to są tylko garbi ...
Rici

Odpowiedzi:

5

Galaretka, 17 15 bajtów

R’DFµ=€QS;@L!:/

Wypróbuj online! lub zweryfikuj wszystkie przypadki testowe jednocześnie .

Jak to działa

R’DFµ=€QS;@L!:/    Main link. Input: n

R                  Yield [1, ..., n] for n > 0 or [0] for n = 0.
 ’                 Decrement. Yields [0, ..., n - 1] or [-1].
  D                Convert each integer into the list of its decimal digits.
   F               Flatten the resulting list of lists.
    µ              Begin a new, monadic chain. Argument: A (list of digits)
       Q           Obtain the unique elements of A.
     =€            Compare each element of A with the result of Q.
                   For example, 1,2,1 =€ Q -> 1,2,1 =€ 1,2
                                           -> [[1, 0], [0, 1], [1, 0]]
        S          Sum across columns.
                   This yields the occurrences of each unique digit.
         ;@L       Prepend the length of A.
            !      Apply factorial to each.
             :/    Reduce by divison.
                   This divides the first factorial by all remaining ones.
Dennis
źródło
Czy to naprawdę galaretka? Widzę wiele postaci ASCII :-P
Luis Mendo
3
Zawsze udaje im się jakoś podkraść ...
Dennis
10

ES6, 118 81 78 bajtów

n=>[...[...Array(n).keys()].join``].map(c=>r/=(o[c]=-~o[c])/i++,o=[],i=r=1)&&r

Ktoś 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.

Neil
źródło
Nie znalazłem sposobu na skrócenie konkatenacji cyfr. Ale cała reszta może być krótsza
edc65
Zaoszczędź 2 bajty za pomocą reduce:n=>[...[...Array(n).keys()].join``].reduce((r,c,i)=>r*++i/(o[c]=-~o[c]),1,o=[])
user81655
1
Łał! ale 78 jest lepsze:n=>[...[...Array(n).keys()].join``].map(c=>r/=(o[c]=-~o[c])/i++,o=[],i=r=1)&&r
edc65
1
@ edc65 r/=(...)/i++jest dokładniejszy niż r*=i++/(...)? To najbardziej absurdalny golf, jaki kiedykolwiek widziałem!
Neil
2
Musiałem zatrzymać się na chwilę, ponieważ myślałem, że masz tam wyrażenie regularne.
Mama Fun Roll
7

APL (Dyalog Extended) , 13 bajtów

×/2!/+\⎕D⍧⍕⍳⎕

Wypróbuj online!

Pełny program. Zastosowania ⎕IO←0.

Jak to działa

×/2!/+\⎕D⍧⍕⍳⎕
               Take input from stdin (N)
               Generate range 0..N-1
               Stringify the entire array (S)
                (The result has spaces between items)
       D       The character array '0123456789'
               Count occurrences of each digit in S
×/2!/+\         Calculate multinomial:
     +\           Cumulative sum
  2!/             Binomial of consecutive pairs
×/                Product

Obliczenia wielomianowe pochodzą z następującego faktu:

(a1+a2++an)!a1!a2!an!=(a1+a2)!a1!a2!×(a1+a2++an)!(a1+a2)!a3!an!

=(a1+a2)!a1!a2!×(a1+a2+a3)!(a1+a2)!a3!×(a1+a2++an)!(a1+a2+a3)!an!

==(za1+za2)za1)(za1+za2)+za3)za1+za2))(za1++zanza1++zan-1)

Bubbler
źródło
1
I dlatego programiści powinni uczyć się matematyki.
Anonimowy
@Anonimowy… i używaj matematycznie skłonnego języka programowania.
Adám
5

MATL , 21 bajtów

:qV0h!4Y2=sts:pw"@:p/

Wypróbuj online!

Wyjaśnienie

:q     % implicitly input N, and generate vector [0, 1, ..., N-1]
V      % convert to string representation of numbers. Contains spaces,
       % but no matter. Only characters '0', ..., '9' will be counted
0h     % append 0 character (not '0'), so that string is never empty
!      % convert string to column char array
4Y2    % string '0123456789' (row char array)
=      % test all pairs for equality
s      % sum each column. For N = 12 this gives [2, 4, 1, 1, ..., 1]
t      % duplicate
s      % compute sum. For N = 12 this gives 14
:p     % factorial
w      % swap. Now vector [2, 4, 1, 1, ..., 1] is on top
"      % for each number in that vector
  @:p  %   factorial
  /    %   divide
       % implicitly end loop
       % implicitly display
Luis Mendo
źródło
@Adnan Solved. I z mniejszą liczbą bajtów :-)
Luis Mendo
Wygląda bardzo ładnie! :)
Adnan
@Adnan Thanks! Dodałem wyjaśnienie
Luis Mendo
5

Python 2, 142 137 101 97 bajtów

(Dzięki @adnan za sugestię dotyczącą input )

(Zastosował obliczenia przyrostowe z wersji C )

f=1;v=10*[0]
for i in range(input()):
 for h in str(i):k=int(h);v[k]+=1;f=f*sum(v)/v[k]
print f

Oryginalna wersja wykorzystująca silnię

import math
F=math.factorial
v=10*[0]
for i in range(input()):
 for h in str(i):v[int(h)]+=1
print reduce(lambda a,x:a/F(x),v,F(sum(v)))

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 kmuszą 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.

rici
źródło
f = f * suma (v) / v [k] -> f * = suma (v) / v [k] zapisuje bajt
Mikko Virkkilä
@ superflux: ale to nie to samo znaczenie.
rici
5

Python 2, 197 Bytes (edycja: zapisano 4 bajty, dzięki Thomas Kwa!)

import math
l,g,f,p,r,s=[],[],math.factorial,1,range,str
for x in r(int(input())):l.append(s(x))
l="".join(l)
for y in r(10):b=s(l).count(s(y));g.append(f(b));
for c in g:p*=y
print f(int(len(l)))/p

Nie golfowany:

import math

l=[] #list of the numbers from 0 to n
exchange_list=[] #numbers that can be exchanged with each other, ie      repeats

multiplied = 1 #for multiplying the digits by each other
n = int(input())

for x in range(n): #put all the numbers from 0-n into the list
    l.append(str(x))

l = "".join(l) #put all the digits in a string to remove repeats

for x in range(10): #look at all the digits and check how many are in the     list/string
    count = str(l).count(str(x))
    if count > 1: #if there is more than 1 of the digit, put the factorial of the amount of - 
        exchange_list.append(math.factorial(count)) # - appearances into the exchange list.

for x in exchange_list: #multiply all the values in the list by each other
    multiplied*=x

print math.factorial(int(len(l)))/multiplied #print the factorial of the  length of the string 
#divided by the exchanges multiplied
Dave Lin
źródło
1
Witamy w Programowaniu zagadek i Code Golf! Podejrzewam, że ta odpowiedź została oznaczona jako VLQ (bardzo niska jakość), ponieważ nie zawiera żadnych wyjaśnień ani wersji bez golfa, które są tutaj normą. Zakładając, że twoja odpowiedź działa i poprawisz ją z bycia „tylko kodem”, wydaje się całkiem dobra!
kot
range(0,10)może być range(10).
lirtosiast
4

CJam, 21 19 bajtów

ri,s_,A,s@fe=+:m!:/

Sprawdź to tutaj.

Wyjaśnienie

ri   e# Read input and convert to integer N.
,    e# Get a range [0 1 ... N-1].
s    e# Convert to string, flattening the range.
_,   e# Duplicate and get its length.
A,s  e# Push "012345789".
@fe= e# Pull up the other copy of the string and count the occurrences of each digit.
+    e# Prepend the string length.
:m!  e# Compute the factorial of each of them.
:/   e# Fold division over the list, dividing the factorial of the length by all the other
     e# factorials.
Martin Ender
źródło
3

JavaScript (ES6), 100

n=>(f=[...[...Array(n).keys()].join``].map(c=>(k[c]=~-k[c],p*=i++),i=p=1,k=[]),k.map(v=>p/=f[~v]),p)

Test

F=n=>(f=[...[...Array(n).keys()].join``].map(c=>(k[c]=~-k[c],p*=i++),i=p=1,k=[]),k.map((v,i)=>p/=f[~v]),p)

// Less golfed
U=n=>( // STEP 1, count digits, compute factorials
      f= // will contain the value of factorials 1 to len of digits string
      [...[...Array(n).keys()].join``] // array of cancatenated digits
      .map(c=> // execute the following for each digit
           (
            k[c]=~-k[c], // put in k[c] the repeat count for digit c, negated 
            p*=i++       // evaluate factorial, will be stored in f
           ),i=p=1,k=[]),// initialisations
       // at the end of step 1 we have all factorials if f and max factorial in p
       // STEP 2, divide the result taking into account the repeated digits
      k.map(v=>p/=f[~v]), // for each digit, divide p by the right factorial (~v === -v-1)
  p // return result in p
) 

// Test
console.log=x=>O.textContent+=x+'\n'

for(j=0;j<=15;j++) console.log(j+' '+F(j))
<pre id=O></pre>

edc65
źródło
Nie jest k[c]=~-k[c]synonimem --k[c]?
usandfriends
1
@usandfriends nie, gdy k [c] jest niezdefiniowany - k [c] to NaN
edc65
Och, niezła tablica silni.
Neil
... chociaż tego nie potrzebujesz. Zobacz moją najnowszą aktualizację.
Neil
3

Pyth, 18 bajtów

/F.!M+lJ.njRTQ/LJT

Wypróbuj online: demonstracja

/F.!M+lJ.njRTQ/LJT   implicit: Q = input number
          jRTQ       convert each number in [0, ..., Q-1] to their digits
        .n           flatten to a single list
       J             store this list in J
              /LJT   for each digit count the number of appearances in J
     +lJ             prepend the length of J
  .!M                compute the factorial for each number
/F                   fold by division
Jakube
źródło
3

Haskell, 92 bajty

import Data.List
h n|l<-sort$show=<<[0..n-1]=foldl1 div$product.map fst.zip[1..]<$>l:group l

Przykład użycia: h 12->1816214400 .

Jak to działa

l<-sort$show=<<[0..n-1]       -- bind l to the sorted concatenated string
                              -- representations of the numbers from 0 to n-1
                              -- e.g. n=12 -> "00111123456789"

               l: group l     -- group the chars in l and put l itself in front
                              -- e.g. ["00111123456789","00","1111","2",..."9"]
            <$>               -- map over this list
    product.map fst.zip[1..]  -- the faculty the length of the sublist (see below)  
                              -- e.g. [87178291200,2,24,1,1,1,..,1]
foldl1 div                    -- fold integer division from the left into this list
                              -- e.g. 87178291200 / 2 / 24 / 1

                              -- Faculty of the length of a list:
                  zip[1..]    -- make pairs with the natural numbers
                              -- e.g. "1111" -> [(1,'1'),(2,'1'),(3,'1'),(4,'1')]
          map fst             -- drop 2nd element form the pairs
                              -- e.g. [1,2,3,4]
  product                     -- calculate product of the list
nimi
źródło
3

C 236 174 138 121 121 bajtów

Ogromne uznanie dla rici za ogromną redukcję bajtów.

long long d,f=1;j,s=1,n,b[10]={1};main(d){for(scanf("%d",&n);n--;)for(j=n;j;j/=10,f*=++s)d*=++b[j%10];printf("%Ld",f/d);}

Nie golfił

long long d,f=1;
j,s=1,n,b[10]={1};

main(d)
{
    scanf("%d",&n); /* get input */
    for(;n--;) /* iterate through numbers... */
        for(j=n;j;j/=10,f*=++s) /* iterate through digits, sum up and factorial */
            d*=++b[j%10]; /* count and factorial duplicates */
    printf("%Ld",f/d); /* print out result */
}

Wypróbuj tutaj .

Cole Cameron
źródło
1
Możesz uratować 43 znaki, nie chowając się przy opcji -lm. Po prostu policz cyfry, jak je znajdziesz:#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);}
rici
Możesz także policzyć je w pętli, w której obliczasz d: for(;m<10;)s+=b[m],d*=f(b[m++])ale myślę, że to jeszcze kilka bajtów.
rici
To wspaniale. Połączę się z moimi obecnymi wysiłkami golfowymi i edytuję.
Cole Cameron,
Fajnie: spójrz na mój, aby zobaczyć, jak zintegrować obliczenia czynnikowe w oryginalnej pętli, co ma tę zaletę, że działa na nieco większym zakresie, jeśli nie masz arytmetyki o dowolnej precyzji. Myślę, że to kolejne 20 bajtów do golenia.
rici
3

C / bc, 233 121 112 bajtów (zakładając karę za 3 bajty |bc)

  1. Zainspirowany przez Cole'a Camerona, usunął zuchwałe manipulacje postaciami i po prostu wykonał arytmetykę wartości argumentu.

  2. Zmieniono na scanf z używania wektora arg.

    C[10]={1},n=1,k,t;main(){for(scanf("%d",&k);k--;)for(t=k;t;t/=10)printf("%d/%d*",++n,++C[t%10]);puts("1");}
    

Wymagania bc faktycznie wykonać dowolne obliczenie precyzji.

Bez golfa i bez ostrzeżenia:

#include <stdio.h>
int main() {
  int C[10]={1},n=1,k,t;    /* 0 is special-cased */
  for(scanf("%d",&k);k--;)  /* For each integer less than k */
    for(int t=k;t;t/=10)    /* For each digit in t */
      printf("%d/%d*",++n,++C[t%10]);  /* Incremental choice computation */
  puts("1");                /* Finish the expression */
}

Ilustrowany (który ufam pokazuje algorytm):

$ for i in {0..15} 100 ; do printf %4d\  $i;./cg70892g<<<$i;done
   0 1
   1 1
   2 2/1*1
   3 2/1*3/1*1
   4 2/1*3/1*4/1*1
   5 2/1*3/1*4/1*5/1*1
   6 2/1*3/1*4/1*5/1*6/1*1
   7 2/1*3/1*4/1*5/1*6/1*7/1*1
   8 2/1*3/1*4/1*5/1*6/1*7/1*8/1*1
   9 2/1*3/1*4/1*5/1*6/1*7/1*8/1*9/1*1
  10 2/1*3/1*4/1*5/1*6/1*7/1*8/1*9/1*10/1*1
  11 2/1*3/2*4/1*5/1*6/1*7/1*8/1*9/1*10/1*11/1*12/2*1
  12 2/1*3/2*4/3*5/2*6/1*7/1*8/1*9/1*10/1*11/1*12/1*13/1*14/4*1
  13 2/1*3/1*4/2*5/3*6/4*7/2*8/1*9/1*10/1*11/1*12/1*13/1*14/1*15/2*16/5*1
  14 2/1*3/1*4/2*5/1*6/3*7/4*8/5*9/2*10/1*11/1*12/1*13/1*14/1*15/1*16/2*17/2*18/6*1
  15 2/1*3/1*4/2*5/1*6/3*7/1*8/4*9/5*10/6*11/2*12/1*13/1*14/1*15/1*16/1*17/2*18/2*19/2*20/7*1
 100 2/1*3/2*4/3*5/1*6/4*7/1*8/5*9/1*10/6*11/1*12/7*13/1*14/8*15/1*16/9*17/1*18/10*19/1*20/11*21/2*22/2*23/12*24/3*25/4*26/5*27/2*28/6*29/2*30/7*31/2*32/8*33/2*34/9*35/2*36/10*37/2*38/11*39/2*40/12*41/3*42/3*43/13*44/4*45/13*46/5*47/6*48/7*49/3*50/8*51/3*52/9*53/3*54/10*55/3*56/11*57/3*58/12*59/3*60/13*61/4*62/4*63/14*64/5*65/14*66/6*67/14*68/7*69/8*70/9*71/4*72/10*73/4*74/11*75/4*76/12*77/4*78/13*79/4*80/14*81/5*82/5*83/15*84/6*85/15*86/7*87/15*88/8*89/15*90/9*91/10*92/11*93/5*94/12*95/5*96/13*97/5*98/14*99/5*100/15*101/6*102/6*103/16*104/7*105/16*106/8*107/16*108/9*109/16*110/10*111/16*112/11*113/12*114/13*115/6*116/14*117/6*118/15*119/6*120/16*121/7*122/7*123/17*124/8*125/17*126/9*127/17*128/10*129/17*130/11*131/17*132/12*133/17*134/13*135/14*136/15*137/7*138/16*139/7*140/17*141/8*142/8*143/18*144/9*145/18*146/10*147/18*148/11*149/18*150/12*151/18*152/13*153/18*154/14*155/18*156/15*157/16*158/17*159/8*160/18*161/9*162/9*163/19*164/10*165/19*166/11*167/19*168/12*169/19*170/13*171/19*172/14*173/19*174/15*175/19*176/16*177/19*178/17*179/18*180/19*181/10*182/20*183/20*184/20*185/20*186/20*187/20*188/20*189/20*190/20*1

A wraz z potokiem przechodzącym przez bc (i dodając obliczenia F (1000):

$ time for i in {0..15} 100 1000; do printf "%4d " $i;./cg70892g<<<$i|bc;done
   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
 100 89331628085599251432057142025907698637261121628839475101631496666431\
15835656928284205265561741805657733401084399630568002336920697364324\
98970890135552420133438596044287494400000000
1000 45200893173828954313462564749564394748293201305047605660842814405721\
30092686078003307269244907986874394907789568742409099103180981532605\
76231293886961761709984429587680151617686667512237878219659252822955\
55855915137324368886659115209005785474446635212359968384367827713791\
69355041534558858979596889046036904489098979549000982849236697235269\
84664448178907805505235469406005706911668121136625035542732996808166\
71752374116504390483133390439301402722573240794966940354106575288336\
39766175522867371509169655132556575711715087379432371430586196966835\
43089966265752333684689143889508566769950374797319794056104571082582\
53644590587856607528082987941397113655371589938050447115717559753757\
79446152023767716192400610266474748572681254153493484293955143895453\
81280908664541776100187003079567924365036116757255349569574010994259\
42252682660514007543791061446917037576087844330206560326832409035999\
90672829766080114799705907407587600120545365651997858351981479835689\
62520355320273524791310387643586826781881487448984068291616884371091\
27306575532308329716263827084514072165421099632713760304738427510918\
71188533274405854336233290053390700237606793599783757546507331350892\
88552594944038125624374807070741486495868374775574664206439929587630\
93667017165594552704187212379733964347029984154761167646334095514093\
41014074159155080290000223139198934433986437329522583470244030479680\
80866686589020270883335109556978058400711868633837851169536982150682\
22082858700246313728903459417761162785473029666917398283159071647546\
25844593629926674983035063831472139097788160483618679674924756797415\
01543820568689780263752397467403353950193326283322603869951030951143\
12095550653333416019778941123095611302340896001090093514839997456409\
66516109033654275890898159131736630979339211437991724524614375616264\
98121300206207564613016310794402755159986115141240217861695468584757\
07607748055900145922743960221362021598547253896628914921068009536934\
53398462709898222067305585598129104976359039062330308062337203828230\
98091897165418693363718603034176658552809115848560316073473467386230\
73804128409097707239681863089355678037027073808304307450440838875460\
15170489461680451649825579772944318869172793737462142676823872348291\
29912605105826175323042543434860948610529385778083808434502476018689\
05150440954486767102167489188484011917026321182516566110873814183716\
30563399848922002627453188732598763510259863554716922484424965400444\
85477201353937599094224594031100637903407963255597853004241634993708\
88946719656130076918366596377038503741692563720593324564994191848547\
42253991635763101712362557282161765775758580627861922528934708371322\
38741942406807912441719473787691540334781785897367428903185049347013\
44010772740694376407991152539070804262207515449370191345071234566501\
33117923283207435702471401696679650483057129117719401161591349048379\
16542686360084412816741479754504459158308795445295721744444794851033\
08800000000

real    0m0.246s
user    0m0.213s
sys     0m0.055s

Ten wyliczony F (5000) - liczba 18 592 cyfr - w mniej niż 10 sekund.

$ time ./cg70892g3<<<5000|BC_LINE_LENGTH=0 bc|wc -c
18593

real    0m9.274s
user    0m9.273s
sys     0m0.005s
rici
źródło
3

Perl 6, 117 bajtów

say $_ <2??1!!permutations(+[(my@n=^$_ .join.comb)]).elems÷[*] ([*] 2..$_ for @n.classify(&unique).values)for lines

i w bardziej czytelnej fascynacji

for (lines) -> $number {
    say 1 and next if $number < 2;
    my @digits = (^$number).join.comb;
    my @duplicates = @digits.classify(&unique).values;
    my $unique_permutations = permutations(+@digits).elems ÷ [*] ([*] 2..$_ for @duplicates);
    say $unique_permutations;
}
Jozuego
źródło
3

Perl 5, 108 bajtów

sub f{eval join"*",@_,1}push@a,/./g for 0..<>-1;for$i(0..9){$b[$i]=grep/$i/,@a}say f(1..@a)/f map{f 1..$_}@b

Ogromne podziękowania dla dev-null za uratowanie mi 17 bajtów i za sprytny pomysł na czynnik.

msh210
źródło
3

05AB1E , 13 12 11 bajtów

ÝD¨SāPr¢!P÷

Wypróbuj online!

Ý             # range [0..input]
 D            # duplicate
  ¨           # drop the last element
   S          # split into digits
    ā         # length range: [1..number of digits]
     P        # product (effectively a factorial)
      r       # reverse the stack
       ¢      # count occurences of each number in the list of digits
        !     # factorial of each count
         P    # product of those
          ÷   # divide the initial factorial by this product
Ponury
źródło
3

Python 2 , 123 bajty

import math
i,b,F="".join(map(str,range(input()))),1,math.factorial
for x in range(10):b*=F(i.count(`x`))
print F(len(i))/b

Wypróbuj online!

  1. Konwertuj range wejściowe na pojedynczy ciąg
  2. Sprawdź, ile razy każda z liczb od 0 do 9 pojawia się w ciągu i uzyskaj silnię dla każdego z nich, a następnie pomnóż je razem
  3. Podziel silnię długości łańcucha przez liczbę obliczoną w kroku 2
ElPedro
źródło
2

PowerShell, 125 bajtów

(1..(($b=0..($args[0]-1)-join'').Length)-join'*'|iex)/((0..9|%{$c=[regex]::Matches($b,$_).count;1..($c,1)[!$c]})-join'*'|iex)

Pobiera dane wejściowe $args[0], odejmuje 1, buduje zakres liczb całkowitych z 0..tej liczby, -joinktóre razem tworzą ciąg i zapisuje jako $b. Bierzemy .Lengthten ciąg, budujemy kolejny zakres z 1..tej długości, -jointe 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..9i wysyłanie go przez pętlę for |%{...}. Każda iteracja, ustawiamy zmienną pomocnik $crówna liczbie razy prąd cyfra $_pojawia się wewnątrz $bdzięki .NET [regex]::matchesrozmowy w połączeniu z .countatrybutem. Następnie konstruujemy nowy zakres od 1..tej wartości, o ile jest ona niezerowa. Tak, w wielu przypadkach spowoduje to zasięg 1..1, który zostanie oceniony na just 1. Bierzemy wszystkie i-join je wszystkie razem *, a potem Invoke-Expressionponownie 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ę.

PS C:\Tools\Scripts\golfing> .\rearranging-the-sequence.ps1 90
1.14947348910454E+159

PS C:\Tools\Scripts\golfing> Measure-Command {.\rearranging-the-sequence.ps1 90} | FL TotalMilliseconds
TotalMilliseconds : 282.587

... poza tym daje Infinityjako wynik, ponieważ długość dopuszczalnego ciągu powoduje, że 170!pasuje do doubletypu danych ( 7.25741561530799E+306), ale 171!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.

AdmBorkBork
źródło
2

Perl6

perl6 -e 'sub p ($a) { my $x = $a.join.comb.classify(+*).values.map(*.elems).classify(+*).values.flatmap(*.list).flatmap((2..+*).list); my $y = 2..$a[*-1]; [/] $x.list * [*] $y.list }; p([1..11]).say'

W tej chwili raczej nie golfisty - potrzebuję teraz snu.

użytkownik52889
źródło
2

Groovy, 156 bajtów

def f(n){def s=(0..n-1).join('')
0==n?1:g(s.size())/s.inject([:]){a,i->a[i]=a[i]?a[i]+1:1;a}*.value.inject(1){a,i->a*g(i)}}
BigInteger g(n){n<=1?1:n*g(n-1)}

Moje pierwsze skromne rozwiązanie Code Golf. Możesz to przetestować tutaj.

A oto bardziej czytelna wersja:

def f(n) {
  def s = (0..n - 1).join('')                       // Store our concatented range, s
  0 == n ? 1 :                                      // Handle annoying case where n = 0
    fact(s.size()) / s.inject([:]) {                // Divide s.size()! by the product of the values we calculate by...
      a, i ->                                       // ...reducing into a map...
        a[i] = a[i] ? a[i] + 1 : 1                  // ...the frequency of each digit
        a                                           // Our Groovy return statement
    }*.value.inject(1) { a, i -> a * fact(i) }      // Finally, take the product of the factorial of each frequency value
}

BigInteger fact(n) { n <= 1 ? 1 : n * fact(n - 1) } // No built-in factorial function...

Całkiem proste, ale było dla mnie kilka najważniejszych rzeczy:

  • Wykonanie iniekcji / redukcji z tablicy charsdo Map<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życiu

Na irytującą cechą była jednak konieczność zadeklarowania funkcji silni z typem zwracanym BigInteger. Miałem wrażenie, że Groovy zawarł wszystkie cyfry w BigIntegerlub BigDecimal, 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.

Zelandia
źródło
2

J, 33 bajty

(#(%*/)&:!&x:#/.~)@([:;<@":"0)@i.

Konwertuje zakres na ciąg cyfr, liczy każdą cyfrę i stosuje współczynnik wielomianowy do obliczenia wyniku.

Stosowanie

   f =: (#(%*/)&:!&x:#/.~)@([:;<@":"0)@i.
   (,.f"0) i. 16
 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
mile
źródło
2

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.

function(n,x=as.numeric(el(strsplit(paste(1:n-1,collapse=""),""))),F=factorial)`if`(n,F(sum(1|x))/prod(F(table(x))),1)

Wypróbuj na skrzypcach R.

Wyjaśniono

  1. Wygeneruj wektor 0 ... n-1i zwiń go do ciągu:paste(1:n-1,collapse="")
  2. Podziel ciąg na cyfry i przekonwertuj na numeryczny (zapisz jako x):x=as.numeric(el(strsplit(...,"")))
  3. Aby obliczyć licznik, po prostu robimy factorial(sum(1|x))to, co jest sprawiedliwe#digits!
  4. Aby obliczyć mianownik, używamy tabledo zbudowania tabeli awaryjnej, która zawiera częstotliwości. W przypadku F (12) wygenerowana tabela to:

    0 1 2 3 4 5 6 7 8 9 
    2 4 1 1 1 1 1 1 1 1 
    
  5. 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>0wrócą inaczej 1.

Billywob
źródło
1

Mathematica, 65 bajtów

(Tr@IntegerLength[a=Range@#-1]+1)!/Times@@(Total[DigitCount@a]!)&

Prawdopodobnie można by dalej grać w golfa.

LegionMammal978
źródło
1

Stax , 12 bajtów

éÄ\↑≈g→FP○░→

Uruchom i debuguj na staxlang.xyz!

Rozpakowane (14 bajtów) i objaśnienie:

r$c%|Fso:GF|F/
r                 Range [0..input)
 $                Stringify each and concat
  c               Copy atop the stack
   %|F            Factorial of length
      s           Swap original back to top
       o          Sort
        :G        Run lengths
          F       For each:
           |F       Factorial
             /      Divide running quotient by this factorial
                  Implicit print
Khuldraeseth na'Barya
źródło
1

Galaretka , 11 bajtów

15-bajtowa odpowiedź Jelly na golfa Dennisa ...

ḶDFµW;ĠẈ!:/

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?

ḶDFµW;ĠẈ!:/ - Link: non-negative integer, N   e.g. 12
Ḷ           - lowered range            [0,1,2,3,4,5,6,7,8,9,10,11]
 D          - to decimal (vectorises)  [[0],[1],[2],[3],[4],[5],[6],[7],[8],[9],[1,0],[1,1]]
  F         - flatten                  [0,1,2,3,4,5,6,7,8,9,1,0,1,1]
   µ        - start a new monadic chain - i.e. f(that)
    W       - wrap in a list           [[0,1,2,3,4,5,6,7,8,9,1,0,1,1]]
      Ġ     - group indices by values  [[1,12],[2,11,13,14],3,4,5,6,7,8,9,10]
     ;      - concatenate              [[0,1,2,3,4,5,6,7,8,9,1,0,1,1],[1,12],[2,11,13,14],3,4,5,6,7,8,9,10]
       Ẉ    - length of each           [14,2,4,1,1,1,1,1,1,1,1]
        !   - factorial (vectorises)   [87178291200,2,24,1,1,1,1,1,1,1,1]
          / - reduce by:
         :  -   integer division       1816214400
Jonathan Allan
źródło
0

Python 2 , 190 bajtów

from collections import*
g,n=range,int(input())
p=lambda r:reduce(lambda x,y:x*y,r,1)
f=lambda n:p(g(1,n+1))
s=''.join(str(i)for i in g(n))
c=Counter(s)
print(f(len(s))/p(f(c[i])for i in c))

Wypróbuj online!

Alexey Burdin
źródło
0

Python 2 , 134 bajty

s="".join(map(str,range(input())))
n=d=1
for i in range(1,len(s)+1):n*=i;d*=i**len([c for c in range(10)if s.count(`c`)>=i])
print n/d

Wypróbuj online!

Alternatywne podejście ...

Chas Brown
źródło