Apa Aneh Fungsi

45

Tugas Anda di sini adalah untuk mengimplementasikan fungsi 1 yang membentuk permutasi pada bilangan bulat positif (A pemilihan dari bilangan bulat positif ke diri mereka sendiri). Ini berarti bahwa setiap bilangan bulat positif akan muncul tepat sekali dalam permutasi. Tangkapannya adalah fungsi Anda harus memiliki probabilitas lebih besar untuk menghasilkan angka ganjil daripada angka genap.

Sekarang ini mungkin tampak aneh atau tidak mungkin. Tentunya ada angka ganjil sebanyak angka genap? Dan sementara intuisi ini benar untuk set yang terbatas itu sebenarnya tidak berlaku untuk set yang tak terbatas. Sebagai contoh, ambil permutasi berikut:

1 3 2 5 7 4 9 11 6 13 15 8 17 19 10 21 23 12 25 27 14 29 31 16 33 35 18 37 39 20 41 43 22 45 47 24 49 51 26 53 55 ...

Jika Anda mengambil subbagian dari urutan dengan ukuran lebih besar dari Anda akan memiliki setidaknya angka ganjil sebagai angka genap, dengan demikian tampaknya probabilitas dari setiap istilah acak ganjil lebih besar daripada kemungkinan genap. Anda juga akan mencatat setiap nomor ganjil atau genap akhirnya akan muncul dalam urutan dan hanya dapat muncul sekali. Dengan demikian urutannya adalah permutasi sejati.1

Definisi Peluang

Untuk menghindari kebingungan atau ambiguitas, saya akan menjabarkan dengan jelas apa yang dimaksud dengan probabilitas dalam pertanyaan ini.

Katakanlah kita memiliki fungsi . Probabilitas bilangan ganjil akan didefinisikan sebagai batas rasio anggota ganjil dari himpunan ke ukuran himpunan karena cenderung menuju infinity.ff{1n}n

limn|{x:x{1n},odd(f(x))}|n

Misalnya fungsi yang disebutkan di atas akan memiliki kemungkinan ganjil 2/3 .


Ini adalah sehingga jawaban akan dinilai dalam byte dengan lebih sedikit byte lebih baik.


Tantangan Ekstra

Berikut adalah beberapa ide yang menyenangkan untuk diajak bermain dan mungkin mencoba untuk diterapkan. Ini hanya untuk bersenang-senang dan tidak mempengaruhi penilaian dengan cara apa pun. Beberapa di antaranya bahkan bukan solusi yang valid untuk tantangan ini, dan jawaban yang hanya mencakup solusi untuk tantangan 2 atau 3 bukanlah jawaban yang valid, dan dapat dihapus .

  • Tulis permutasi dengan probabilitas ganjil 1 . (ini mungkin)

  • Tulis permutasi yang memiliki angka ganjil lebih banyak daripada angka genap dalam untuk apa pun tetapi memiliki probabilitas ganjil .f{1n}n1/2

  • Tulis permutasi yang tidak memiliki probabilitas yang ditentukan (yaitu tidak ada batasan).


1: Di sini fungsi berarti program atau fungsi. Itu hanya sepotong kode yang mengambil input dan menghasilkan output.

Wisaya Gandum
sumber

Jawaban:

22

Jelly , 7 byte

Æf^<¥4P

Swap 2 detik dan 3 detik dalam faktorisasi utama input. Probabilitas odds adalah 2/3 .

Cobalah online!

Bagaimana itu bekerja

Æf^<¥4P  Main link. Argument: n

Æf       Compute all prime factors of n, with duplicates.
    ¥4   Combine the two links to the left into a dyadic chain and call it with
         right argument 4.
   <       Compare each prime factor with 4. Yields 1 for 2 and 3, 0 otherwise.
  ^        Bitwise XOR the results with the corresponding prime factors.
         This maps 2 to 3, 3 to 2, and all other primes to themselves.
      P  Take the product of the resulting primes.
