Liczby Hamminga

20

Biorąc pod uwagę dodatnią liczbę całkowitą, wypisz w kolejności tyle liczb hamujących .

Zasady:

  • Wejściowy jest dodatnia n1,000,000
  • Dane wyjściowe powinny być pierwszymi n terminami https://oeis.org/A051037
  • Czas realizacji musi wynosić <1 minutę
  • To jest ; najkrótszy kod wygrywa
grokus
źródło
2
Który cel powinna mieć odpowiedź? Golf? Najbardziej efektywny algorytm? Po prostu szukasz metod rozwiązania?
Nakilon
Przepraszamy za brak konkretów. Sam tego nie rozwiązałem, więc nie jestem pewien, czy wyznaczone przeze mnie granice są rozsądne. Proszę daj mi znać.
grokus 30.01.11
OEIS
Stephen
3
1 to liczba Hamminga, więc wydrukowanie 1 000 000 1s jest zgodne z twoimi specyfikacjami. Będzie również w porządku, tzn. Nie będzie nieuporządkowaną sekwencją. :)
Czy Ness

Odpowiedzi:

7

Haskell, 101 97 92+ | n | postacie

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

Oblicza pełny milion w 3,7 s na maszynie, na której testowałem (zmiennie więcej, jeśli naprawdę chcesz przechowywać dane wyjściowe)

Nie golfowany:

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

Wszyscy Haskell są notorycznie dobrzy w definiowaniu listy jako leniwej funkcji samej siebie, w sposób, który faktycznie działa.

JB
źródło
1
Nie otrzymujesz dodatniego parametru liczby całkowitej, który dodaje więcej rozmiaru do twojego kodu
Zhen
@Zhen Dodatni parametr liczby całkowitej to token od drugiego do ostatniego, a jego rozmiar jest zadeklarowany na zewnątrz w nagłówku.
JB
3

Znaki Python 181

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
źródło
Jak tam 181 znaków? Zapisałem to w pliku, usuwając białe znaki po h=[], używając minimalnej odległości tabulacji i podziałów pojedynczych znaków, a rozmiar pliku kończy się na 187 bajtach.
nitro2k01
1
W każdym razie ... Trivial optymalizacja: h=[1]. Podaj także liczbę bezpośrednio w kodzie źródłowym, aby zapisać znaki dla liczb <1000000.
nitro2k01
Niestety, nie rozumiem, że odpowiedź jest bardzo stara.
nitro2k01
@ nitro2k01, robię 183 znaków. (Na końcu pierwszego wiersza jest trochę spacji), a wcięcie powinno być spacją dla jednego poziomu i tabulatorem dla dwóch poziomów).
Peter Taylor
1

Rubin - 154 231 znaków

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

A teraz jest wystarczająco szybki, ale z pewnością wiele golfa może się jeszcze zdarzyć.

→ 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
źródło
1

Perl, 94 znaki (ale zbyt wolno)

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

Nie golfowany:

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

Obliczenie pierwszych 100 000 liczb zajmuje 11 minut, a ja nawet nie chcę myśleć o 1 000 000. Pierwsze 10 000 robi się w uporządkowanych 3 sekundach; to tylko coś przypominającego O (n ^ 2) :(

Hobbs
źródło
1

APL (Dyalog Classic) , 34 23 bajtów

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

Wypróbuj 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
źródło
Przemieszczanie się wokół ratuje cztery:1↓0 1{⍺↑{⍵[⍋⍵]}∪,⍵∘.×⍳5}⍣≡⍨1+⊢
Adám,
FYI, {⍺⍴∧∪,⍵×⍀⍳5}`⍣≡∘1w języku Extended. (Potrzebny jest backtick z powodu błędu.)
Adám
0

Haskell, 71

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

Wynik

*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
źródło
Specyfikacja wymaga drukowania, więc kod do wydrukowania powinien zostać policzony. Pozwala to również na uczciwe porównanie z innymi implementacjami Haskell.
Peter Taylor
@PeterTaylor Jak myślisz, ile znaków powinienem dodać?
Timtech
0

Ursala, 103

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

Wynik dlamain = 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
źródło
0

Mathematica, 54 bajty

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

Nieefektywna, ale krótka czysta funkcja. Oblicza wszystkie produkty formularza 2^i * 3^j * 5^kdla 0 <= i, j, k <= #( #jest pierwszym argumentem funkcji), a następnie Sorts je i Takes tylko pierwszy #.

ngenisis
źródło
1
Jakoś nie sądzę, że wykonanie obliczeń 1e18 nastąpi za niecałą minutę.
Jonathan Allan,
-1

Japt, 15 bajtów

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

Spróbuj

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

Spróbuj


3 bajty

Jeśli podejście Jo Kinga zostanie uznane za prawidłowe.

o!²

Spróbuj

Kudłaty
źródło
Wydaje się, że nie zbliża się to do spełnienia wymogu wykonania w <1 minutę. (I podejście Jo Kinga jest nieprawidłowe).
Anders Kaseorg