Menyusun ulang urutan

23

pengantar

Mari kita amati urutan berikut (bilangan bulat non-negatif):

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, ...

Sebagai contoh, mari kita ambil tiga angka pertama . Ini adalah 0, 1, 2. Angka-angka yang digunakan dalam urutan ini dapat dipesan dalam enam cara berbeda:

012   120
021   201
102   210

Jadi, katakanlah F (3) = 6 . Contoh lain adalah F (12) . Ini berisi angka-angka:

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11

Atau versi gabungan:

01234567891011

Untuk menemukan sejumlah cara untuk mengatur ulang ini, pertama-tama kita perlu melihat panjang string ini. Panjang string ini adalah 14. Jadi kami menghitung 14! . Namun, misalnya yang dapat bertukar tempat tanpa mengganggu string terakhir. Ada 2 nol, jadi ada 2! cara untuk mengubah angka nol tanpa mengganggu urutannya. Ada juga 4, jadi ada 4! cara untuk beralih. Kami membagi total dengan dua angka ini:

Ada 14! / (4! × 2!) = 1816214400 cara untuk mengatur string 01234567891011. Jadi kita dapat menyimpulkan bahwa F (12) = 1816214400 .

Tugas

Diberikan N , output F (N) . Untuk mereka yang tidak membutuhkan pengantar. Untuk menghitung F (N), pertama-tama kita menggabungkan bilangan bulat N-negatif pertama (misalnya untuk N = 12, string yang digabungkan akan menjadi 01234567891011) dan menghitung jumlah cara untuk mengatur string ini.

Uji kasus

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

Catatan

Menghitung jawaban harus dihitung dalam batas waktu 10 detik , brute-force tidak diperbolehkan .

Ini adalah , jadi pengiriman dengan jumlah byte paling sedikit menang!

Adnan
sumber
Apakah hasilnya 10benar? Rasanya seperti itu harus kurang dari 10 !, karena di situlah angka yang berulang dimulai.
Geobits
@ Geobits 10Digit pertama adalah 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Sepuluh digit berbeda, jadi hasilnya 10!
Adnan
Ah benar saya pikir0 kasus ini melempar hitungan saya (string kosong bodoh).
Geobits
1
Tidak perlu khawatir tentang itu lagi. Proposal celah berada di +4 ketika saya memposting komentar. Sekarang jam +9 .
Dennis
1
Inilah pertanyaan matematika yang menarik tentang teka-teki ini: Berapa nilai F (N) relatif terhadap N !? Ada sejumlah nilai N yang F (N) / F (N-1) <N, tetapi biasanya sedikit lebih besar. Saya cukup yakin F(N)tidakO(N!) dan itu log F(N)adalah O(log N!)tetapi mereka hanya firasat ...
Rici

Jawaban:

5

Jelly, 17 15 byte

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

Cobalah online! atau verifikasi semua kasus uji sekaligus .

Bagaimana itu bekerja

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
sumber
Apakah ini benar-benar Jelly? Saya melihat banyak karakter ASCII :-P
Luis Mendo
3
Mereka selalu berhasil menyelinap masuk entah bagaimana ...
Dennis
10

ES6, 118 81 78 byte

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

Seseorang pasti memberi tahu saya bahwa ada cara yang lebih singkat untuk merangkai angka-angka itu n.

Menyimpan 37 byte keren dengan mengambil ide @ edc65 dan menjalankannya dengan steroid. (Simpan byte tambahan dengan menggunakan '|' alih-alih&& tetapi itu membatasi hasilnya hingga 31 bit.)

Sunting: Disimpan 3 byte lebih lanjut lagi berkat @ edc65.

Neil
sumber
Tidak menemukan cara untuk mempersingkat penggabungan digit. Tetapi sisanya bisa lebih pendek
edc65
Simpan 2 byte dengan reduce:n=>[...[...Array(n).keys()].join``].reduce((r,c,i)=>r*++i/(o[c]=-~o[c]),1,o=[])
user81655
1
Wow! tetapi 78 lebih baik:n=>[...[...Array(n).keys()].join``].map(c=>r/=(o[c]=-~o[c])/i++,o=[],i=r=1)&&r
edc65
1
@ edc65 r/=(...)/i++lebih akurat daripada r*=i++/(...)? Itu golf paling menggelikan yang pernah saya lihat!
Neil
2
Saya harus berhenti sejenak, karena saya pikir Anda memiliki regex di sana.
Mama Fun Roll
7