Dennis
sumber
Jawaban ini cukup pintar. Saya percaya saya mengerti mengapa ini bekerja tetapi Anda mungkin ingin memasukkan bukti bahwa itu berhasil karena saya menemukannya tidak intuitif pada awalnya.
Wheat Wizard
6
Bukti bahwa ini adalah permutasi: fungsi adalah kebalikannya sendiri. Proof of ratio: kemungkinan outputnya aneh adalah peluang bahwa aslinya tidak memiliki faktor 3, yang tepatnya ketika tidak dibagi tiga. Kesempatan itu adalah 2/3.
tommeding
15

Sekam , 11 10 byte

-1 byte terima kasih kepada Leo, dan fungsinya yang sedikit berbeda

Ini memiliki probabilitas aneh 1

!uΣz:NCNİ1

Cobalah online!

Itu mengindeks urutan:

[1,2,3,5,7,9,11,4,13,15,17,19,21,23,25,27,29,6,31,33]
1 odd, 1 even, 5 odd, 1 even, 9 odd, 1 even, 13 odd...

Penjelasan

!               Index the following sequence (1-indexed)
 u              remove duplicates                     [1,2,3,5,7,9,11,4,13,15...]
  Σ              Concatenate                          [1,1,2,3,5,3,7,9,11,4,13..]
   z:            Zipwith append                       [[1,1],[2,3,5],[3,7,9,11]..
     N          Natural numbers
      CNİ1      Odd numbers cut into lists of lengths [[1],[3,5],[7,9,11]...]
                corresponding to the Natural numbers
H.Piz
sumber
1
Bisakah Anda menjelaskan fungsinya?
Wheat Wizard
1 byte lebih sedikit dengan menggunakan nub: tio.run/##yygtzv6vkFuce3jboeX6PsqqRrmPmhof7lhcdGjbf8XSc4urrPyc/…
Leo
8

Haskell, 35 34 32 byte

f n=n:2*n+1:2*n+3:f(n+2)
(f 0!!)

Menerapkan urutan contoh [1,3,2,5,7,4,9,11,6,13,15,8,17,19,10,21,...].

Cobalah online!

Untuk referensi: versi lama, 34 byte (-1 byte terima kasih kepada @xnor):

(!!)$do e<-[0,2..];[e,2*e+1,2*e+3]

Cobalah online!

nimi
sumber
Simpan paren:(!!)$do ...
xnor
8

Sekam , 8 byte

!uΣzeİ1N

Cobalah online!

Ini mengimplementasikan contoh urutan ( 1,3,2,5,7,4...).

Penjelasan

!uΣzeİ1N
   ze       zip together
     İ1       the odd numbers
       N      with the natural (positive) numbers
  Σ         flatten the resulting list
 u          remove duplicates
!           index into the obtained sequence with the input
Leo
sumber
7

Semua orang melakukan Tantangan 1, jadi mari kita lakukan dua lainnya.

Perl 6 , 26 byte - Tantangan 2

{($_==1)+$_-(-1)**($_%%2)}

Cobalah online!

Hanya saja 1 3 2 5 4 7 6...Dalam jumlah genap, selalu ada 2 angka ganjil daripada genap. Dalam jumlah ganjil, 1 lagi. Namun ini jelas memiliki batas (n+2)/(2n+2) -> ½.


Perl 6 , 70 byte - Tantangan 3

{((1,),(2,4),->@a,@ {@(map(@a[*-1]+2*(*+1),^(4*@a)))}...*).flat[$_-1]}

Cobalah online!

Harus diakui, ini adalah golf yang mengerikan. Itu indeks urutan yang berisi 2⁰ angka ganjil, lalu 2¹ genap, kemudian 2² ganjil, lalu 2³ genap, dan sebagainya.

Probabilitas setelah n "blok" demikian, jika n ganjil, adalah (2⁰ + 2² + 2⁴ + ... + 2ⁿ⁻¹) / (2ⁿ-1). Jumlah dalam pembilang sama dengan ⅓ (4 ½ (n + 1) - 1) = ⅓ (2 n + 1 - 1). Jadi probabilitas setelah jumlah ganjil blok adalah ⅔ (dalam batas).

Jika kita menambahkan satu blok lagi (dan menghitungnya genap n + 1), bagaimanapun, kami tidak menambahkan angka ganjil (pembilang tetap sama) tetapi sekarang ada (2 n + 1 - 1) angka dalam total . Tanda kurung dibatalkan dan kami mendapatkan probabilitas ⅓ (dalam batas).

Ini tampaknya seharusnya memiliki 2 titik kluster yang berbeda, ⅓ dan ⅔, untuk memastikan bahwa batasnya tidak ada, tetapi ini tidak benar-benar membuktikannya. Upaya saya untuk melakukan bukti yang kuat dan kuat dapat ditemukan dalam jawaban Math.SE ini: https://math.stackexchange.com/a/2416990/174637 . Kesalahan memukul disambut.


Perl 6 , 39 byte - Tantangan inti.

{my$l=$_ div 3;$_%3??2*($_-$l)-1!!2*$l}

Cobalah online!

Meskipun saya memposting jawaban ini karena tantangan 2 dan 3 yang menawarkan teka-teki matematika kecil yang menyenangkan, ada persyaratan ketat untuk semua jawaban berisi solusi untuk tantangan inti. Ini dia.

Ini adalah contoh urutannya.

Ramillies
sumber
2
Ini adalah tantangan ekstra . Agar ini menjadi jawaban yang valid, Anda harus memberikan solusi untuk tantangan inti. Solusi untuk tantangan 1 juga merupakan solusi untuk tantangan inti, tetapi solusi untuk tantangan 2 atau 3 tidak.
Peter Taylor
1
Nah, tantangan ekstra adalah hal yang menarik pada pertanyaan ini bagi saya. Tantangan intinya bukan. Tapi saya menambahkan beberapa solusi.
Ramillies
Saya meminta bukti bahwa respons Anda terhadap Tantangan 3 tidak memiliki batasan dalam pertanyaan Math.SE ini: math.stackexchange.com/questions/2416053/…
Kevin
@ Kevin, terima kasih sudah bertanya. Saya pikir saya mungkin telah membingungkan Anda. Saya cukup yakin itu baik-baik saja. Satu-satunya hal adalah saya sering membuktikan hal-hal yang cukup keras untuk diri saya sendiri, hanya untuk ketenangan pikiran (karena kaki Anda mungkin tergelincir dengan mudah, terutama ketika menangani benda tak terbatas seperti ini) - dan saya belum melakukannya di sini. Itu semua yang ingin saya katakan.
Ramillies
1
@ Kevin - jadi setelah semua, saya mengatasi kemalasan saya (tindakan heroik!) Dan membuat buktinya. Saya mempostingnya sebagai jawaban untuk pertanyaan Math.SE Anda. Semoga tidak apa-apa (melakukan pekerjaan seperti ini di malam hari sebenarnya bukan ide yang bagus :—)). Ternyata itu hampir tidak mengerikan seperti yang saya pikirkan.
Ramillies
5

