Reihenfolge ändern

23

Einführung

Beobachten wir die folgende Reihenfolge (nicht negative ganze Zahlen):

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

Nehmen wir zum Beispiel die ersten drei Zahlen. Das sind 0, 1, 2. Die in dieser Sequenz verwendeten Nummern können auf sechs verschiedene Arten bestellt werden:

012   120
021   201
102   210

Nehmen wir also an, dass F (3) = 6 ist . Ein weiteres Beispiel ist F (12) . Dies enthält die Zahlen:

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

Oder die verkettete Version:

01234567891011

Um die Anzahl der Möglichkeiten zu finden, dies neu anzuordnen, müssen wir uns zuerst die Länge dieser Zeichenfolge ansehen. Die Länge dieser Zeichenfolge beträgt 14. Also berechnen wir 14! . Zum Beispiel können diejenigen jedoch Orte austauschen, ohne die endgültige Zeichenfolge zu stören. Es gibt 2 Nullen, also gibt es 2! Möglichkeiten, die Nullen auszutauschen, ohne die Reihenfolge zu stören. Es gibt auch 4, also gibt es 4! Möglichkeiten, die zu wechseln. Wir teilen die Summe durch diese beiden Zahlen:

Das hat 14! / (4! × 2!) = 1816214400 Möglichkeiten zum Anordnen der Zeichenfolge 01234567891011. Wir können also schließen, dass F (12) = 1816214400 ist .

Die Aufgabe

Bei N wird F (N) ausgegeben . Für diejenigen, die keine Einführung brauchen. Um F (N) zu berechnen, verketten wir zuerst die ersten N nicht-negativen ganzen Zahlen (z. B. für N = 12 wäre die verkettete Zeichenfolge 01234567891011) und berechnen die Anzahl der Möglichkeiten, diese Zeichenfolge anzuordnen.

Testfälle

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

Hinweis

Die Berechnung der Antwort muss innerhalb einer Frist von 10 Sekunden erfolgen . Brute-Forcing ist nicht zulässig .

Das ist , also gewinnt die Einsendung mit der geringsten Anzahl von Bytes!

Adnan
quelle
Ist die Ausgabe 10korrekt? Es fühlt sich an, als sollte es weniger als 10 sein, da hier die sich wiederholenden Ziffern beginnen.
Geobits
@Geobits Die ersten 10Ziffern sind 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Zehn verschiedene Ziffern, also 10 !.
Adnan
Ah richtig. Ich denke, der 0Fall hat meine Zählung abgebrochen (dumme leere Fäden).
Geobits
1
Darüber brauchen Sie sich keine Sorgen mehr zu machen. Der Lückenvorschlag war bei +4, als ich den Kommentar gepostet habe. Es ist jetzt bei +9 .
Dennis
1
Hier ist eine interessante mathematische Frage zu diesem Rätsel: Was ist der Wert von F (N) relativ zu N !? Es gibt eine Anzahl von Werten für N, für die F (N) / F (N-1) <N ist, diese ist jedoch gewöhnlich geringfügig größer. Ich bin mir ziemlich sicher , dass F(N)nicht der Fall ist O(N!)und dass log F(N)ist , O(log N!)aber das ist nur Ahnungen ...
rici

Antworten:

5

Jelly, 17-15 Bytes

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

Probieren Sie es online! oder überprüfen Sie alle Testfälle auf einmal .

Wie es funktioniert

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
quelle
Ist das wirklich Gelee? Ich sehe zu vielen ASCII-Zeichen: -P
Luis Mendo
3
Sie schaffen es immer, sich irgendwie einzuschleichen ...
Dennis
10

ES6, 118 81 78 Bytes

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

Jemand muss mir sagen, dass es einen kürzeren Weg gibt, die Zahlen zu verketten n.

Sparte coole 37 Bytes, indem du die Idee von @ edc65 auf Steroiden ausführst. (Save ein zusätzliches Byte unter Verwendung von ‚|‘ statt &&. Aber dem Grenzen des Ergebnis 31 Bit)

Edit: 3 weitere Bytes dank @ edc65 gespeichert.

Neil
quelle
Es wurde keine Möglichkeit gefunden, die Ziffernverkettung zu verkürzen. Aber der Rest kann kürzer sein
edc65
Speichern Sie 2 Bytes mit reduce:n=>[...[...Array(n).keys()].join``].reduce((r,c,i)=>r*++i/(o[c]=-~o[c]),1,o=[])
user81655
1
Wow! aber 78 ist besser:n=>[...[...Array(n).keys()].join``].map(c=>r/=(o[c]=-~o[c])/i++,o=[],i=r=1)&&r
edc65
1
@ edc65 r/=(...)/i++ist genauer als r*=i++/(...)? Das ist das lächerlichste Golf, das ich je gesehen habe!
Neil
2
Ich musste einen Moment innehalten, weil ich dachte, du hättest eine Regex drin.
Mama Fun Roll
7

