Jumlah kombinasi dengan pengulangan

8

Tulis kode terpendek Anda dapat memecahkan masalah berikut:

Memasukkan:

Integer X dengan 2 <= XdanX <= 100

Keluaran:

Kombinasi total 2, 3, dan 5 (pengulangan diizinkan, hal-hal penting) yang jumlahnya sama dengan X.

Contoh:

Memasukkan: 8

Output:, 6karena kombinasi yang valid adalah:

3+5
5+3
2+2+2+2
2+3+3
3+2+3
3+3+2

Memasukkan: 11

Output:, 16karena kombinasi yang valid adalah 

5+3+3
5+2+2+2
3+5+3
3+3+5
3+3+3+2
3+3+2+3
3+2+3+3
3+2+2+2+2
2+5+2+2
2+3+3+3
2+3+2+2+2
2+2+5+2
2+2+3+2+2
2+2+2+5
2+2+2+3+2
2+2+2+2+3

Memasukkan: 100

Keluaran:, 1127972743581281karena kombinasi yang valid adalah ... banyak

Input dan output dapat berupa bentuk apa pun yang masuk akal. Hitungan byte terendah di setiap bahasa menang. Aturan standar kode-golf berlaku.

code-golf combinatorics integer-partitions anta40
sumber
1
Selamat datang di PPCG! Sayangnya, di sini kami tidak menjawab pertanyaan pemrograman umum. Namun, Anda mungkin bisa mendapatkan bantuan di Stack Overflow . Pastikan untuk memeriksa pusat bantuan mereka sebelum bertanya. :)
Erik the Outgolfer
1
Bisakah seseorang menulis ulang ini menjadi sebuah tantangan? Karena ini akan menyenangkan.
Magic Gurita Guci
1
@Shaggy Ugghhh ... menyaring tantangan dengan kata sumdi dalamnya bukanlah ide yang baik untuk mencoba menyelesaikan pertanyaan itu ...
Magic Octopus Mm
2
Saya menulis ulang pertanyaan Anda sedikit agar lebih cocok dengan codegolf. Saya juga mengubah hasil untuk input 11dari 12menjadi 16. Tentu saja merasa bebas untuk memperbaikinya jika saya salah memahami niat Anda
Ton Hospel
2
Ini adalah oeis.org/A079973
Ton Hospel

Jawaban:

9

Python 2 , 46 45 byte

terima kasih kepada xnor untuk -1 byte

f=lambda n:n>0and f(n-2)+f(n-3)+f(n-5)or n==0

Cobalah online!

ovs
sumber
Sepertinya and/orkarya dan menghemat byte: f=lambda n:n>0and f(n-2)+f(n-3)+f(n-5)or n==0.
xnor
@ xnor terima kasih banyak. Saya hanya mencobanya sebaliknya
Ov
6

Oasis , 9 byte

cd5e++VT1

Cobalah online!

Penjelasan

        1    # a(0) = 1
       T     # a(1) = 0, a(2) = 1
      V      # a(3) = 1, a(4) = 1

             # a(n) = 
c    +       # a(n-2) +
 d  +        # a(n-3) +
  5e         # a(n-5)
Emigna
sumber
3

Pyth , 9 byte