Brain-Flak , 120 byte

(({})<{{({}[()]<({}(()[{}]))>)}{}({}[({})]<({}<>{}<({}())>)><>)}>)<>({}[()]){{}((<>{}<>[{}]){}[()])<>}{}{(({}){})<>{}}<>

Cobalah online!

Lakukan fungsi berikut:

fungsi

Fungsi ini menghasilkan urutan

2 4 1 6 3 5 7 8 9 11 13 15 17 19 21 10 23 25 27 29...

Fungsi ini memiliki probabilitas ganjil 1

0 '
sumber
4

R, 82 byte (Tantangan ekstra 1)

f<-function(n){if(sqrt(n)==floor(sqrt(n))){2*sqrt(n)}else{2*(n-floor(sqrt(n)))-1}}

Cobalah secara Online!

Jika input adalah kuadrat sempurna, berikan angka genap. Kalau tidak, berikan nomor ganjil. Kotak yang sempurna memiliki kepadatan alami 0, yang berarti bahwa urutan ini memberikan angka ganjil dengan probabilitas 1.

KSmarts
sumber
Bisakah Anda menambahkan tautan TIO ?
H.PWiz
1
58 bytes
Giuseppe
56 byte
Giuseppe
53 byte
Giuseppe
3

C (gcc) , 29 byte