APL (Dyalog Extended) , 13 Byte

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

Probieren Sie es online!

Ein volles Programm. Verwendet ⎕IO←0.

Wie es funktioniert

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

Die multinomiale Berechnung ergibt sich aus folgender Tatsache:

(ein1+ein2++einn)!ein1!ein2!einn!=(ein1+ein2)!ein1!ein2!×(ein1+ein2++einn)!(ein1+ein2)!ein3!einn!

=(ein1+ein2)!ein1!ein2!×(ein1+ein2+ein3)!(ein1+ein2)!ein3!×(ein1+ein2++einn)!(ein1+ein2+ein3)!einn!

==(ein1+ein2ein1)(ein1+ein2+ein3ein1+ein2)(ein1++einnein1++einn-1)

Bubbler
quelle
1
Und deshalb sollten Programmierer Mathematik lernen.
Anonym
@Anonymous… und verwende eine mathematisch geneigte Programmiersprache.
Am
5

MATL , 21 Bytes

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

Probieren Sie es online!

Erläuterung

: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
quelle
@Adnan Gelöst. Und mit weniger Bytes :-)
Luis Mendo
Sieht sehr gut aus! :)
Adnan
@Adnan Danke! Ich habe eine Erklärung hinzugefügt
Luis Mendo
5

Python 2, 142 137 101 97 Bytes

(Danke @adnan für den Vorschlag über input)

(Wendet die inkrementelle Berechnung von der C-Version an )

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

Originalversion mit Fakultät

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

Wirklich, das einzige, was oben erwähnt wird, ist das Aufrufen math.factorial Fund Weglassen einiger Leerzeichen, also gibt es wahrscheinlich eine kürzere Python-Lösung.

Wenn eine Erklärung erforderlich ist, wird vdie Häufigkeit jeder Ziffer gezählt. Die Zählung wird für jede Ziffer in jeder Zahl im angegebenen Bereich aktualisiert.

In der Originalversion berechnen wir die Anzahl der Permutationen mit der Standardformel (Σf i )! / Π (f i !). Für die aktuelle Version erfolgt diese Berechnung inkrementell, indem die Multiplikationen und Divisionen so verteilt werden, wie wir die Ziffern sehen. Es mag nicht offensichtlich sein, dass die ganzzahlige Teilung immer genau sein wird, aber es ist leicht zu beweisen, dass jede Division durch mehrere aufeinanderfolgende ganze Zahlen kfolgen muss k, sodass eine dieser Multiplikationen durch teilbar sein muss k. (Das ist eine Intuition, kein Beweis.)

Die Originalversion ist schneller für große Argumente, da sie nur 10 Bignum-Teilungen enthält. Obwohl das Teilen eines Bignums durch eine kleine ganze Zahl schneller ist als das Teilen eines Bignums durch ein Bignum, wird es bei Tausenden von Bignum-Teilungen etwas träge.

rici
quelle
f = f * sum (v) / v [k] -> f * = sum (v) / v [k] speichert ein Byte
Mikko Virkkilä
@superflux: aber es ist nicht die gleiche bedeutung.
rici
5