/sM{y*P30

Coba di sini!

Pyth , 16 byte

l{s.pMfqT@P30T./

Coba di sini

Bagaimana?

  1. Menghasilkan faktor prima dari 30 , yaitu [2, 3, 5] , mendapat pengulangan diulang N kali, menghilangkan elemen duplikat, menjumlahkan setiap daftar dan menghitung kemunculan N di dalamnya .

  2. Untuk setiap bilangan integer p , ia memeriksa apakah p sama dengan p ∩ primefac (30) . Itu hanya membuat mereka yang memenuhi kondisi ini, dan untuk setiap partisi k yang tersisa , ia mendapat daftar permutasi k , meratakan daftar yang dihasilkan dengan 1 level, mendupuplikasi dan mengambil panjangnya.

Tuan Xcoder
sumber
3

Jelly , 11 byte

5ÆRẋHŒPQḅ1ċ

Cobalah online!

Bagaimana itu bekerja

5ÆRẋHŒPQḅ1ċ -> Program lengkap. Argumen: N, bilangan bulat.
5ÆR -> Mendorong semua bilangan prima antara 2 dan 5, secara inklusif.
   ẋH -> Ulangi daftar ini N / 2 kali.
     ŒP -> Hasilkan powerset.
       Q -> Hapus entri duplikat.
        ḅ1 -> Konversi masing-masing dari unary (yaitu jumlah setiap daftar)
          ċ -> Hitung kemunculan N ke dalam daftar ini.
Tuan Xcoder
sumber
Percepat ³dengan mengganti dengan H(maka akan habis pada 12 daripada 6)
Jonathan Allan
@ JonathanAllan Selesai, terima kasih.
Tn. Xcoder
2

Perl, 38 byte

Termasuk +1untukp

perl -pE '$_=1x$_;/^(...?|.{5})+$(?{$\++})\1/}{' <<< 11; echo

Cukup menarik yang harus saya gunakan \1untuk memaksa mundur. Biasanya saya menggunakan ^tetapi pengoptimal regex tampaknya terlalu pintar untuk itu dan memberikan hasil yang terlalu rendah. Saya mungkin harus mulai memberikan nomor versi perl saat menggunakan trik ini karena pengoptimal dapat berubah di setiap versi. Ini diuji padaperl 5.26.1

Ini 49efisien dan benar-benar dapat menangani X=100(tetapi meluap X=1991)

perl -pe '$\=$F[@F]=$F[-2]+$F[-3]+$F[-5]for($F[5]=1)..$_}{' <<< 100;echo
Ton Hospel
sumber
2

C, 41 byte

G(x){return x>0?G(x-2)+G(x-3)+G(x-5):!x;}

Cobalah online!

0xrgb
sumber
2

R , 56 49 47 byte

Pendekatan rekursif dari jawaban ovs . Giuseppe memotong dua byte terakhir untuk membuatnya menjadi 47.

f=pryr::f(+`if`(x<5,x!=1,f(x-2)+f(x-3)+f(x-5)))

Cobalah online!

rturnbull
sumber
1
48 bytes
Giuseppe
@Giuseppe Peningkatan yang sangat bagus!
rturnbull
1
ah, Anda tidak perlu 0(saya tidak mempertimbangkan itu sebelumnya), karena unary juga +akan memaksa numeric.
Giuseppe
1

MATL , 15 byte

:"5Zq@Z^!XsG=vs

Sangat tidak efisien: memori yang dibutuhkan bersifat eksponensial.

Cobalah online!

Bagaimana itu bekerja

:"       % For each k in [1 2 ... n], where n is implicit input
  5Zq    %   Push primes up to 5, that is, [2 3 5]
  @      %   Push k
  Z^     %   Cartesian power. Gives a matrix where each row is a Cartesian k-tuple
  !Xs    %   Sum of each row
  G=     %   Compare with input, element-wise
  vs     %   Concatenate all stack contents vertically and sum
         % Implicit end. Implicit display
Luis Mendo
sumber
1

Ruby , 41 byte

f=->n{n<5?n==1?0:1:[n-5,n-2,n-3].sum(&f)}

Cobalah online!

Ini adalah solusi rekursif, yang recurcive panggilan makhluk: [n-5,n-2,n-3].sum(&f).

MegaTom
sumber
0

Pyth, 12 byte

l{fqQsTy*P30

Ini sangat tidak efisien dan mencapai batas memori untuk input di atas 5.

Cobalah online

Penjelasan

l{fqQsTy*P30
         P30   Get the prime factors of 30 [2, 3, 5].
        *   Q  Repeat them (implicit) input times.
       y       Take the power set...
  fqQsT        ... and filter the ones whose sum is the input.
l{             Count unique lists.

sumber
0

Bahasa Wolfram (Mathematica) , 43 byte

Tr[Multinomial@@@{2,3,5}~FrobeniusSolve~#]&

Cobalah online!

Penjelasan: FrobeniusSolvemenghitung semua solusi dari jumlah yang tidak berurutan 2a + 3b + 5c = n, lalu mencari Multinomialtahu berapa banyak cara kita dapat memesan jumlah itu.

Atau kita bisa menyalin solusi orang lain untuk jumlah byte yang sama:

f@1=0;f[0|2|3|4]=1;f@n_:=Tr[f/@(n-{2,3,5})]
Bukan pohon
sumber