Czynniki faktorowe

16

Dzisiaj w mojej klasie statystyk odkryłem, że niektóre czynniki można uprościć, jeśli zostaną pomnożone razem! Na przykład:5! * 3! = 5! *3*2 = 5! *6 = 6!

Twoja praca:

Biorąc pod uwagę ciąg zawierający tylko cyfry arabskie i wykrzykniki, uprość mój silniak do najkrótszego możliwego ciągu, w jak najmniejszej liczbie bajtów dla twojego języka, stylu golfowego.

Wejście

Ciąg zawierający tylko liczby arabskie i wykrzykniki. Współczynniki wejściowe nie będą większe niż 200 !. Silniki nie będą miały więcej niż jednego silnia na liczbę. Dane wejściowe można traktować jako listę liczb całkowitych.

Wynik

Prawdopodobnie skrócony ciąg, który ma równoważną wartość na wejściu. Zamówienie jest nieważne. Notacja czynnikowa jest koniecznością, ale nie musisz używać więcej niż jednego symbolu czynnikowego na liczbę.

Przypadki testowe

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!

Powodzenia

tuskiomi
źródło
Ponieważ pusty produkt ma wartość 1, to powiedzmy, że 1!1!pusty ciąg znaków?
Jonathan Allan
@JonathanAllan 1! 1! Zmniejsza się do 1! Lub 0!
tuskiomi
Który następnie sprowadza się do pustego ciągu: /
Jonathan Allan
@JonathanAllan Powiem, że 1 nie jest równy pustemu ciągowi znaków
tuskiomi

Odpowiedzi:

5

Galaretka ,  17  18 bajtów

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

Monadyczny link pobierający i zwracający listę liczb (trzyma się jednej opcji silnia na liczbę)

Wypróbuj online!

W jaki sposób?

Gra w golfa (choć napisana niezależnie) rozwiązania Pietu1998.

!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
źródło
1
Wydaje mi się to wystarczająco jasne - nie musimy tego używać, ale możemy to zrobić, jeśli chcemy.
Jonathan Allan
1
@tuskiomi Stopka po prostu formatuje wynik listy dla zachowania przejrzystości ... jako pełny program (a nie jako funkcja) kod wydrukuje format listy Jelly (nic dla pustych i bez załączania [] dla list o długości 1) .
Jonathan Allan
1
@tuskiomi TIO ma ograniczenia ;-), ale myślę, że działa teoretycznie.
Erik the Outgolfer
1
@tuskiomi potęga kartezjańska zaowocowałaby listą 23! ^ 4 list. Skończy się czas (limit TIO 60s), jeśli nie pamięć.
Jonathan Allan
1
N! ^ M gdzie N jest produktem, a M jest liczbą terminów (i też w przestrzeni !!)
Jonathan Allan
3

Galaretka , 19 bajtów

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

Wypróbuj online!

Szybko i brudno. Bardzo wolno, nawet 23!2!3!2!przypadek testowy jest odcinkiem. I / O jako listy liczb całkowitych.

Wyjaśnienie

,!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
źródło
Możemy używać list jako I / O
Jonathan Allan
@JonathanAllan Och, to najwyraźniej nie było edytowane w OP
PurkkaKoodari
Moje 17 wydaje się jeszcze wolniejsze ...
Jonathan Allan
Och, to jest zbyt podobne - tio.run/##y0rNyan8/…
Jonathan Allan
@JonathanAllan Śmiało i opublikuj to, wygląda inaczej niż dla mnie, mimo że algorytm jest zasadniczo taki sam.
PurkkaKoodari
2

Czysty , 397 ... 317 bajtów

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

Wypróbuj online!

Przyjmuje to [Int], określa główne czynniki wyniku i zmniejsza ponad czynniki, aby znaleźć najmniejszą reprezentację, używając największego współczynnika na dowolnym etapie jako wartości wyjściowej dla następnego składnika czynnikowego. Nie ukończy niektórych testów na TIO, ale jest dość * szybki i może uruchomić je wszystkie w mniej niż 3 minuty na laptopie średniej klasy.

* dla O((prod(N)!)^sum(N))algorytmu złożoności

Obrzydliwe
źródło
Testcase: 6, 2, 2
tsh
@tsh Naprawiono teraz. Nie sortowano według najmniejszej długości, ale według największego pierwszego członka opartego na błędnym założeniu.
Οurous
1

> <> , 66 bajtów

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

Wypróbuj online!

Nieefektywny, nie znajduje najmniejszego ciągu, a tłumacz nie radzi sobie zbyt dobrze z bardzo dużymi liczbami. Ale przynajmniej próbowałem? Pobiera dane wejściowe jako listę liczb za pośrednictwem -vflagi.

Najpierw oblicza wartość wejściową, dzieląc każdą liczbę i mnożąc je razem. Następnie znajduje największy czynnik, który dzieli czysto na sumę i generuje go. Powtarzaj, aż albo otrzyma liczbę pierwszą (którą wyprowadza) lub 1 i wyjdzie z programu. Z tego powodu, że czasami nie znaleźć najkrótszą reprezentację liczby, na przykład w przypadku testu 7!2!2!7!2!2!2!2!powraca 10!224zamiast 8!8!bo stwierdzi suma jest podzielna przez 10! pierwszy.

Jo King
źródło
1

Rubinowy , 240 237 233 bajty

Jest to niezwykle nieefektywne

Akceptuje tablicę liczb całkowitych jako dane wejściowe

Zwraca ciąg znaków i wybiera najkrótszą opcję między, powiedzmy '720!', '6!!'a'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]}

Wypróbuj online!

Asone Tuhid
źródło