Python 2, 197 Bytes (edit: 4 Bytes gespeichert, danke 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

Ungolfed:

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
quelle
1
Willkommen bei Programming Puzzles und Code Golf! Diese Antwort wurde als VLQ (sehr niedrige Qualität) gekennzeichnet, da sie vermutlich keine Erklärung oder ungolfed Version enthält, die hier die Norm sind. Angenommen, Ihre Antwort funktioniert und Sie verbessern sie, indem Sie "nur Code" sind, dann scheint sie ziemlich gut zu sein!
Katze
range(0,10)kann sein range(10).
Lirtosiast
4

CJam, 21 19 Bytes

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

Teste es hier.

Erläuterung

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

Prüfung

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
quelle
Geht das nicht k[c]=~-k[c]auch mit --k[c]?
Usandfriends
1
@usandfriends nein, wenn k [c] undefiniert ist
edc65
Ooh, schöne Auswahl an Fakultäten.
Neil
... obwohl du es nicht brauchst. Siehe mein letztes Update.
Neil
3

Pyth, 18 Bytes

/F.!M+lJ.njRTQ/LJT

Probieren Sie es online aus: Demonstration

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

Haskell, 92 Bytes

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

Anwendungsbeispiel: h 12-> 1816214400.

Wie es funktioniert

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

C 236 174 138 121 Bytes

Rici gebührt viel Anerkennung für die massive Reduzierung von Bytes.

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

Ungolfed

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

Probieren Sie es hier aus .

Cole Cameron
quelle
1
Sie könnten 43 Zeichen sparen, indem Sie nicht mit -lm herumspielen. Zählen Sie einfach die Ziffern, wie Sie sie finden:#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
Sie könnten sie auch in der Schleife zählen, in der Sie d berechnen: for(;m<10;)s+=b[m],d*=f(b[m++])aber ich denke, das sind ein paar Bytes mehr.
rici
Das ist hervorragend. Ich werde mit meinen aktuellen Golfbemühungen kombinieren und bearbeiten.
Cole Cameron
Nizza: Schauen Sie sich meine an, um zu sehen, wie die Fakultätsberechnung in die Originalschleife integriert wird. Dies hat den Vorteil, dass Sie in einem etwas größeren Bereich arbeiten können, wenn Sie keine Arithmetik mit willkürlicher Genauigkeit haben. Ich denke, das sind noch 20 Bytes zu rasieren.
rici
3

C / bc, 233 121 112 Bytes (unter der Annahme einer 3-Byte-Strafe für |bc)

  1. Inspiriert von Cole Cameron, wurde die hackige Manipulation von Charakteren entfernt und der Argumentwert einfach berechnet.

  2. Geändert in scanf von arg vector.

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

Muss bctatsächlich die willkürliche Präzisionsberechnung durchführen.

Ungolfed und warnfrei:

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

Illustriert (dem ich vertraue, zeigt der Algorithmus):

$ 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

Und mit der Pipe durch bc (und addiert die Berechnung von 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

Dies berechnete F (5000) - eine 18.592-stellige Zahl - in weniger als 10 Sekunden.

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

real    0m9.274s
user    0m9.273s
sys     0m0.005s
rici
quelle
3

Perl 6, 117 Bytes

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

und in einer lesbareren fasion

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

Perl 5, 108 Bytes

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

Vielen Dank an dev-null für das Speichern von 17 Bytes und an japhy für die faktorielle Idee.

msh210
quelle
3

05AB1E , 13 12 11 Bytes

ÝD¨SāPr¢!P÷

Probieren Sie es 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
Grimmig
quelle
3

Python 2 , 123 Bytes

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

Probieren Sie es online!

  1. Konvertieren Sie die range Eingabe in eine einzelne Zeichenfolge
  2. Überprüfen Sie, wie oft jede der Zahlen von 0 bis 9 in der Zeichenfolge vorkommt, und berechnen Sie die Fakultät für jede Zahl und multiplizieren Sie sie dann miteinander
  3. Teilen Sie die Fakultät der Länge der Zeichenfolge durch die in Schritt 2 berechnete Zahl
ElPedro
quelle
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)

Nimmt Eingaben auf $args[0], subtrahiert 1, erstellt eine Reihe von Ganzzahlen von 0..dieser Zahl -joinund fügt sie zu einer Zeichenfolge zusammen und speichert sie als $b. Wir nehmen die .Lengthvon dieser Zeichenkette, bauen einen anderen Bereich von 1..dieser Länge auf, -joindiese ganzen Zahlen zusammen mit *, und leiten das dann weiterInvoke-Expression (ähnlich wie eval) weiter. Mit anderen Worten, wir haben die Fakultät der Länge der Zahlenfolge basierend auf der Eingabe konstruiert. Das ist unser Zähler.

Das teilen wir / durch ...

Unser Nenner, der aufgebaut wird, indem ein Bereich genommen 0..9und durch eine for-Schleife gesendet wird |%{...}. Bei jeder Iteration setzen wir eine Hilfsvariable $c, die der Häufigkeit entspricht, mit der die aktuelle Ziffer dank des .NET- Aufrufs in Verbindung mit dem Attribut $_angezeigt wird. Wir konstruieren dann einen neuen Bereich von bis zu diesem Wert, solange er nicht Null ist. Ja, in vielen Fällen wird dies zu einem Bereich führen , der als gerecht bewertet wird . Wir nehmen alle diejenigen , und sie zusammen mit , dann Rohr , das zu wieder. Mit anderen Worten, wir haben das Produkt der Fakultäten der Anzahl der Vorkommen jeder Ziffer konstruiert.$b[regex]::matches.count1..1..11-join*Invoke-Expression


NB

Erledigt Eingaben 90problemlos und in deutlich weniger als einer Sekunde.

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

... darüber hinaus ergibt sich Infinityals Ausgabe, da die Länge der durchlässigen Zeichenkette ergibt, 170!welche in den doubleDatentyp ( 7.25741561530799E+306) passt , dies aber 171!nicht tut. PowerShell hat eine ... Eigenheit ..., die im Falle eines Überlaufs automatisch von [int]nach [double]hochwandelt (vorausgesetzt, Sie haben die Variable nicht explizit umgewandelt). Nein, ich weiß nicht, warum es nicht [long]für ganzzahlige Werte geht.

Wenn wir explizite Casting- und Manipulationsvorgänge durchführen (z. B. mit [uint64]64-Bit-Ganzzahlen ohne Vorzeichen), könnten wir diese zwar erhöhen, aber der Code würde dadurch erheblich aufgebläht, da wir mit Bedingungen einen Bereich von bis zu 170 Länge benötigen und ihn dann neu erstellen müssten jede Multiplikation von da an. Da die Herausforderung keinen oberen Bereich angibt, gehe ich davon aus, dass dies angemessen ist.

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

Im Moment eher ungolfed - brauche jetzt Schlaf.

user52889
quelle
2

Groovy, 156 Bytes

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

Meine bescheidene erste Code Golf Lösung. Sie können es hier testen.

Und hier ist eine besser lesbare Version:

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

Ganz einfach, aber es gab ein paar Highlights für mich:

  • Durchführen einer Injektion / Reduktion von einem Array von charsauf ein Map<Character, Integer>. Dies war immer noch etwas kompliziert, da es keinen Standardwert für die Kartenwerte gab. Dies bezweifle, dass dies möglich ist, aber wenn die Karte alle Werte auf 0 zurücksetzt, könnte ich das Ternäre vermeiden, das notwendig ist, um eine NPE zu vermeiden.

  • Der Groovy Spread Operator (zB }*.value) macht immer Spaß

