Setiap Kemungkinan Panjang Siklus

21

Suatu fungsi (atau program) yang mengambil input dan menyediakan output dapat dikatakan memiliki siklus jika memanggil fungsi pada outputnya sendiri berulang kali akhirnya mencapai angka aslinya. Misalnya, ambil fungsi berikut:

Input:  n    1 2 3 4 5 6
Output: f(n) 5 7 1 3 4 9

Jika kita mulai dengan n=1, f(n)=5, f(f(n))=f(5)=4, f(f(f(n)))=f(4)=3, f(f(f(f(n))))=f(3)=1.

Ini ditulis (1 5 4 3). Karena ada 4 angka unik dalam loop ini, ini adalah siklus dengan panjang 4.


Tantangan Anda adalah menulis program atau fungsi yang memiliki siklus dari setiap panjang yang memungkinkan. Artinya, harus ada siklus panjang 1, panjang 2, dan seterusnya.

Selain itu, fungsi / program Anda harus dari bilangan bulat positif ke bilangan bulat positif, dan itu harus bijective , artinya harus ada tepat satu nilai input untuk setiap nilai output yang mungkin, di atas semua bilangan bulat positif. Dengan kata lain, fungsi / program harus menghitung permutasi bilangan bulat positif.


Detail: Setiap sistem input / output standar diperbolehkan, termasuk STDIN, STDOUT, argumen fungsi, pengembalian, dll. Lubang standar dilarang.

Anda tidak perlu khawatir tentang keterbatasan tipe data Anda - properti di atas hanya perlu tahan dengan asumsi bahwa a int atau floatdapat memiliki nilai apa pun, misalnya.

Tidak ada batasan pada perilaku fungsi pada input yang bukan bilangan bulat positif, dan input / output tersebut akan diabaikan.


Skor adalah kode golf dalam byte, kode terpendek menang.

isaacg
sumber
"harus ada siklus dengan panjang 1, panjang 2, dan seterusnya" Haruskah ini diartikan sebagai "harus ada setidaknya siklus dengan panjang 1, setidaknya satu dari panjang 2, dan seterusnya" atau "harus ada menjadi persis siklus panjang 1, salah satu dari panjang 2, dan seterusnya".
Bakuriu
@ Bakuriu Setidaknya satu siklus dari setiap panjang positif.
isaacg

Jawaban:

11

Pyth, 11 8 byte

.<W-0zz1

Jauh lebih membosankan daripada jawaban saya sebelumnya.

Setiap angka yang berisi peta 0 digit untuk dirinya sendiri. Setiap nomor lain memetakan ke nomor yang digit-digitnya dirotasi oleh 1. Jadi misalnya:

1 -> 1
10 -> 10
15 -> 51 -> 15
104 -> 104
123 -> 231 -> 312 -> 123
orlp
sumber
8

Python 2, 56 55 54 byte

n=input()
a=b=1
while a+b<=n:a+=b;b+=1
print(n+~a)%b+a

Inilah 21 keluaran pertama:

[1, 3, 2, 6, 4, 5, 10, 7, 8, 9, 15, 11, 12, 13, 14, 21, 16, 17, 18, 19, 20]

Polanya jelas jika kita memecah daftar menjadi beberapa bagian seperti:

 1    2  3    4  5  6    7  8  9  10    11  12  13  14  15    16  17  18  19  20  21
[1]  [3, 2]  [6, 4, 5]  [10, 7, 8, 9]  [15, 11, 12, 13, 14]  [21, 16, 17, 18, 19, 20]
Sp3000
sumber
Sial, ini adalah pola yang juga ingin kutuju, tetapi dengan bentuk tertutup.
orlp
1
Menarik .. nilai-a mengikuti urutan A000124 . Tapi saya kira Anda sudah tahu itu: P
Kade
Perhatikan bahwa urutan ini adalah oeis.org/A066182 .
orlp
8