APL (Dyalog Extended) , 13 byte

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

Cobalah online!

Program lengkap. Penggunaan ⎕IO←0.

Bagaimana itu bekerja

×/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

Perhitungan multinomial berasal dari fakta berikut:

(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!

==(a1+a2a1)(a1+a2+a3a1+a2)(a1++ana1++an1)

Bubbler
sumber
1
Dan inilah mengapa programmer harus belajar matematika.
Anonim
@ Anonim ... dan gunakan bahasa pemrograman yang cenderung matematis.
Adám
5

MATL , 21 byte

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

Cobalah online!

Penjelasan

: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
sumber
@Adnan Diselesaikan. Dan dengan byte lebih sedikit :-)
Luis Mendo
Terlihat sangat baik! :)
Adnan
@ Adnan Terima kasih! Saya telah menambahkan penjelasan
Luis Mendo
5

Python 2, 142 137 101 97 byte

(Terima kasih @adnan untuk sarannya input )

(Diterapkan perhitungan inkremental dari versi 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

Versi asli menggunakan faktorial

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)))

Sungguh, satu-satunya golf di atas adalah panggilan math.factorial F dan meninggalkan beberapa ruang, jadi mungkin ada solusi python yang lebih pendek.

Jika diperlukan penjelasan, v pertahankan hitungan frekuensi setiap digit; hitungan diperbarui untuk setiap digit di setiap angka dalam rentang yang ditunjukkan.

Dalam versi asli, kami menghitung jumlah permutasi menggunakan rumus standar (Σf i )! / Π (f i !). Untuk versi saat ini, perhitungan ini dilakukan secara bertahap dengan mendistribusikan multiplies dan membagi seperti yang kita lihat digit. Mungkin tidak jelas bahwa pembagian bilangan bulat akan selalu tepat, tetapi mudah untuk membuktikan berdasarkan pengamatan bahwa setiap divisi kharus mengikuti kmultiplies dari integer berturutan, sehingga salah satu dari multiplies tersebut harus dapat dibagi olehk . (Itu intuisi, bukan bukti.)

Versi asli lebih cepat untuk argumen besar karena hanya membagi 10 bignum. Meskipun membagi bignum dengan bilangan bulat kecil lebih cepat daripada membagi bignum dengan bignum, ketika Anda memiliki ribuan bignum membagi, itu menjadi sedikit lamban.

Rici
sumber
f = f * jumlah (v) / v [k] -> f * = jumlah (v) / v [k] menyimpan satu byte
Mikko Virkkilä
@superflux: tapi itu tidak sama artinya.
rici
5

Python 2, 197 Bytes (sunting: disimpan 4 byte, terima kasih 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

Tidak Disatukan:

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
sumber
1
Selamat Datang di Programming Puzzles dan Code Golf! Jawaban ini ditandai sebagai VLQ (kualitas sangat rendah), saya curiga karena tidak mengandung penjelasan atau versi yang tidak diklik, yang merupakan norma di sini. Dengan asumsi jawaban Anda berfungsi, dan Anda memperbaikinya dari menjadi "hanya kode", sepertinya cukup bagus!
kucing
range(0,10)bisa range(10).
lirtosiast
4

CJam, 21 19 byte

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

Uji di sini.

Penjelasan

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
sumber
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)

Uji

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
sumber
Bukankah k[c]=~-k[c]identik dengan --k[c]?
usandfriend
1
@ usandfriends no, ketika k [c] tidak ditentukan --k [c] adalah NaN
edc65
Ooh, berbagai faktorial.
Neil
... meskipun kamu tidak membutuhkannya. Lihat pembaruan terakhir saya.
Neil
3

Pyth, 18 byte

/F.!M+lJ.njRTQ/LJT

Cobalah online: Demonstrasi

/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
sumber
3

Haskell, 92 byte

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

Contoh penggunaan: h 12-> 1816214400.

Bagaimana itu bekerja

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
sumber
3

C, 236 174 138 121 byte

Banyak kredit untuk rici, untuk pengurangan besar byte.

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);}

Tidak disatukan

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 */
}

Coba di sini .

