Factoring Fakultäten

16

Heute in meiner Statistikklasse habe ich festgestellt, dass einige Fakultäten vereinfacht werden können, wenn sie miteinander multipliziert werden! Beispielsweise:5! * 3! = 5! *3*2 = 5! *6 = 6!

Deine Arbeit:

Vereinfachen Sie meine Fakultät mit einer Zeichenfolge, die nur arabische Zahlen und Ausrufezeichen enthält, auf die kürzestmögliche Zeichenfolge, und zwar in der für Ihre Sprache geringsten Anzahl von Bytes, Code-Golf-Stil.

Eingang

Eine Zeichenfolge, die nur arabische Zahlen und Ausrufezeichen enthält. Die Fakultäten für die Eingabe werden nicht größer als 200 sein !. Fakultäten werden nicht mehr als eine Fakultät pro Zahl haben. Die Eingabe kann als Liste von ganzen Zahlen erfolgen.

Ausgabe

Eine möglicherweise verkürzte Zeichenfolge, die den entsprechenden Wert für die Eingabe hat. Ordnung ist unwichtig. Die faktorielle Notation ist ein Muss, Sie müssen jedoch nicht mehr als ein faktorielles Symbol pro Zahl verwenden.

Testfälle

In: 3!2!2!  
Out: 4! 

In 2!3!2!0! 
Out: 4! 

In: 7!2!2!7!2!2!2!2! 
Out: 8!8! 

In: 23!3!2!2! 
Out: 24!  
Also: 4!!

In: 23!3!2!2!2! 
Out: 24!2!

In: 127!2!2!2!2!2!2!2! 
Out: 128!

In: 32!56!29!128!  
Out: 29!32!56!128!

Viel Glück

tuskiomi
quelle
Da das leere Produkt 1 ist, ist die Ausgabe für beispielsweise 1!1!nur eine leere Zeichenfolge?
Jonathan Allan
@ JonathanAllan 1! 1! Reduziert auf 1! Oder 0!
Tuskiomi
Was dann auf die leere Zeichenfolge reduziert: /
Jonathan Allan
@ JonathanAllan Ich werde sagen, 1 ist nicht gleich wie leere Zeichenfolge
Tuskiomi

Antworten:

5

Jelly ,  17 bis  18 Bytes

!P
ÇṗLÇ⁼¥ÐfÇḢḟ1ȯ0F

Ein monadischer Link, der eine Liste der Zahlen aufnimmt und zurückgibt (bleibt bei der Option einer Fakultät pro Zahl)

Probieren Sie es online!

Wie?

Eine Golfversion (obwohl unabhängig geschrieben) der Pietu1998-Lösung.

!P - Link 1, product of factorials: list
!  - factorial (vectorises)
 P - product

ÇṗLÇ⁼¥ÐfÇḢḟ1ȯ0F - Main link: list                       e.g. [3,2,2]
Ç               - call the last link (1) as a monad           24
  L             - length                                      3
 ṗ              - Cartesian power      [[1,1,1],[1,1,2],...,[1,1,24],...,[24,24,24]]
        Ç       - call the last link (1) as a monad           24
      Ðf        - filter keep if:
     ¥          -   last two links as a dyad:
   Ç            -     call the last link (1) as a monad     [1,2,...,24!,...,24!^3]
    ⁼           -     equal?
         Ḣ      - head
          ḟ1    - filter out any ones
            ȯ0  - or with zero (for the empty list case)
              F - flatten (to cater for the fact that zero is not yet a list)
Jonathan Allan
quelle
1
Scheint mir klar genug - wir müssen es nicht benutzen, können es aber, wenn wir wollen.
Jonathan Allan
1
@tuskiomi Die Fußzeile formatiert lediglich die Listenausgabe, um die Übersichtlichkeit zu gewährleisten. Als vollständiges Programm (und nicht als Funktion) gibt der Code das Jelly-Format einer Liste aus (nichts für leere und kein Einschließen von [] für Listen der Länge 1). .
Jonathan Allan
1
@tuskiomi TIO hat Grenzen ;-) aber ich denke es funktioniert theoretisch.
Erik der Outgolfer
1
@tuskiomi die kartesische Macht würde zu einer Liste von 23! ^ 4 Listen führen. Wenn kein Speicher vorhanden ist, ist die Zeit abgelaufen (TIO auf 60s begrenzt).
Jonathan Allan
1
N! ^ M wobei N ist das Produkt und M ist die Anzahl der Begriffe (und im Raum auch !!)
Jonathan Allan
3

Jelly , 19 Bytes

,!P€E
SṗLçÐfµḢḟ1ȯ1F

Probieren Sie es online!

Schnell und dreckig. Sehr langsam, auch der 23!2!3!2!Testfall ist eine Strecke. I / O als Liste von ganzen Zahlen.

Erläuterung