Pyth, 25 byte

+hK/*J/h@h*8tQ2 2tJ2%-QKJ

Ini adalah urutan yang sama dengan @ Sp3000, tetapi dengan formulir tertutup. Bentuk tertutup adalah:

M (n) = lantai ((1 + sqrt (1 + 8 * (n - 1))) / 2) B (n) = M (n) * (M (n) - 1) / 2 f (n) = B (n) + ((n - B (n) + 1) mod M (n))

orlp
sumber
5

Python3, 40 byte

n=input();print([n[1:]+n[0],n]['0'in n])

Setiap angka yang berisi peta 0 digit untuk dirinya sendiri. Setiap nomor lain memetakan ke nomor yang digit-digitnya dirotasi oleh 1. Jadi misalnya:

1 -> 1
10 -> 10
15 -> 51 -> 15
104 -> 104
123 -> 231 -> 312 -> 123
orlp
sumber
1
Déjà vu! Keren melihatnya dalam dua bahasa!
Denham Coote
3

Ruby, 22 + 1 = 23

Dengan bendera baris perintah -p, jalankan

~/(.)(.?)/
$_=$1+$'+$2

Ketika diberikan sebagai input representasi string dari angka (tanpa baris baru tertinggal), itu membuat digit pertama tetap konstan, kemudian memutar sisanya ke kiri, sehingga 1234menjadi1342 .

Ini dapat dikurangi menjadi 21 karakter dengan $_=$1+$'+$2if/(.)(.)/, tetapi mencetak peringatan.

histokrat
sumber
3

Ruby, 16 + 1 = 17

Dengan bendera baris perintah -p, jalankan

$_=$_[/.0*$/]+$`

Ini adalah fungsi yang lebih rumit daripada jawaban saya yang lain, tetapi kebetulan lebih golf (dan toleran untuk mengikuti baris baru). Dibutuhkan digit bukan nol terakhir dari input, ditambah angka nol yang tertinggal, dan memindahkannya ke awal nomor. Jadi 9010300menjadi 3009010. Angka apa pun dengan n digit bukan nol akan menjadi bagian dari siklus panjang-n.

Input adalah string dalam basis apa pun melalui STDIN, output adalah string dalam basis itu.

histokrat
sumber
2

Python, 43

The kebalikan dari fungsi Sp3000 ini , dilaksanakan secara rekursif.

f=lambda n,k=1:n>k and k+f(n-k,k+1)or n%k+1

Fungsi adalah satu siklus diikuti oleh dua siklus diikuti oleh tiga ...

(1)(2 3)(4 5 6)(7 8 9 10)(11 12 13 14 15)...

Operasi n%k+1bertindak sebagai ksiklus-pada nomor 1..k. Untuk menemukan yang tepat kuntuk digunakan, geser semuanya ke bawah k=1, lalu k=2, dan seterusnya, hingga n<=k.

Tidak
sumber
2

Pyth, 15 byte

Jawaban terpendek sejauh ini yang menggunakan operasi numerik daripada operasi string.

.|.&Q_=.&_=x/Q2

    Q                input
            /Q2      input div 2
           x   Q     that XOR input
          =          assign that to Q
         _           negate that
       .&       Q    that AND Q
      =              assign that to Q
     _               negate that
  .&                 input AND that
.|               Q   that OR Q

Efek dari fungsi ini pada representasi biner adalah memperluas blok paling kanan dari 1s ke 0 berikutnya; atau jika tidak ada 0, untuk meresetnya kembali ke 1 tunggal:

10010110100000 ↦  
10010110110000 ↦  
10010110111000 ↦  
10010110111100 ↦  
10010110111110 ↦  
10010110111111 ↦
10010110100000  

Pyth, 26 byte, varian menyenangkan

.|.&Q_h.&/Q2+Qy=.&/Q2_h.|y

    Q                           input
         /Q2                    input div 2
             Q                  input
                  /Q2           input div 2
                         yQ     twice input
                       .|  Q    that OR input
                     _h         NOT that
                .&              (input div 2) AND that
               =                assign that to Q
              y                 twice that
            +                   input plus that
       .&                       (input div 2) AND that
     _h                         NOT that
  .&                            input AND that
.|                          Q   that OR Q

Lakukan operasi di atas secara bersamaan ke semua blok 1s, bukan hanya yang paling kanan — masih menggunakan operasi bitwise dan aritmatika saja.

1000010001001 ↦
1100011001101 ↦
1110011101001 ↦
1111010001101 ↦
1000011001001 ↦
1100011101101 ↦
1110010001001 ↦
1111011001101 ↦
1000011101001 ↦
1100010001101 ↦
1110011001001 ↦
1111011101101 ↦
1000010001001
Anders Kaseorg
sumber
1

Swift 1.2, 66 byte

func a(b:Int){var c=0,t=1,n=b
while n>c{n-=c;t+=c++}
print(n%c+t)}
Input:  1,   2, 3,  4, 5, 6,   7, 8, 9, 10,   11, 12, 13, 14, 15
Output: 1,   3, 2,  5, 6, 4,   8, 9, 10, 7,   12, 13, 14, 15, 11
David Skrundz
sumber
1

Brachylog , 5 byte

∋0&|↺

Cobalah online!

Port jawaban Pyth @ orlp. Sederhana dan rapi:

∋0    % If input contains a 0 (since input is a single number, "contains" ∋ treats it as an array 
      %   of its digits, so this means "if any of input's digits are 0")
&     % Then output is the input
|     % Otherwise
↺     % Circularly shift the input once, and unify that with the output

Saya awalnya ingin port solusi Python @ Sp3000, tapi butuh 23 byte kekalahan :

⟧∋B-₁⟦++₁A≤?;A--₁;B%;A+

Cobalah online!

sundar - Pasang kembali Monica
sumber
0

JavaScript (ES6), 43 byte

f=(n,i=1,j=1)=>n>j?f(n,++i,j+i):n++<j?n:n-i
Neil
sumber
0

Matlab (189)

  function u=f(n),if(~n|n==1)u=n;else,u=n;y=factor(n);z=y(y~=2);if ~isempty(z),t=y(y~=max(y));if isempty(t),u=y(end)*2^(nnz(y)-1);else,g=max(t);e=primes(g*2);u=n/g*e(find(e==g)+1);end,end,end

  • Fungsi:

    Memetakan bilangan bulat apa pun berdasarkan faktor prima, jika jumlahnya nol atau difaktorkan menjadi 2 atau 1, jumlahnya dipetakan ke dirinya sendiri, jika tidak kita memilih faktor prima terbesar dari angka ini, maka kita menambah faktor prima berbeda yang tersisa dengan terdekat faktor prima lebih besar sampai kita mencapai angka di biggest_prime^nmana njumlah dari semua eksponen semua faktor, begitu kita mencapai jumlah itu, kita beralih ke max_prime*2^(n-1)dan kita mereproduksi siklus yang sama lagi.

Abr001am
sumber
0

Matlab (137)

  function u=h(n),if(~n|n==1)u=n;else,u=n;y=factor(n);z=y(y~=2);if~isempty(z),e=nnz(y);f=nnz(z);if(~mod(e,f)&e-f)u=n/2^(e-f);else,u=u*2;end

  • Pendekatan yang sedikit mirip, mengalikan secara bertahap angka apa pun yang tidak sama dengan {0,1,2 ^ n} 2sampai kita menemukan eksponen 2yang dapat dibagi dengan jumlah eksponen faktor prima lainnya. lalu kita beralih ke awal siklus dengan membagi 2^(sum of exponents of other primes). mati rasa lainnya dipetakan untuk diri mereka sendiri.
Abr001am
sumber