Cole Cameron
sumber
1
Anda bisa menyimpan 43 karakter dengan tidak mengotak-atik dengan -lm. Hitung saja digit ketika Anda menemukannya:#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
Anda juga bisa menghitungnya dalam loop di mana Anda menghitung d: for(;m<10;)s+=b[m],d*=f(b[m++])tapi saya pikir itu beberapa byte lagi.
rici
Itu brilian. Saya akan menggabungkan dengan upaya golf saya saat ini dan mengedit.
Cole Cameron
Bagus: lihat tambang untuk melihat bagaimana mengintegrasikan perhitungan faktorial ke dalam loop asli, yang memiliki keuntungan bekerja pada kisaran yang sedikit lebih besar jika Anda tidak memiliki aritmatika presisi sewenang-wenang. Saya pikir itu 20 byte lagi untuk dicukur.
rici
3

C / bc, 233 121 112 byte (dengan asumsi penalti 3 byte untuk |bc)

  1. Terinspirasi oleh Cole Cameron, menghapus manipulasi karakter hacky dan hanya melakukan aritmatika pada nilai argumen.

  2. Berubah menjadi scanf dari menggunakan arg 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");}
    

Perlu bcbenar-benar melakukan perhitungan presisi yang sewenang-wenang.

Tidak disatukan dan bebas peringatan:

#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 */
}

Diilustrasikan (yang saya percayai menunjukkan algoritme):

$ 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

Dan, dengan pipa melalui bc (dan menambahkan perhitungan 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

Ini menghitung F (5000) - angka 18.592 digit - dalam waktu kurang dari 10 detik.

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

real    0m9.274s
user    0m9.273s
sys     0m0.005s
Rici
sumber
3

Perl 6, 117 byte

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

dan dalam fasion yang lebih mudah dibaca

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;
}
Joshua
sumber
3

Perl 5, 108 byte

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

Banyak terima kasih kepada dev-null karena telah menyelamatkan saya 17 byte, dan untuk japhy atas ide faktorial.

msh210
sumber
3

05AB1E , 13 12 11 byte

ÝD¨SāPr¢!P÷

Cobalah 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
Grimmy
sumber
3

Python 2 , 123 byte

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

Cobalah online!

  1. Ubah rangeinput menjadi string tunggal
  2. Periksa berapa kali masing-masing angka dari 0 hingga 9 muncul dalam string dan dapatkan faktorial untuk masing-masing kemudian gandakan bersama
  3. Bagilah faktorial dari panjang tali dengan jumlah yang dihitung pada langkah 2
ElPedro
sumber
2

PowerShell, 125 byte

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

Mengambil input $args[0], mengurangi 1, membangun serangkaian bilangan bulat dari 0..angka itu, -joinmenyatukannya menjadi sebuah string, dan menyimpannya sebagai $b. Kami mengambil .Lengthstring itu, membangun rentang lain dari 1..panjang itu, -joinbilangan bulat itu bersama *, lalu menyalurkannya keInvoke-Expression (mirip denganeval ). Dengan kata lain, kami telah membangun faktorial dari panjang urutan nomor berdasarkan input. Itu pembilang kita.

Kami membaginya / dengan ...

Penyebut kami, yang dibangun dengan mengambil jarak 0..9dan mengirimkannya melalui for-loop |%{...}. Setiap iterasi, kami menetapkan variabel pembantu $csama dengan berapa kali digit saat ini $_muncul dalam $bberkat panggilan NET[regex]::matches ditambah dengan .countatribut. Kami kemudian membuat rentang baru dari 1..hingga nilai itu, asalkan bukan nol. Ya, dalam banyak kasus, ini akan menghasilkan kisaran 1..1, yang dievaluasi menjadi adil 1. Kami mengambil semua itu dan -joinmereka bersama-sama *, lalu menyambungkannya Invoke-Expressionlagi. Dengan kata lain, kami telah membuat produk faktorial dari jumlah kemunculan setiap digit.


NB

Menangani input hingga 90tanpa masalah dan secara signifikan kurang dari satu detik.

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

... di luar itu menghasilkan Infinitysebagai output, karena panjang string yang diijinkan menghasilkan 170!cocok dengan doubletipe data ( 7.25741561530799E+306), tetapi 171!tidak. PowerShell memiliki ... permainan kata-kata ... yang secara otomatis up-gips dari [int]ke [double]dalam kasus overflow (asalkan Anda tidak secara eksplisit melemparkan variabel untuk memulai dengan). Tidak, saya tidak tahu mengapa itu tidak menggunakan [long]nilai integer.