f(n){return n&3?n+n/2|1:n/2;}

Cobalah online!

Setiap angka keempat genap:

1 3 5   7 9 11   13 15 17   19 21 23   25 27 29
      2        4          6          8          10

Tantangan ekstra 1, 52 byte

f(n,i){for(i=0;n>>i/2;i+=2);return n&n-1?2*n-i-1:i;}

Cobalah online!

Mengembalikan 2 * (x + 1) jika n sama dengan 2 x dan angka ganjil berturut-turut sebaliknya:

    1   3 5 7   9 11 13 15 17 19 21    23 25
2 4   6       8                     10      
nwellnhof
sumber
3

Brain-Flak , 140 138 136 byte

({}<(((()())()()))((<>[()])[()()])>){({}[()]<(({}(({}({}))[({}[{}])]))[({}[{}])]<>(({}(({}({}))[({}[{}])]))[({}[{}])])<>)>)}{}({}<{}{}>)

Cobalah online!

Penjelasan

Ini melakukan fungsi yang mirip dengan yang disarankan dalam pertanyaan.

2 3 1 4 7 5 6 11 9 8 15 13 10 17 15 ...

Sebagian besar kerjanya berdasarkan potongan yang saya buat untuk menggulung tumpukan untuk tumpukan ukuran 3.

(({}(({}({}))[({}[{}])]))[({}[{}])])

Kami menyiapkan dua tumpukan satu dengan nilai akumulator (dua bahkan ganjil genap) dan satu dengan angka 4 4 2. Setiap iterasi kami menggulung kedua tumpukan dan menambahkan bagian atas tumpukan kiri ke atas tumpukan kanan.

(({}(({}({}))[({}[{}])]))[({}[{}])]<>(({}(({}({}))[({}[{}])]))[({}[{}])])<>)

Ini akan menambah setiap angka ganjil dengan 4 dan angka genap oleh 2. Saat kita mengulanginya, kita mendapatkan pola 2 ganjil 1, dengan setiap bilangan bulat positif dipukul. Jadi kita hanya mengulang nkali dengan nmenjadi input. Ini memiliki probabilitas asimtotik 2/3 .

Wisaya Gandum
sumber
2

Jelly , 10 byte

ÆE;0ṭ2/FÆẸ

Probabilitas odds adalah 2/3 .

Cobalah online!

Bagaimana itu bekerja

ÆE;0ṭ2/FÆẸ  Main link. Argument: n

ÆE          Compute the exponents of n's prime factorization.
  ;0        Append a 0.
     2/     Reduce all pairs by...
    ṭ         tack, appending the left argument to the right one.
            This inverts all non-overlapping pairs of exponents.
       F    Flatten the result.
        ÆẸ  Consider the result a prime factorization and compute the corresponding
            integer.
Dennis
sumber
1

C, 80 byte

#define R if(k++==n)return
i,j,k;f(n){for(i=k=1,j=2;;i+=4,j+=2){R i;R i+2;R j;}}

Implementasi contoh permutasi dari pertanyaan.

Cobalah online!

Steadybox
sumber
1

Batch, 36 byte

@cmd/cset/an=%1*2,(-~n*!!(n%%3)+n)/3

Menerapkan urutan yang diberikan dalam pertanyaan.

Neil
sumber
1

JavaScript, 23 byte

n=>n/2+n/2%2+(n%4&&n-1)

