Hamming-Nummern

19

Geben Sie bei einer positiven Ganzzahl so viele Hamming-Zahlen in der angegebenen Reihenfolge aus.

Regeln:

  • Die Eingabe erfolgt als positive Ganzzahln1,000,000
  • Die Ausgabe sollte die ersten n Begriffe von https://oeis.org/A051037 sein
  • Die Ausführungszeit muss <1 Minute sein
  • Das ist ; kürzester Code gewinnt
grokus
quelle
2
Welches Ziel sollte eine Antwort haben? Golf? Effektivster Algorithmus? Nur nach Lösungsmethoden suchen?
Nakilon
Entschuldigen Sie, dass Sie nicht konkret sind. Ich habe das nicht selbst gelöst, daher bin ich mir nicht sicher, ob die von mir eingegebenen Grenzen angemessen sind. Lass es mich wissen, bitte.
Grokus
OEIS
Stephen
3
Da 1 eine Hamming-Zahl ist, entspricht das Drucken von 1.000.000 1s Ihren Spezifikationen. Es wird auch in Ordnung sein, dh keine ungeordnete Reihenfolge. :)
Will Ness

Antworten:

7

Haskell, 101 97 92+ | n | Zeichen

h=1:m 2h&m 3h&m 5h
m=map.(*)
c@(a:b)&o@(m:n)|a<m=a:b&o|a>m=m:c&n|0<1=a:b&n
main=print$take 1000000h

Berechnet die volle Million in 3.7s auf dem Computer, auf dem ich getestet habe (variabel mehr, wenn Sie die Ausgabe tatsächlich speichern möchten)

Ungolfed:

-- print out the first million Hamming numbers
main = print $ take 1000000 h

-- h is the entire Hamming sequence.
-- It starts with 1; for each number in the
-- sequence, 2n, 3n and 5n are also in.
h = 1 : (m 2 h) & (m 3 h) & (m 5 h)

-- helper: m scales a list by a constant factor
m f xs = map (f*) xs

-- helper: (&) merges two ordered sequences
a@(ha:ta) & b@(hb:tb)
    |    ha < hb = ha : ta & b
    |    ha > hb = hb :  a & tb
    |  otherwise = ha : ta & tb

Alles in allem ist Haskell dafür bekannt, eine Liste als eine träge Funktion von sich selbst zu definieren, auf eine Weise, die tatsächlich funktioniert.

JB
quelle
1
Sie erhalten nicht den positiven Integer-Parameter, der Ihrem Code mehr Größe verleiht
Zhen
@Zhen Der positive Ganzzahlparameter ist das vorletzte Token und seine Größe wird im Header als "outfront" deklariert.
JB
3

Python 181 Zeichen

h=[]        
h.append(1)
n=input()
i=j=k=0
while n:
    print h[-1]
    while h[i]*2<=h[-1]:
        i+=1
    while h[j]*3<=h[-1]:
        j+=1
    while h[k]*5<=h[-1]:
        k+=1
    h.append(min(h[i]*2,h[j]*3,h[k]*5))
    n-=1
fR0DDY
quelle
Wie ist das 181 Zeichen? Ich habe dies in einer Datei gespeichert und das Leerzeichen danach h=[]mit einem minimalen Tabulatorabstand und Zeilenumbrüchen für einzelne Zeichen entfernt. Die Dateigröße beträgt schließlich 187 Byte.
Nitro2k01
1
Wie auch immer ... Trivial Optimierung: h=[1]. Geben Sie außerdem eine Nummer direkt im Quellcode an, um Zeichen für Zahlen zu speichern <1000000.
Nitro2k01
Tut mir leid, aber ich habe nicht bemerkt, dass die Antwort überholt ist.
Nitro2k01
@ nitro2k01, ich mache es 183 Zeichen. (Am Ende der ersten Zeile befindet sich ein Leerzeichen am Ende, und der Einzug sollte ein Leerzeichen für eine Ebene und ein Tabulator für zwei Ebenen sein.)
Peter Taylor
1

Ruby - 154 231 Zeichen

def k i,n;(l=Math).log(i,2)*l.log(i,3)*l.log(i,5)/6>n end
def l i,n;k(i,n)?[i]:[i]+l(5*i,n)end
def j i,n;k(i,n)?[i]:[i]+j(3*i,n)+l(5*i,n)end
def h i,n;k(i,n)?[i]:[i]+h(2*i,n)+j(3*i,n)+l(5*i,n)end
puts h(1,n=gets.to_i).sort.first n

Und jetzt ist es schnell genug, es gibt definitiv eine Menge Golf, die trotzdem passieren kann.

→ time echo 1000000 | ruby golf-hamming.rb | wc
1000000 1000000 64103205
echo 1000000  0.00s user 0.00s system 0% cpu 0.003 total
ruby golf-hamming.rb  40.39s user 0.81s system 99% cpu 41.229 total
wc  1.58s user 0.05s system 3% cpu 41.228 total
Nemo157
quelle
1

