Opis problemu

Biorąc pod uwagę zestaw unikatowych, pierwszych liczb pierwszych (niekoniecznie obejmujących 2), generuj iloczyn wszystkich kombinacji pierwszych mocy tych liczb pierwszych - np. Bez powtórzeń - a także 1. Na przykład, biorąc pod uwagę zbiór {2, 3, 5, 7}, produkujesz {1, 2, 3, 5, 6, 7, 10, 14, 15, 21, 30, 35, 42, 70, 105, 210}, ponieważ:

  1  =  1
  2  =  2
  3  =  3
  5  =  5
  6  =  2 x 3
  7  =  7
 10  =  2 x 5
 14  =  2 x 7
 15  =  3 x 5
 21  =  3 x 7
 30  =  2 x 3 x 5
 35  =  5 x 7
 42  =  2 x 3 x 7
 70  =  2 x 5 x 7
105  =  3 x 5 x 7
210  =  2 x 3 x 5 x 7

Zauważ, że jeśli liczebność twojego zestawu wejściowego wynosi k, to da ci 2 ^ k członków w zestawie wyjściowym.

Zasady / warunki

1. Możesz używać dowolnego języka. Cel najmniejszej liczby znaków w kodzie źródłowym.
2. Twoje rozwiązanie musi być kompletnym programem lub pełną funkcją. Funkcja może być anonimowa (jeśli Twój język obsługuje funkcje anonimowe).
3. Twoje rozwiązanie powinno obsługiwać produkty do co najmniej 2 ^ 31. Nie przejmuj się wykryciem lub obsługą przepełnienia liczb całkowitych, jeśli masz przekazane liczby, których produkt jest zbyt wielki, aby je reprezentować. Proszę jednak podać granice swoich obliczeń.
4. Możesz zaakceptować listę lub zestaw i stworzyć listę lub zestaw. Możesz założyć, że dane wejściowe są posortowane, ale nie musisz tworzyć posortowanych danych wyjściowych.

tło

Kiedy lub dlaczego jest to przydatne? Jednym z użytecznych miejsc jest generowanie tabeli mnożników do równoległego wyścigu w algorytmie faktorowania liczb całkowitych znanym jako faktoryzacja form kwadratowych. Tam każdy nieparzysty mnożnik, który próbujesz, zmniejsza prawdopodobieństwo niepowodzenia algorytmu (w celu znalezienia współczynnika) o około 50% na twardych półpierwszych liczbach. Zatem z zestawem generujących liczb pierwszych {3, 5, 7, 11}, który wytwarza zestaw 16 próbnych mnożników do równoległego wyścigu, algorytm zawodzi około 2 ^ 16 czasu na twardych półpierwszych. Dodanie 13 do listy liczb pierwszych daje zestaw 32 próbnych mnożników, zmniejszając prawdopodobieństwo niepowodzenia do około 2 ^ –32, dając drastyczną poprawę wyniku bez dodatkowych kosztów obliczeniowych (ponieważ nawet przy dwukrotnie większej liczbie mnożników ścigających się równolegle, na średnia nadal znajduje odpowiedź w tej samej łącznej liczbie kroków).

Pure Bash, 32 bajty