Output: 1, 3, 5, 2, 7, 9, 11, 4, 13, 15, 17, 6, 19, 21, 23, 8 ...

  • Untuk semua n = 4k:
    • f (n) = n / 2 = 2k
  • Untuk semua n = 4k + b
    • f (n) = n / 2 + b / 2 + n - 1 = 3/2 * (4k + b) + 1/2 * b - 1 = 6k + 2b - 1

Tantangan 2:

n=>n^(n>1)

Output: 1, 3, 2, 5, 4, 7, 6, 9, 8, 11, 10, 13, 12, 15, 14

tsh
sumber
n=>n%4?1.5*n|1:n/2lebih pendek 5 byte.
nwellnhof
1

CJam (21 byte)

{2b_(&!\_,2*\1$~+2b?}

Demo online menunjukkan 32 output pertama. Ini adalah blok anonim (fungsi).

Ini juga merupakan solusi untuk menantang 1: angka-angka yang dipetakan ke angka genap adalah kekuatan 2, sehingga kepadatan angka genap dalam output n pertama adalah lg (n) / n yang cenderung nol.

Pembedahan

{         e# Declare a block; let's call the input x
  2b      e#   Convert to base 2
  _(&     e#   Copy, pull out first digit (1) and set intersection with rest
  !       e#   Boolean not, so empty set (i.e. power of 2) maps to 1 and non-empty
          e#   to 0
  \_,2*   e#   Take another copy, find its length, and double it
  \1$~+   e#   Take the original base 2 array and append ~(2L) = -2L-1
  2b      e#   Convert from base 2, to get 2x-2L-1
  ?       e#   Take the 2L if it was a power of 2, and the 2x-2L-1 otherwise
}
Peter Taylor
sumber
1

Perl 40 byte

$,=$";$i=4;{say$i-3,$i/2,($i+=4)-5;redo}

sumber
1

Brain-Flueue , 88 byte

({}<(((<>)[()])[()()])>)<>(((()())()()))<>{({})({})({})({}[()]<({}<>({})<>)>)}{}{}({}){}

Cobalah online!

Penjelasan

Ini mengimplementasikan fungsi yang sama dengan jawaban terakhir saya tetapi menggunakan model FIFO Brain-Flueue untuk memotong beberapa sudut. Berikut adalah istilah pasangan pertama yang dihasilkannya.

2 3 1 4 7 5 6 11 9 8 15 13 10 17 15 ...

Bagian pertama dari kode ini hanya sedikit pengaturan, kita meletakkan 0,-1,-3tumpukan pertama dan 2,4,4tumpukan kedua. Itu 2,4,4akan digunakan untuk menggilir angka genap dan ganjil seperti yang saya lakukan dalam jawaban Brain-Flak saya.

Kami kemudian mengulangi n kali, setiap kali menambahkan bagian atas tumpukan kiri ke tumpukan kanan. Karena Brain-Flueue menggunakan antrian sebagai lawan tumpukan, nilai-nilai secara alami bergulir ketika kita menyentuh mereka mencegah perlunya kode tambahan.

Wisaya Gandum
sumber
Apa perbedaan antara Flueue dan Flak?
FantaC
@tfbninja Flueue menggunakan Antrian alih-alih tumpukan.
Wheat Wizard
tapi ... Anda menggunakan penerjemah bflk ... bagaimana Anda membuatnya berbeda
FantaC
@ tfbninja -lflueueArgumen.
Wheat Wizard
0

Python 2 , 46 104 55 byte

lambda n:2*((n-int(n**.5))+.5,n**.5-1)[n!=1>0==n**.5%1]

Cobalah online!

Salah membaca pertanyaan, sekarang menerapkan fungsi yang dapat digunakan untuk membuat urutan, bukan yang menghasilkan urutan. Juga dikecualikan 0dari himpunan kemungkinan keluaran.

Kemungkinan menemukan bilangan bulat positif ganjil sekarang menyatu 1.

Jonathan Frech
sumber
Ini harus mengembalikan nomor, bukan set / daftar sejauh yang saya mengerti
Tn. Xcoder
Juga, ini bukan permutasi yang benar, karena mengandung 0.
Tn. Xcoder
@ Mr.Xcoder Terima kasih telah memperhatikan.
Jonathan Frech
0

Jelly , 9 byte

Ḥ€’ĖUẎQ⁸ị

Cobalah online!

Implements 1, 3, 2, 5, 7, 4, 9, 11, 6, ...(probabilitas 2/3).

Erik the Outgolfer
sumber
0

Pyth , 9 byte

*Fmxd<d4P

Coba di sini! atau Tes lebih banyak dalam sekali jalan!

Anda dapat menggunakan kode ini untuk memverifikasi rasio angka ganjil hingga titik tertentu. Ganti 10000dengan batas yang Anda inginkan (jangan atur jauh lebih tinggi, karena kesalahan memori).

Km*Fmxk<k4PdS10000clf%T2KlK

Coba di sini .

Di atas memberikan sekitar 0,667 . Peluang sebenarnya dari kejadian aneh adalah 2/3 . Pendekatan ini merupakan implementasi setara dari jawaban Dennis .


Penjelasan

*Fmxd<d4P   Full program.

        P   Prime factors.
  m         Map over ^.
   x        Bitwise XOR between:
    d          The current prime factor.
     <d4       The integer corresponding to the boolean value of current factor < 4.
*F          Product of the list.
Tuan Xcoder
sumber
0

Java 8, 20 byte

n->n%4>0?n+n/2|1:n/2

Pelabuhan @nwellnhof 's C jawabannya .
Beberapa hal yang saya coba sendiri ternyata beberapa byte lebih lama atau sedikit salah.

Implements: 1,3,5,2,7,9,11,4,13,15,17,6,19,21,23,8,25,27,29,10,31,33,35,12,37,...
dengan probabilitas 3/4.

Coba di sini.

Kevin Cruijssen
sumber
0

Lua, 67 53 byte

Penjelasan datang ketika saya selesai bermain golf ini :)

Program ini mengambil integer melalui argumen baris perintah sebagai input dan mencetak elemen ke-n dari urutan contoh ke STDOUT

n=...print(n%3<1 and n/3*2or n+math.floor(n/3)+n%3-1)

Penjelasan

n=...                              -- shorthand for the argument
print(                             -- prints out the result of the following ternary
     n%3<1                         -- if n is divisible by 3
       and n/3*2                   -- prints out the corresponding even number
       or n+math.floor(n/3)+n%3-1) -- else prints out the odd number

Angka genap dari urutan ini adalah nangka genap dan nkelipatan 3, oleh karena itu rumusnya n%3*2cukup untuk menghasilkannya.

Untuk angka ganjil, ini sedikit lebih sulit. Berdasarkan fakta bahwa kami dapat menemukannya tergantung pada arus n, kami memiliki tabel berikut:

n       |  1   2   4   5   7   8   10   11  
target  |  1   3   5   7   9   11  13   15
target-n|  +0  +1  +1  +2  +2  +3  +3   +4

Mari kita sebut nilainya target-n i, kita dapat melihat bahwa setiap kali n%3==2, ibertambah. Inilah formula kami:

n+math.floor(n/3)+n%3-1

Angka ganjil didasarkan npada yang kami tambahkan i.

Nilai ikenaikan pada tingkat yang sama dengan divisi euclidian sebesar 3, dengan offset. math.floor(n/3)memberi kita tingkat kenaikan dan n%3-1memberi kita offset, menjadikannya terjadi n%3==2alih-alih n%3==0.

Katenkyo
sumber
Satu byte dapat dengan mudah disimpan dengan menghapus ruang yang tidak perlu ( ...and (n/...).
Jonathan Frech
@JonathanFrech dapat menyelamatkan 2 di tempat ini dengan benar-benar menghapus tanda kurung sebagai and n/3*2orkarya yang sama baiknya
Katenkyo