Jika kami melakukan beberapa casting dan manipulasi eksplisit (misalnya, menggunakan [uint64], untuk integer 64-bit yang tidak ditandatangani), kami bisa mendapatkan yang lebih tinggi, tetapi itu akan menggembungkan kode secara signifikan karena kami perlu berkisar hingga 170-panjang dengan kondisional dan kemudian menyusun kembali setiap perkalian dari sana ke depan. Karena tantangannya tidak menentukan kisaran atas, saya menganggap ini sudah memadai.

AdmBorkBork
sumber
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'

Agak ungolfed saat ini - perlu tidur sekarang.

pengguna52889
sumber
2

Groovy, 156 byte

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)}

Solusi Code Golf pertama saya yang sederhana. Anda bisa mengujinya di sini.

Dan ini versi yang lebih mudah dibaca:

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

Cukup mudah, tetapi ada beberapa highlight untuk saya:

  • Melakukan suntikan / pengurangan dari array charske Map<Character, Integer>. Ini masih sedikit rumit oleh kurangnya nilai default untuk nilai peta. Keraguan ini mungkin, tetapi jika peta men-default semua nilai ke 0, saya bisa menghindari ternary yang diperlukan untuk menghindari NPE.

  • Operator penyebaran Groovy (mis. }*.value) Selalu menyenangkan untuk digunakan

Pada fitur yang mengganggu, adalah keharusan untuk mendeklarasikan fungsi faktorial dengan tipe kembali BigInteger. Saya mendapat kesan bahwa Groovy membungkus semua angka BigIntegeratau BigDecimal, tetapi ini mungkin tidak terjadi ketika datang untuk mengembalikan tipe. Saya harus bereksperimen lebih banyak. Tanpa jenis pengembalian ini secara eksplisit dinyatakan, kami mendapatkan nilai faktorial yang salah dengan sangat cepat.

lealand
sumber
2

J, 33 byte

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

Ubah rentang menjadi string digit, hitung setiap digit, dan terapkan koefisien multinomial untuk menghitung hasilnya.

Pemakaian

   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
mil
sumber
2

R, 118 byte

Sekitar 8 bulan terlambat ke pesta tetapi berpikir saya akan mencobanya karena itu tampak seperti tantangan yang menarik.

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)

Cobalah R-biola

Dijelaskan

  1. Hasilkan vektor 0 ... n-1dan runtuh ke string:paste(1:n-1,collapse="")
  2. Pisahkan string menjadi digit-nya dan konversikan ke numerik (simpan sebagai x):x=as.numeric(el(strsplit(...,"")))
  3. Untuk menghitung pembilang, kita cukup melakukan factorial(sum(1|x))mana saja#digits!
  4. Untuk menghitung penyebut kita menggunakan tableuntuk membangun tabel kontingensi yang berisi daftar frekuensi. Dalam kasus F (12) tabel yang dihasilkan adalah:

    0 1 2 3 4 5 6 7 8 9 
    2 4 1 1 1 1 1 1 1 1 
    
  5. Yang berarti kita dapat menggunakan factorial()(yang by the vectorized) menggunakan hitungan dan hanya mengambil produk:prod(factorial(table(x)))

Catatan: langkah 4 dan 5 hanya dijalankan jika n>0sebaliknya kembali 1.

Billywob
sumber
1

Mathematica, 65 byte

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

Mungkin bisa bermain golf lebih lanjut.

LegionMammal978
sumber
1

Stax , 12 byte

éÄ\↑≈g→FP○░→

Jalankan dan debug di staxlang.xyz!

Dibongkar (14 byte) dan penjelasan:

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
sumber
1

Jelly , 11 byte

Golfed 15 byte Jelly menjawab ...

ḶDFµW;ĠẈ!:/

Tautan monadik yang menerima bilangan bulat non-negatif yang menghasilkan bilangan bulat positif.

Cobalah online! Atau lihat suite tes .

Bagaimana?

Ḷ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
sumber
0

Python 2 , 190 byte

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))

Cobalah online!

Alexey Burdin
sumber
0

Python 2 , 134 byte

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

Cobalah online!

Pendekatan alternatif ...

Chas Brown
sumber