eval echo \$[{1,${1// /\}*{1,}}]

Odczytuje listę wejściową (oddzieloną pojedynczą spacją) przekazaną jako argument wiersza poleceń.

Wykorzystywane są trzy różne rozszerzenia powłoki:

1. ${1// /\}*{1,}jest rozszerzenie parametr , który zastępuje w przestrzeni 2 3 5 7z }*{1,dać 2}*{1,3}*{1,5}*{1,7. \$[{1,i }]są dodawane odpowiednio na początku i na końcu, aby dać \$[{1,2}*{1,3}*{1,5}*{1,7}]. Klawisz \$[odwrotnego ukośnika pozwala uniknąć prób rozszerzenia arytmetycznego na tym etapie.
2. \$[{1,2}*{1,3}*{1,5}*{1,7}]jest rozszerzeniem nawiasów klamrowych . Ponieważ rozwijanie nawiasów zwykle odbywa się przed rozszerzaniem parametrów , musimy użyć, evalaby wymusić, aby rozszerzenie parametrów miało miejsce jako pierwsze. Wynikiem rozszerzenia nawiasu jest $[1*1*1*1] $[1*1*1*7] $[1*1*5*1] ... $[2*3*5*7].
3. $[1*1*1*1] $[1*1*1*7] $[1*1*5*1] ... $[2*3*5*7]to lista rozszerzeń arytmetycznych , które są następnie oceniane w celu uzyskania listy liczb, których potrzebujemy.

Wydajność:

$ ./comboprime.sh "2 3 5 7"
1 7 5 35 3 21 15 105 2 14 10 70 6 42 30 210
$

CJam, 13 bajtów

1aq~{1$f*+}/p

Odczytuje tablicę (np. [2 3 5 7]) Ze STDIN. Wypróbuj online.

Funkcja anonimowa miałaby taką samą liczbę bajtów:

{1a\{1$f*+}/}

Przykładowy przebieg

$ cjam <(echo '1aq~{1$f*+}/p') <<< '[]'
[1]
$ cjam <(echo '1aq~{1$f*+}/p') <<< '[2 3 5 7]'
[1 2 3 6 5 10 15 30 7 14 21 42 35 70 105 210]

Jak to działa

1a               " Push R := [1].              ";
  q~             " Read an array A from STDIN. ";
    {     }/     " For each a ∊ A:             ";
     1$f*+       "     R += { ra : r ∊ R }     ";
            p    " Print.                      ";

Haskell, 22

rozwiązaniem jest funkcja anonimowa:

map product.mapM(:[1])

przykładowe użycie:

*Main> map product.mapM(:[1]) $ [2,3,5]
[30,6,10,2,15,3,5,1]

objaśnienie:
(:[1]) jest funkcją, która po podaniu liczby xzwraca listę [x,1].
mapM(:[1])jest funkcją, która podając listę liczb odwzorowuje funkcję (:[1])nad nimi i zwraca każdy możliwy sposób wyboru elementu z każdej listy. na przykład mapM(:[1]) $ [3,4]najpierw mapuje funkcję do pobrania [[3,1] , [4,1]]. możliwe są następujące opcje [3,4](wybranie pierwszej liczby obu) [3,1] [1,4]i [1,1]dlatego zwraca [[3,4],[3,1],[1,4],[1,1]].

następnie map productodwzorowuje wszystkie opcje i zwraca ich produkty, które są pożądanym produktem wyjściowym.

ta funkcja jest polimorficzna w swoim typie, co oznacza, że ​​może działać na wszystkich typach liczb. możesz Intpodać mu listę, a wynikiem będzie lista, Intale można ją również zastosować do listy typówIntegeri zwróć listę Integer. oznacza to, że funkcja przepełnienia nie określa zachowania, ale typu danych wejściowych (ekspresyjny system typów Haskella :))

Mathematica, 18 17 bajtów

1##&@@@Subsets@#&

To anonimowa funkcja. Nazwij to jak

1##&@@@Subsets@#&[{2,3,5,7}]

Aktualizacja: C (funkcja f), 92

Nawet jako funkcja jest to wciąż najdłuższy wpis tutaj. Po raz pierwszy podałem tablicę o nieznanej długości jako argument funkcji w C i najwyraźniej nie ma możliwości, aby funkcja C wiedziała o długości przekazywanej do niej tablicy, ponieważ argument jest przekazywany jako wskaźnik ( niezależnie od użytej składni). Dlatego do podania długości wymagany jest drugi argument.

Zachowałem wyjście na standardowe wyjście, ponieważ ustawienie tablicy liczb całkowitych i zwrócenie jej prawie na pewno byłoby dłuższe.

Dzięki Dennis za wskazówki.

Zobacz funkcję f(92 znaki z wyłączeniem niepotrzebnych białych znaków) w programach testowych poniżej.

Wyjście przez printf

j;

f(int c,int*x){
  int p=1,i;
  for(i=c<<c;i--;p=i%c?p:!!printf("%d ",p))p*=(i/c>>i%c)&1?1:x[i%c];
}

main(int d,char**v){
  d--;
  int y[d];
  for(j=d;j--;)y[j]=atoi(v[j+1]);
  f(d,y);
}

Dane wyjściowe za pomocą wskaźnika tablicy

j,q[512];

f(int c,int*x,int*p){
    for(int i=-1;++i-(c<<c);p[i/c]*=(i/c>>i%c)&1?1:x[i%c])i%c||(p[i/c]=1);
}

main(int d,char**v){
  d--;
  int y[d];
  for(j=d;j--;)y[j]=atoi(v[j+1]);
  f(d,y,q);
  for(j=1<<d;j--;)printf("%d ",q[j]);
}

C (program), 108

wykluczając niepotrzebne białe znaki.

p=1,i;
main(int c,char**v){
  c-=1;
  for(i=c<<c;i--;i%c||(printf("%d ",p),p=1))(i/c>>i%c)&1||(p*=atoi(v[i%c+1]));
}

Dane wejściowe z wiersza poleceń, dane wyjściowe na standardowe wyjście. C nie wygra tutaj, ale może spróbuję przejść na funkcję jutro.

Zasadniczo iterujemy wszystkie 1<<ckombinacje liczb pierwszych, przy czym każdy fragment i/czwiązany jest z obecnością lub brakiem określonej liczby pierwszej w produkcie. „Pętla wewnętrzna” i%cprzebiega przez liczby pierwsze, mnożąc je zgodnie z wartością i/c.Gdy i%cosiągnie 0, produkt jest wyprowadzany, a następnie ustawiany na 1 dla następnej „zewnętrznej” iteracji.

co ciekawe, printf("%d ",p,p=1)nie działa (zawsze drukuje 1). To nie jest pierwszy raz, gdy widziałem dziwne zachowanie, gdy wartość jest użyta w a printfi przypisana później w tym samym nawiasie. Możliwe jest w tym przypadku, że drugi przecinek nie jest traktowany jako separator argumentów, ale raczej jako operator.

Stosowanie

$ ./a 2 3 5 7
1 2 3 6 5 10 15 30 7 14 21 42 35 70 105 210

Haskell, 27 bajtów

Jest to implementacja HJMell odpowiedzi CJam @ sudo jako funkcji anonimowej. Nie pokona niesamowitego rozwiązania Haskell @proud haskeller, ale i tak go tu zostawię.

foldr((=<<)(++).map.(*))[1]

Objaśnienie: foldr przyjmuje funkcję binarną, wartość i listę. Następnie zastępuje każdą komórkę minusy na liście przez aplikację funkcji i koniec listy o wartość, na przykład: foldr f v [a,b,c] == f a (f b (f c v)). Naszą wartością jest lista zawierająca jeden element 1, a funkcją binarną jest f = (=<<)(++).map.(*). Teraz fbierze liczbę n, tworzy funkcję, (n*)która się zwielokrotnia n, czyni z niej funkcję, g = map(n*)która stosuje tę funkcję do wszystkich elementów listy i przekazuje tę funkcję do (=<<)(++). Tutaj (++)jest funkcja konkatenacji i (=<<)jest monadycznego powiązań , które w tym przypadku odbywa się (++)i g, i daje funkcję, która pobiera w wykazie, stosujeg do jego kopii i łączy oba.

W skrócie: zacznij od [1]i dla każdego numeru nna liście wejściowej weź kopię bieżącej listy, pomnóż wszystko przez ni dołącz ją do bieżącej listy.

Python: 55 znaków

f=lambda l:l and[x*l[0]for x in f(l[1:])]+f(l[1:])or[1]

Rekurencyjnie generuje produkty, wybierając kolejno włączenie lub wyłączenie każdej liczby.

PARI / GP , 26 bajtów

v->divisors(factorback(v))

Dłuższe wersje obejmują

v->divisors(prod(i=1,#v,v[i]))

(30 bajtów) i

v->divisors(fold((x,y)->x*y,v))

(31 bajtów).

Zauważ, że jeśli dane wejściowe byłyby matrycą faktoryzacji, a nie zestawem, 18 bajtów można zapisać za pomocą divisorssamego. Ale wydaje się, że konwersja zestawu na macierz faktoryzacji zajmuje więcej niż 18 bajtów. (Czy mogę to zrobić w 39 bajtach bezpośrednio jako v->concat(Mat(v~),Mat(vectorv(#v,i,1)))lub 24 bajty przez pomnożenie i ponowne faktoring v->factor(factorback(v)), czy ktoś może zrobić lepiej?)

Szałwia - 36 34

Zasadniczo to samo co rozwiązanie Martina Büttnera , jeśli dobrze to rozumiem. Jak wspomniałem w komentarzu, równie dobrze mogę opublikować to jako odpowiedź.

lambda A:map(prod,Combinations(A))

Jest to anonimowa funkcja, którą można na przykład wywołać w następujący sposób:

(lambda A:map(prod,Combinations(A)))([2,3,5,7])

J (20)

Okazało się to dłużej, niż się spodziewałem lub oczekiwałem. Nadal: krótszy niż haskel!

*/@:^"1#:@i.@(2&^)@#

Stosowanie:

    f=:*/@:^"1#:@i.@(2&^)@#
    f 2 3 5 7
1 7 5 35 3 21 15 105 2 14 10 70 6 42 30 210

Działa to dla dowolnego zestawu liczb, nie tylko liczb pierwszych. Ponadto liczby pierwsze mogą mieć nieograniczony rozmiar, o ile tablica ma postfiks x:2 3 5 7x

05AB1E , 2 bajty

æP

Wypróbuj online!

Wyjaśnienie

æ   # powerset
 P  # product

R, 56 bajtów

r=1;for(i in 1:length(s))r=c(r,apply(combn(s,i),2,prod))

Rozważam tutaj, że s jest zestawem (i listą). Jestem pewien, że można go jeszcze skrócić. Zobaczę.

PHP, 97 bajtów

<?for(;$i++<array_product($a=$_GET[a]);){$t=$i;foreach($a as$d)$t%$d?:$t/=$d;if($t<2)echo"$i\n";}