Ein ärgerliches Merkmal war jedoch die Notwendigkeit, die Fakultätsfunktion mit dem Rückgabetyp zu deklarieren BigInteger. Ich hatte den Eindruck, dass Groovy alle Zahlen in BigIntegeroder eingeschlossen hat BigDecimal, aber dies ist möglicherweise nicht der Fall, wenn es um Rückgabetypen geht. Ich muss noch mehr experimentieren. Ohne diesen explizit angegebenen Rückgabetyp erhalten wir sehr schnell falsche Fakultätswerte.

lealand
quelle
2

J, 33 Bytes

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

Konvertiert den Bereich in eine Folge von Ziffern, zählt jede Ziffer und wendet den Multinomialkoeffizienten an, um das Ergebnis zu berechnen.

Verwendung

   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
Meilen
quelle
2

R, 118 Bytes

Ungefähr 8 Monate zu spät zur Party, aber ich dachte, ich würde es versuchen, weil es nach einer interessanten Herausforderung aussah.

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)

Probieren Sie es auf R-Geige

Erklärt

  1. Erzeugen Sie einen Vektor 0 ... n-1und reduzieren Sie ihn zu einem String:paste(1:n-1,collapse="")
  2. Teilen Sie die Zeichenfolge in Ziffern auf und konvertieren Sie sie in numerische Zeichen (speichern unter x):x=as.numeric(el(strsplit(...,"")))
  3. Um den Zähler zu berechnen, machen wir einfach factorial(sum(1|x))was gerade ist#digits!
  4. Um den Nenner zu berechnen, erstellen wir tableeine Kontingenztabelle, in der die Häufigkeiten aufgelistet sind. Im Fall von F (12) ist die erzeugte Tabelle:

    0 1 2 3 4 5 6 7 8 9 
    2 4 1 1 1 1 1 1 1 1 
    
  5. Das heißt, wir können die Verwendung factorial()(die übrigens vektorisiert ist) für die Zählung verwenden und einfach das Produkt nehmen:prod(factorial(table(x)))

Hinweis: Die Schritte 4 und 5 werden nur ausgeführt, wenn sie n>0ansonsten zurückgegeben werden 1.

Billywob
quelle
1

Mathematica, 65 Bytes

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

Könnte wahrscheinlich weiter golfen werden.

LegionMammal978
quelle
1

Stax , 12 Bytes

éÄ\↑≈g→FP○░→

Führen Sie es aus und debuggen Sie es unter staxlang.xyz!

Entpackt (14 Bytes) und Erklärung:

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

Jelly , 11 Bytes

Dennis '15-Byte -Gelee-Antwort auf dem Golfplatz ...

ḶDFµW;ĠẈ!:/

Ein monadischer Link, der eine nicht negative Ganzzahl akzeptiert, die eine positive Ganzzahl ergibt.

Probieren Sie es online! Oder sehen Sie sich die Testsuite an .

Wie?

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

Python 2 , 190 Bytes

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

Probieren Sie es online!

Alexey Burdin
quelle
0

Python 2 , 134 Bytes

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

Probieren Sie es online!

Ein alternativer Ansatz ...

Chas Brown
quelle