Temukan Semua Rantai Gozinta yang Berbeda

36

Rantai Gozinta

(Terinspirasi oleh Project Euler # 606 )

Rantai gozinta untuk n adalah urutan di {1,a,b,...,n}mana setiap elemen membagi dengan benar berikutnya. Misalnya, ada delapan rantai gozinta yang berbeda untuk 12:

{1,12}, {1,2,12}, {1,2,4,12}, {1,2,6,12}, {1,3,12}, {1,3,6,12}, {1,4,12} and {1,6,12}.

Tantangan

Tulis program atau fungsi yang menerima bilangan bulat positif ( n > 1) dan mengeluarkan atau mengembalikan semua rantai gozinta yang berbeda untuk angka yang diberikan.

  1. Urutan dalam rantai penting (naik), urutan rantai tidak.
  2. Jika ada, Anda tidak dapat menggunakan builtin yang menyelesaikan tantangan.
  3. Ini adalah .

Sunting: Menghapus 1sebagai input potensial.

Payung
sumber
4
Selamat datang di PPCG. Pertanyaan pertama yang bagus!
AdmBorkBork
5
"Jika ada ([melihatmu, Mathematica!)]"
Erik the Outgolfer
3
Seperti yang dikatakan AdmBorkBork, kasus tepi biasanya ditambahkan hanya jika penting untuk inti tantangan - jika Anda ingin alasan hanya [[1]]saya akan mengatakan bahwa jika [1,1]gozinta 1maka [1,1,12]gozinta 12apa adanya [1,1,1,12]dan sekarang kita bisa tidak lagi "kembalikan semua ..."
Jonathan Allan
4
Anda harus memperjelas permainan kata dalam pertanyaan bagi mereka yang tidak mengetahuinya. 2|4dibaca "dua masuk ke empat" alias "dua gozinta empat".
mbomb007
1
Dua setengah jam bukanlah waktu yang cukup bagi kotak pasir untuk bekerja. Lihat FAQ kotak pasir .
Peter Taylor

Jawaban:

10

Python 3 , 68 65 byte

Sunting: -3 byte terima kasih kepada @notjagan

f=lambda x:[y+[x]for k in range(1,x)if x%k<1for y in f(k)]or[[x]]

Cobalah online!

Penjelasan

Setiap rantai gozinta terdiri dari nomor xdi ujung rantai, dengan setidaknya satu pembagi di sebelah kiri itu. Untuk setiap pembagi kdari xrantai [1,...,k,x]yang berbeda. Karena itu kita dapat untuk setiap pembagi kmenemukan semua rantai gozinta yang berbeda dan menambahkannya xke akhir, untuk mendapatkan semua rantai gozinta yang berbeda dengan klangsung ke kiri x. Ini dilakukan secara rekursif sampai di x = 1mana [[1]]dikembalikan, karena semua rantai gozinta mulai dengan 1, yang berarti rekursi telah mencapai titik terendah.

Kode menjadi sangat pendek karena pemahaman daftar Python memungkinkan iterasi ganda. Ini berarti bahwa nilai yang ditemukan di f(k)dapat ditambahkan ke daftar yang sama untuk semua pembagi yang berbeda k.

Halvard Hummel
sumber
sedang mencoba melakukan ini, sudah terlambat sekarang = /
Rod
3
Jawaban ini sangat cepat dibandingkan dengan yang lain sejauh ini.
ajc2000
-3 byte dengan menghapus daftar yang tidak perlu membongkar.
notjagan
7

Sekam , 13 byte

ufo=ḣ⁰…ġ¦ΣṖḣ⁰

Pendekatan yang agak berbeda dengan H.PWiz , meskipun masih dengan kekerasan. Cobalah online!

Penjelasan

Gagasan dasarnya adalah menggabungkan semua [1,...,n]urutan dan membagi hasilnya menjadi sublist di mana masing-masing elemen membagi berikutnya. Dari jumlah tersebut, kami menyimpan yang dimulai dengan 1, diakhiri dengan ndan tidak mengandung duplikat. Ini dilakukan dengan built-in "rangify" . Kemudian tetap membuang duplikat.

ufo=ḣ⁰…ġ¦ΣṖḣ⁰  Input is n=12.
           ḣ⁰  Range from 1: [1,2,..,12]
          Ṗ    Powerset: [[],[1],[2],[1,2],[3],..,[1,2,..,12]]
         Σ     Concatenate: [1,2,1,2,3,..,1,2,..,12]
       ġ¦      Split into slices where each number divides next: [[1,2],[1,2],[3],..,[12]]
 fo            Filter by
      …        rangified
   =ḣ⁰         equals [1,...,n].
u              Remove duplicates.
Zgarb
sumber
Saya kira tidak ada yang lebih pendek untuk memfilter ke array di powerset di mana setiap angka membagi yang berikutnya?
ETHproduksi
@ ETHproduksi Tidak, itu satu byte lebih lama .
Zgarb
5

Jelly , 9 8 byte

ÆḌ߀Ẏ;€ȯ

Cobalah online!

Menggunakan teknik yang mirip dengan jawaban Japt saya , dan karenanya berjalan sangat cepat pada kasus uji yang lebih besar.

Bagaimana itu bekerja

ÆḌ߀Ẏ;€ȯ    Main link. Argument: n (integer)
ÆḌ          Yield the proper divisors of n.
       ȯ    If there are no divisors, return n. Only happens when n is 1.
  ߀        Otherwise, run each divisor through this link again. Yields
            a list of lists of Gozinta chains.
    Ẏ       Tighten; bring each chain into the main list.
     ;€     Append n to each chain.
Produksi ETH
sumber
4

Mathematica, 77 byte

FindPath[Graph@Cases[Divisors@#~Subsets~{2},{m_,n_}/;m∣n:>m->n],1,#,#,All]&

Membentuk a di Graphmana simpul adalah Divisorsdari input #, dan ujung-ujungnya mewakili pembagian yang tepat, kemudian menemukan Alljalur dari titik 1ke titik #.

ngenisis
sumber
1
Woah, ini cukup pintar!
JungHwan Min
3

Jelly , 12 byte

ŒPµḍ2\×ISµÐṀ

Tautan monadik yang menerima bilangan bulat dan mengembalikan daftar daftar bilangan bulat.

Cobalah online!

Bagaimana?

Kami ingin semua daftar bilangan bulat unik yang diurutkan antara satu dan N sedemikian rupa sehingga yang pertama adalah satu, yang terakhir adalah N, dan semua pasangan dibagi. Kode mencapai filter ini dengan memeriksa kriteria pembagian pasangan-bijaksana puas atas set daya rentang yang dimaksud, tetapi hanya memilih mereka dengan jumlah maksimum perbedaan inkremental (yang dimulai dengan satu dan berakhir dengan N akan memiliki sejumlah perbedaan inkremental N-1, yang lain akan memiliki lebih sedikit).

ŒPµḍ2\×ISµÐṀ - Link: number N
ŒP           - power-set (implicit range of input) = [[1],[2],...,[N],[1,2],[1,3],...,[1,N],[1,2,3],...]
          ÐṀ - filter keep those for which the result of the link to the left is maximal:
  µ      µ   - (a monadic chain)
    2\       -   pairwise overlapping reduce with:
   ḍ         -     divides? (1 if so, 0 otherwise)
       I     -   increments  e.g. for [1,2,4,12] -> [2-1,4-2,12-4] = [1,2,8]
      ×      -   multiply (vectorises) (no effect if all divide,
             -                          otherwise at least one gets set to 0)
        S    -   sum         e.g. for [1,2,4,12] -> 1+2+8 = 11 (=12-1)
Jonathan Allan
sumber
Tunggu ada pengurangan yang tumpang tindih n-bijaksana? : o bagaimana saya tidak pernah melihat bahwa: PI menggunakan <slice>2<divisible>\<each>: P
HyperNeutrino
Menggunakan perubahan terbaru ke quick Jelly, Anda dapat menggunakan Ɲsebagai ganti `2` untuk 11 byte .
Tn. Xcoder
3

Japt , 17 byte

⬣ßX m+S+UR÷ª'1

Uji secara online!

Anehnya, menghasilkan output sebagai string jauh lebih mudah daripada menghasilkannya sebagai array array ...

Penjelasan

 ⬠£  ßX m+S+URà ·  ª '1
Uâq mX{ßX m+S+UR} qR ||'1   Ungolfed
                            Implicit: U = input number, R = newline, S = space
Uâ                          Find all divisors of U,
  q                           leaving out U itself.
    mX{         }           Map each divisor X to
       ßX                     The divisor chains of X (literally "run the program on X")
          m    R              with each chain mapped to
           +S+U                 the chain, plus a space, plus U.
                  qR        Join on newlines.
                     ||     If the result is empty (only happens when there are no factors, i.e. U == 1)
                       '1     return the string "1".
                            Otherwise, return the generated string.
                            Implicit: output result of last expression
Produksi ETH
sumber
Jadi, apakah pendekatan Anda menghindari pembuatan rantai yang tidak valid kemudian memfilternya, seperti yang dilakukan pendekatan lain?
Payung
@Umbrella Tidak, itu hanya menghasilkan yang valid, satu pembagi sekaligus, maka mengapa ia bekerja secepat kilat bahkan pada kasus-kasus seperti 12000 :-)
ETHproduksi
Penggunaan rekursi yang sangat bagus :) Dan saya melakukan ¬trik itu! : p
Shaggy
@Shaggy ¬adalah salah satu alasan mengapa saya telah mengimplementasikan banyak fungsi yang pada dasarnya "melakukan X tanpa argumen, atau Y diberi argumen yang benar": P
ETHproduk
3

Mathematica, 60 byte

Cases[Subsets@Divisors@#,x:{1,___,#}/;Divisible@@Reverse@{x}]&

Penggunaan bentuk multi-arg tak tercatat dari Divisible, di mana Divisible[n1,n2,...]pengembalian Truejika n2∣n1, n3∣n2dan sebagainya, dan Falsesebaliknya. Kami mengambil semua Subsetsdari daftar Divisorsinput #, kemudian kembali Casesdari bentuk {1,___,#}sehingga Divisiblememberikan Trueuntuk Reversed urutan pembagi.

ngenisis
sumber
Jadi, Divisibleapakah pada dasarnya adalah builtin untuk memverifikasi rantai gozinta?
Payung
@Umbrella Ini tidak memeriksa pembagian yang tepat.
ngenisis
3

Haskell, 51 byte

f 1=[[1]]
f n=[g++[n]|k<-[1..n-1],n`mod`k<1,g<-f k]

Secara rekursif menemukan rantai gozinta pembagi yang tepat dan tambahkan n.

Cobalah online!

Sievers Kristen
sumber
Saya merasa harus ada kredit ekstra untuk penanganan yang tepat 1. Karena secara kolektif kami memutuskan untuk dibebaskan 1, dapatkah Anda menghemat 10 byte dengan menghapus kasing itu?
Payung
@Umbrella 1bukan kasus khusus untuk algoritma ini, diperlukan sebagai kasus dasar untuk rekursi. Dengan sendirinya, persamaan pendefinisian kedua hanya dapat mengembalikan daftar kosong.
Christian Sievers
Saya melihat. Solusi saya (belum diposkan) juga digunakan [[1]]sebagai basis.
Payung
3

Haskell (Lambdabot), 92 85 byte

x#y|x==y=[[x]]|1>0=(guard(mod x y<1)>>(y:).map(y*)<$>div x y#2)++x#(y+1)
map(1:).(#2)

Kebutuhan Lambdabot Haskell sejak guardmembutuhkan Control.Monadharus diimpor. Fungsi utama adalah fungsi anonim, yang saya diberitahu diizinkan dan memangkas beberapa byte.

Terima kasih kepada Laikoni karena telah menghemat tujuh byte.

Penjelasan:

Monad sangat berguna.

x # y

Ini adalah fungsi rekursif kami yang melakukan semua pekerjaan yang sebenarnya. xadalah angka yang kita akumulasikan (produk dari pembagi yang tetap dalam nilainya), dan ymerupakan angka berikutnya yang harus kita coba bagi ke dalamnya.

 | x == y = [[x]]

Jika xsama ymaka kita sudah selesai berulang. Cukup gunakan xsebagai akhir dari rantai gozinta saat ini dan kembalikan.

 | 1 > 0 =

Haskell golf-isme untuk "True". Artinya, ini adalah kasus default.

(guard (mod x y < 1) >>

Kami beroperasi di dalam daftar monad sekarang. Dalam daftar monad, kami memiliki kemampuan untuk membuat banyak pilihan sekaligus. Ini sangat membantu ketika menemukan "semua kemungkinan" dari sesuatu dengan kelelahan. The guardpernyataan mengatakan "hanya mempertimbangkan pilihan berikut jika kondisi benar". Dalam hal ini, hanya pertimbangkan pilihan berikut jika ymembelah x.

(y:) . map (y *) <$> div x y#2)

Jika ymemang memecah x, kami memiliki pilihan untuk menambahkan yke rantai gozinta. Dalam hal ini, secara rekursif panggilan (#), mulai lagi dari awal di y = 2dengan xsama dengan x / y, karena kita ingin "faktor luar" yang ykita hanya ditambahkan ke rantai. Lalu, apa pun hasil dari panggilan rekursif ini, gandakan nilainya dengan yang ybaru saja kami ypertimbangkan dan tambahkan ke rantai gozinta secara resmi.

++

Pertimbangkan pilihan berikut juga. Ini hanya menambahkan dua daftar bersama, tetapi secara monadis kita dapat menganggapnya sebagai mengatakan "pilih antara melakukan hal ini ATAU hal lain ini".

x # (y + 1)

Opsi lainnya adalah terus berulang dan tidak menggunakan nilainya y. Jika ytidak membagi xmaka ini adalah satu-satunya pilihan. Jika ytidak membagi xmaka opsi ini akan diambil serta opsi lainnya, dan hasilnya akan digabungkan.

map (1 :) . (# 2)

Ini adalah fungsi utama gozinta. Itu memulai rekursi dengan memanggil (#)dengan argumennya. A 1ditambahkan ke setiap rantai gozinta, karena (#)fungsi tidak pernah menempatkan orang ke dalam rantai.

Silvio Mayolo
sumber
1
Penjelasan hebat! Anda dapat menyimpan beberapa byte dengan meletakkan penjaga pola semua dalam satu baris. mod x y==0dapat disingkat menjadi mod x y<1. Karena fungsi anonim diizinkan, fungsi utama Anda dapat ditulis sebagai pointfree map(1:).(#2).
Laikoni
3

Haskell, 107 100 95 byte

f n=until(all(<2).map head)(>>=h)[[n]]
h l@(x:_)|x<2=[l]|1<2=map(:l)$filter((<1).mod x)[1..x-1]

Mungkin ada kondisi terminasi yang lebih baik (mencoba sesuatu seperti

f n=i[[n]]
i x|g x==x=x|1<2=i$g x
g=(>>=h)

tapi ini lebih lama). Pemeriksaan untuk 1tampaknya bijaksana karena menggosok ulangi 1s atau duplikat ( nubtidak dalam Prelude) lebih banyak byte.

Cobalah online.

Leif Willerts
sumber
3
(>>=h)untuk(concatMap h)
Michael Klein
95 byte
Cristian Lupascu
u
Aduh,
3

JavaScript (Firefox 30-57), 73 byte

f=n=>n>1?[for(i of Array(n).keys())if(n%i<1)for(j of f(i))[...j,n]]:[[1]]

Nyaman n%0<1itu salah.

Neil
sumber
2

Jelly , 17 byte

ḊṖŒP1ppWF€ḍ2\Ạ$Ðf

Cobalah online!

Erik the Outgolfer
sumber
Itu sangat cepat. Namun, hasil Anda 1tidak terduga. Saya belum berhasil menemukan hasil yang pasti 1, tetapi saya berasumsi demikian [[1]]. Saya tidak bisa mengatakan dengan pasti bahwa [1,1]itu tidak benar kecuali bahwa semua hasil lainnya meningkatkan urutan. Pikiran?
Payung
@Umbrella Anda mungkin ingin membiarkan jawaban melakukan apa saja untuk 1.
Mr. Xcoder
@Umbrella Jika itu masalah, saya bisa memperbaikinya untuk +2 (ganti ;€dengan ;Q¥€).
Erik the Outgolfer
2

Mathematica, 104 byte

(S=Select)[Rest@S[Subsets@Divisors[t=#],FreeQ[#∣#2&@@@Partition[#,2,1],1>2]&],First@#==1&&Last@#==t&]&
J42161217
sumber
FreeQ[...]bisa menjadiAnd@@BlockMap[#∣#2&@@#&,#,2,1]
JungHwan Min
sangat bagus! tapi saya mendapatkan pesan tambahan DeveloperPartitionMap :: nlen: - Teks pesan tidak ditemukan - >> `kenapa begitu?
J42161217
BlockMapmenggunakan Developer`PartitionMapfungsi secara internal, tetapi karena ini adalah fungsi pengembang, ia tidak memiliki pesan kesalahan. Kesalahan ini disebabkan oleh daftar yang memiliki 1 atau 0 elemen, yang Anda tidak dapat membuat 2-partisi dengan.
JungHwan Min
2

Mathematica, 72 byte

Cases[Subsets@Divisors@#,{1,___,#}?(And@@BlockMap[#∣#2&@@#&,#,2,1]&)]&

Penjelasan

Divisors@#

Temukan semua pembagi input.

Subsets@ ...

Hasilkan semua himpunan bagian dari daftar itu.

Cases[ ... ]

Pilih semua kotak yang sesuai dengan pola ...

{1,___,#}

Dimulai dengan 1 dan berakhir dengan <input>...

?( ... )

dan memenuhi syarat ...

And@@BlockMap[#∣#2&@@#&,#,2,1]&

Elemen kiri membagi elemen kanan untuk semua 2-partisi daftar, offset 1.

JungHwan Min
sumber
2

TI-BASIC, 76 byte

Input N
1→L1(1
Repeat Ans=2
While Ans<N
2Ans→L1(1+dim(L1
End
If Ans=N:Disp L1
dim(L1)-1→dim(L1
L1(Ans)+L1(Ans-(Ans>1→L1(Ans
End

Penjelasan

Input N                       Prompt user for N.
1→L1(1                        Initialize L1 to {1}, and also set Ans to 1.

Repeat Ans=2                  Loop until Ans is 2.
                              At this point in the loop, Ans holds the
                              last element of L1.

While Ans<N                   While the last element is less than N,
2Ans→L1(1+dim(L1              extend the list with twice that value.
End

If Ans=N:Disp L1              If the last element is N, display the list.

dim(L1)-1→dim(L1              Remove the last element, and place the new
                              list size in Ans.

L1(Ans)+L1(Ans-(Ans>1→L1(Ans  Add the second-to-last element to the last
                              element, thereby advancing to the next
                              multiple of the second-to-last element.
                              Avoid erroring when only one element remains
                              by adding the last element to itself.

End                           When the 1 is added to itself, stop looping.

Saya bisa menyimpan 5 byte lagi jika diizinkan keluar dengan kesalahan alih-alih dengan anggun, dengan menghapus centang Ans> 1 dan kondisi loop. Tapi saya tidak yakin itu diizinkan.

calc84maniac
sumber
Apakah Anda memasukkan ini ke dalam kalkulator? Karena itu tak terduga dan agak mengesankan.
Payung
Ya! Bagian rumit tentang TI-BASIC adalah bahwa hanya ada variabel global, jadi saya harus menggunakan daftar itu sendiri sebagai tumpukan rekursi saya.
calc84maniac
2

Mathematica 86 77 Bytes

Select[Subsets@Divisors@#~Cases~{1,___,#},And@@BlockMap[#∣#2&@@#&,#,2,1]&]&

Brute force menurut definisi.

Berharap ada cara yang lebih pendek untuk melakukan perbandingan elemen berurutan dari daftar.

Terima kasih kepada @Jenny_mathy dan @JungHwanMin untuk saran menghemat 9 byte

Kelly Lowder
sumber
1
Anda dapat menggunakan FreeQ[#∣#2&@@@Partition[#,2,1],1>2]&](sebagai argumen kedua) untuk menuju ke 82 byte
J42161217
@Jenny_mathy Atau lebih baik,And@@BlockMap[#∣#2&@@#&,#,2,1]
JungHwan Min
1

Sekam , 17 16 byte

-1 byte, terima kasih kepada Zgarb

foEẊ¦m`Je1⁰Ṗthḣ⁰

Cobalah online!

H.Piz
sumber
Pendek, tapi lambat. Saya memasukkan 50input dan waktunya habis. Apa inti dari pendekatan Anda?
Payung
Ini pada dasarnya mencoba semua rantai yang mungkin dan mengambil yang cocok dengan spec
H.PWiz
@Umbrella TIO memiliki batas waktu 60 detik, itu bukan kesalahan program.
Erik the Outgolfer
o`:⁰:1dapat`Je1⁰
Zgarb
@Zgarb Sekali lagi ...
H.PWiz
0

PHP 147 141

Diedit untuk menghapus tes yang berlebihan

function g($i){$r=[[1]];for($j=2;$j<=$i;$j++)foreach($r as$c)if($j%end($c)<1&&$c[]=$j)$r[]=$c;foreach($r as$c)end($c)<$i?0:$R[]=$c;return$R;}

Dijelaskan:

function g($i) {

15 karakter boilerplate :(

    $r = [[1]];

Init hasil ditetapkan [[1]]sebagai setiap rantai dimulai dengan 1. Ini juga mengarah ke dukungan untuk 1 sebagai input.

    for ($j = 2; $j <= $i; $j++) {
        foreach ($r as $c) {
            if ($j % end($c) < 1) {
                $c[] = $j;
                $r[] = $c;
            }
        }
    }

Untuk setiap nomor dari 2 sampai $i, kita akan memperpanjang rantai masing-masing di set kami dengan jumlah saat ini jika itu gozinta , kemudian, menambahkan rantai diperpanjang untuk hasil yang ditetapkan kami.

    foreach ($r as $c) {
        end($c) < $i ? 0 : $R[] = $c;
    }

Saring rantai perantara kami yang tidak berhasil $i

    return $R;
}

10 karakter boilerplate :(

Payung
sumber
-1

Mathematica

f[1] = {{1}};
f[n_] := f[n] = Append[n] /@ Apply[Join, Map[f, Most@Divisors@n]]

Jawaban di-cache untuk panggilan tambahan.

Batang
sumber
1
Selamat datang di situs ini! Ini adalah kode-golf sehingga Anda harus memasukkan jumlah byte Anda dan sebagai tambahan upaya untuk menghapus semua spasi tambahan, yang saya kira Anda memiliki beberapa.
Wheat Wizard