,!P€E    Helper link. Arguments: attempt, original
,        Make the array [attempt, original].
         Example: [[1,1,1,4], [2,3,2,0]]
 !       Take the factorial of each item.
         Example: [[1,1,1,24], [2,6,2,1]]
  P€     Take the product of each sublist.
         Example: [24, 24]
    E    Check if the values are equal.

SṗLçÐfµḢḟ1ȯ1F   Main link. Arguments: original
S               Find the sum S of the integers in the input.
  L             Find the number N of integers in the input.
 ṗ              Generate all lists containing N integers from 1 to S.
   çÐf          Take the lists whose factorial-product is the same as the original.
       Ḣ        Take the first match. This is the one with the most ones.
        ḟ1      Remove any ones.
          ȯ1    If there were only ones, return a one instead.
            F   Turn into a list if needed.
PurkkaKoodari
quelle
Wir können Listen als I / O verwenden
Jonathan Allan
@ JonathanAllan Oh, das wurde anscheinend nicht in die OP
PurkkaKoodari 18.01.18
Meine 17 scheint noch langsamer ...
Jonathan Allan
Oh, es ist viel zu ähnlich - tio.run/##y0rNyan8/…
Jonathan Allan
@ JonathanAllan Mach weiter und poste es, sieht für mich anders aus, obwohl der Algorithmus im Wesentlichen derselbe ist.
PurkkaKoodari
2

Sauber , 397 ... 317 Bytes

import StdEnv,StdLib
c=length
f c m=sortBy c o flatten o map m
%n=f(>)@[2..n]
@1=[]
@n#f=[i\\i<-[2..n]|n/i*i==n&&and[i/j*j<i\\j<-[2..i-1]]]
=f++ @(n/prod f)
?l=group(f(>)%l)
$l=hd(f(\a b=c a<c b)(~(?l))[0..sum l])
~[]_=[[]]
~i n=[[m:k]\\m<-take n[hd(i!!0++[0])..],k<- ~[drop(c a)b\\a<-group(%m)&b<-i|b>a]n|i== ?[m:k]]

Probieren Sie es online!

Dies nimmt ein [Int], bestimmt die Primfaktoren des Ergebnisses und reduziert die Faktoren, um die kleinste Darstellung zu finden, wobei der größte Faktor in jedem Stadium als Basiswert für den nächsten Fakultätsausdruck verwendet wird. Einige Testfälle werden mit TIO nicht abgeschlossen, aber es ist ziemlich schnell und kann sie alle auf einem Midrange-Laptop in weniger als 3 Minuten ausführen.

* für einen O((prod(N)!)^sum(N))Komplexitätsalgorithmus

Οurous
quelle
Testfall: 6, 2, 2
Dienstag,
@tsh Jetzt behoben. Es wurde nicht nach der kleinsten Länge sortiert, sondern nach dem größten ersten Element, basierend auf einer falschen Annahme.
Urous
1

> <> 66 Bytes

1}:?\~l1=?v{!
-:?!\:{*}1
v?( 4:{/}1<o"!"n-1
{:,} :{/?%}:+1
\:1-?n;

Probieren Sie es online!

Nicht effizient, findet nicht die kleinste Zeichenfolge und der Interpreter kann mit extrem großen Zahlen nicht gut umgehen. Aber zumindest habe ich es versucht? Übernimmt die Eingabe als Liste von Zahlen durch das -vFlag.

Zunächst wird der Wert der Eingabe berechnet, indem jede Zahl faktorisiert und miteinander multipliziert wird. Dann findet es die größte Fakultät, die sich sauber in die Summe aufteilt und diese ausgibt. Wiederholen Sie diesen Vorgang, bis entweder eine Primzahl (die ausgegeben wird) oder eine 1 angezeigt wird und das Programm beendet wird. Aus diesem Grund findet es manchmal nicht die kürzeste Darstellung der Zahl. Der Testfall 7!2!2!7!2!2!2!2!kehrt zum Beispiel zurück, 10!224anstatt festzustellen, dass 8!8!die Summe durch 10 teilbar ist. zuerst.

Scherzen
quelle
1

Ruby , 240 237 233 Bytes

Das ist unglaublich ineffizient

Akzeptiert ein Array von Ints als Eingabe

Gibt einen String zurück und wählt die kürzeste Option zwischen, sagen wir '720!', '6!!'und'3!!!'

->i{f=->n{n>0?n*f[n-1]:1}
s=->a{eval a.map{|i|f[i]}*?*}
r=->e,a=[2]{e==s[a]?a:s[a]<=e&&(r[e,a[0..-2]+[a[-1]+1]]||r[e,a+[2]])}
j=->v{v.join(?!)+?!}
u=r[s[i]]
while j[g=u.map{|i|i&&r[i]?[r[i],p]:i}.flatten].size<j[u].size;u=g;end
j[u]}

Probieren Sie es online!

Asone Tuhid
quelle