Perl, 94 Zeichen (aber zu langsam)

use List::Util min;
$\=$/;$h{1}=();delete$h{$_=min keys%h},print,@h{$_*2,$_*3,$_*5}=()for 1..<>

Ungolfed:

use List::Util 'min';
my %hamming;
my $up_to = <>;
$hamming{1} = (); # The value is undef, but the key exists!
for (1 .. $up_to) {
    my $next = min( keys %hamming );
    delete $hamming{$next}; # We're done with this one
    print $next, "\n";
    @hamming{ $next * 2, $next * 3, $next * 5 } = (); # Create keys for the multiples
} # Rinse, repeat

Es dauert 11 Minuten, um die ersten 100.000 Zahlen zu berechnen, und ich möchte nicht einmal über 1.000.000 nachdenken. Die ersten 10.000 werden in 3 Sekunden erledigt. es ist nur etwas, das O (n ^ 2) ähnelt :(

hobbs
quelle
1

APL (Dyalog Classic) , 34 23 Bytes

{⍺⍴{⍵[⍋⍵]}∪,⍵∘.×⍳5}⍣≡∘1

Probieren Sie es online!

n=1000000

{⍺⍴{⍵[⍋⍵]}∪,⍵∘.×⍳5}⍣≡∘1     Monadic function:
{⍺⍴{⍵[⍋⍵]}∪,⍵∘.×⍳5}         Define the following helper function g(⍺,⍵):
             ⍵∘.×⍳5             Make a multiplication table between  and (1 2 3 4 5).
                                (Including 4 is unnecessary but saves bytes.)
            ,                   Flatten the table into an array.
                               Keep unique elements.
    {⍵[⍋⍵]}                     Grade up the array and access it at those indices.
                                (This is the APL idiom to sort an array.)
 ⍺⍴                             Keep the first  elements; pad by repeating the array.
{⍺⍴{⍵[⍋⍵]}∪,⍵∘.×⍳5}⍣≡       Repeatedly apply g with some fixed left argument
                             until a fixed point is reached.
                             At this point we have a dyadic function that takes
                             n on the left and the starting value on the right,
                             and returns multiples of the n Hamming numbers.
                      1     Fix 1 as the right argument.
Lirtosiast
quelle
Durcheinander bringen spart vier:1↓0 1{⍺↑{⍵[⍋⍵]}∪,⍵∘.×⍳5}⍣≡⍨1+⊢
Adám
Zu Ihrer Information, {⍺⍴∧∪,⍵×⍀⍳5}`⍣≡∘1in Extended. (Backtick wegen Fehler benötigt.)
Adám
0

Haskell, 71

h n = drop n $ iterate (\(_,(a:t))-> (a,union t [2*a,3*a,5*a])) (0,[1])

Ausgabe

*Main> map fst $ take 20 $ h 1
[1,2,3,4,5,6,8,9,10,12,15,16,18,20,24,25,27,30,32,36]
Timtech
quelle
Die Spezifikation fordert Sie zum Drucken auf, daher sollte der zu druckende Code gezählt werden. Dies ermöglicht auch einen fairen Vergleich mit der anderen Haskell-Implementierung.
Peter Taylor
@PeterTaylor Wie viele Zeichen sollte ich Ihrer Meinung nach hinzufügen?
Timtech
0

Ursala, 103

#import std
#import nat
smooth"p" "n" = ~&z take/"n" nleq-< (rep(length "n") ^Ts/~& product*K0/"p") <1>

Ausgabe fürmain = smooth<2,3,5>* nrange(1,20)

<1,2,3,4,5,6,8,9,10,12,15,16,18,20,24,25,27,30,32,36>
Timtech
quelle
0

Mathematica, 54 Bytes

Sort[1##&@@@({2,3,5}^#&/@Tuples[0~Range~#,3])]~Take~#&

Ineffiziente aber kurze reine Funktion. Berechnet alle Produkte der Form 2^i * 3^j * 5^kfür 0 <= i, j, k <= #( #ist das erste Argument für die Funktion), dann Sorts sie und Takes nur das erste #.

Genisis
quelle
1
Irgendwie glaube ich nicht, dass 1e18-Berechnungen in weniger als einer Minute durchgeführt werden.
Jonathan Allan
-1

Japt, 15 Bytes

@_k e§5}a°X}h1ì

Versuch es

ÆJ=_k d>5}f°Jª1

Versuch es


3 Bytes

Wenn Jo Kings Ansatz als gültig angesehen wird.

o!²

Versuch es

Zottelig
quelle
Dies scheint nicht annähernd der Erfüllung der Anforderung zu entsprechen, in <1 Minute ausgeführt zu werden. (Und Jo Kings Ansatz ist nicht gültig.)
Anders Kaseorg