Daftar semua kombinasi dengan penggantian (atau kombinasi dengan pengulangan) ukuran k dari seperangkat elemen n .

Kombinasi dengan penggantian adalah multiset unordered bahwa setiap elemen di dalamnya juga di set dari n elemen. Perhatikan bahwa:

• Itu tidak teratur. Jadi set yang sebelumnya dicetak dengan urutan yang berbeda tidak boleh dicetak lagi.
• Ini adalah multiset. Elemen yang sama dapat (tetapi tidak diharuskan) muncul lebih dari sekali. Ini adalah satu-satunya perbedaan antara kombinasi dengan penggantian dan kombinasi normal.
• Set harus memiliki elemen k yang tepat .

Atau, itu juga merupakan subset size- k dari multiset yang berisi masing-masing n elemen k kali.

Input harus berupa n dan k , di mana elemen-elemennya adalah bilangan bulat pertama n positif atau non-negatif, atau elemen n dan k , di mana Anda dapat mengasumsikan elemen n semuanya berbeda satu sama lain.

Output harus berupa daftar semua kombinasi dengan penggantian dengan ukuran k dari set yang diberikan. Anda dapat mencetaknya dan elemen-elemen di dalamnya masing-masing dalam urutan apa pun.

Anda tidak boleh menggunakan builtin menghasilkan kombinasi dengan penggantian. Tetapi Anda dapat menggunakan builtin untuk menghasilkan kombinasi normal, permutasi, tupel, dll.

Ini golf kode, kode terpendek yang menang.

Contoh

Input: 4 2
Output: [0 0] [0 1] [0 2] [0 3] [1 1] [1 2] [1 3] [2 2] [2 3] [3 3]

Jelly, 4 byte

Terima kasih kepada Sp3000 untuk menghemat 2 byte.

ṗṢ€Q

Input adalah ndan ksebagai argumen baris perintah dalam urutan itu. Menggunakan elemen 1untuk n.

Cobalah online!

Penjelasan

ṗ     # Get k-th Cartesion power of n.
 Ṣ€   # Sort each tuple.
   Q  # Remove duplicates.

CJam (8 byte)

{m*:$_&}

Demo online

Pembedahan

{    e# Declare block (anonymous function); parameters are n k
  m* e# Cartesian product, which implicitly lifts n to [0 1 ... n-1]
  :$ e# Sort each element of the Cartesian product, to give them canonical forms
  _& e# Deduplicate
}

Mathematica, 31 29 byte

Terima kasih kepada A Simmons untuk menghemat 2 byte.

{}⋃Sort/@Range@#~Tuples~#2&

Fungsi tanpa nama mengambil ndan ksebagai argumen integer dalam urutan itu dan mengembalikan daftar daftar. Elemennya adalah 1untuk n. Bekerja sama dengan jawaban Peter CJam.

MATL , 11 byte

(Ada solusi 9-byte berdasarkan kekuatan Cartesian, tetapi Peter Taylor sudah melakukannya . Mari kita coba sesuatu yang berbeda).

Kombinasi dengan penggantian dapat dikurangi menjadi kombinasi tanpa penggantian sebagai berikut. Kami ingin n Cr k, misalnya dengan n=3, k=2:

0 0
0 1
0 2
1 1
1 2
2 2

Kami dapat menghitung n+k-1 C k:

0 1
0 2
0 3
1 2
1 3
2 3

lalu kurangi 0 1 ... k-1dari setiap baris:

+q:2GXn2G:-

Penjelasan:

+q     % take two inputs n, k and compute n+k-1
:      % range [1,2...,n+k-1]
2G     % push second input, k
Xn     % combinations without replacement
2G:    % range [1,2,...,k]
-      % subtract with broadcast. Display

Kode ini berfungsi di rilis 13.1.0 dari bahasa / kompiler, yang lebih awal dari tantangan.

Anda dapat mencobanya secara online! Perhatikan bahwa kompiler online telah diperbarui untuk merilis 14.0.0, jadi Xnperlu diubah ke XN.

JavaScript (Firefox 30-57), 71 byte

f=(n,k)=>k?[for(m of Array(n).keys())for(a of f(m+1,k-1))[...a,m]]:[[]]

Saya bisa menggunakannya keys()sekali.

Ruby, 56 55 byte

Dua solusi, secara mengejutkan keduanya memiliki panjang yang sama:

->n,k{[*1..n].repeated_permutation(k).map(&:sort).uniq}
->n,k{(a=[*1..n]).product(*[a]*(k-1)).map(&:sort).uniq}

Hei, kau tidak mengatakan kita bisa menggunakan builtin permutasi ...

Ini hanya menghasilkan semua permutasi berulang (yang kedua menghasilkan produk Cartesian berulang) dan menghilangkan yang tidak dalam urutan.

Terima kasih kepada Martin karena telah menyimpan byte dengan 0...n-> 1..n!

Pyth, 7 byte

{SM^UQE

Menggunakan algoritma yang sama dengan jawaban Peter.

    UQ   range(input())
      E  input()
   ^     repeated Cartesian product of ^^, ^ times
 SM      map(sort)
{        uniq

Python, 63 byte

f=lambda n,k:n*k and[l+[n]for l in f(n,k-1)]+f(n-1,k)or[[]][k:]

Metode rekursif. Untuk membuat multiset dari kunsur-unsur, 1untuk n, kami memilih untuk:

• Sertakan instance lain dari n, dan masih membuat multiset k-1elemen dari 1hinggan
• Jangan sertakan contoh lain dari n, dan itu tetap membuat multiset kelemen dari ke 1ken-1

Kami mengakhiri ketika salah satu katau nmencapai 0, dan jika kmencapai 0, kami memberikan kasus dasar dari daftar kosong. Jika tidak, kami memiliki jumlah elemen yang salah, dan berikan daftar kosong.

Python 3, 81 80

Solusi rekursif:

t=lambda n,k,b=0:[[]]if k<=0 else [[i]+l for i in range(b,n)for l in t(n,k-1,i)]

Fungsi t(n, k, b)mengembalikan daftar ksubset semua elemen multi-rentang dari bke n. Daftar ini kosong jika k <= 0. Jika tidak, kami memecahkan masalah berdasarkan elemen terkecil dari multi-subset, yang kami tunjukkan i.

Untuk masing-masing idalam rentang dari bhingga n, kami membuat semua ksubset -multi dengan elemen terkecil idengan mulai dengan [i]dan kemudian menambahkan setiap (k-1)subset -multi dari rentang dari ike n, yang kami peroleh dengan menelepon secara rekursif t(n, k-1, i).

Dyalog APL , 22 byte

{∪{⍵[⍋⍵]}¨↓⍉⍺⊥⍣¯1⍳⍺*⍵}

Membutuhkan ⎕IO←0, yang merupakan standar dalam banyak sistem APL. Membawa k sebagai argumen kiri, n sebagai argumen kanan.

⍳⍺*⍵0 1 2 ... kⁿ
⍺⊥⍣¯1konversikan ke basis k
⍉transpos
↓buat matriks ke daftar daftar,
{⍵[⍋⍵]}¨masing-masing ...
∪unik

J, 18 byte

[:~.#~<@/:~@#:i.@^

Pendekatan serupa digunakan dalam solusi @ Adám .

Pendekatan lain menggunakan produk Cartesian {selama 24 byte. Mengambil kpada LHS dan npada RHS.

~.@:(/:~&.>)@,@{@(#<@i.)

Pemakaian

   f =: [:~.#~<@/:~@#:i.@^
   4 f 2
┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
│0 0│0 1│0 2│0 3│1 1│1 2│1 3│2 2│2 3│3 3│
└───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘

Penjelasan

[:~.#~<@/:~@#:i.@^ Input: n on LHS and k on RHS
                 ^ Compute n^k
              i.@  Create a range [0, 1, ... n^k-1]
    #~             Create k copies on n
            #:     On each value in the range above, convert each digit to base-n
                   and take the last k digits of it
        /:~@       For each array of digits, sort it in ascending order
      <@           Box each array of digits
[:~.               Take the distinct values in the array of boxes and return it

Clojure, 94 byte

(defn f[k n](if(= 1 k)(for[i(range n)][i])(sort(set(for[i(f(dec k)n)j(range n)](conj i j))))))

Perhatikan urutan parameter yang diubah: 1 adalah kdan 2 adalah n. Ini menyimpan 1 byte dalam (f(dec k)n).

Mathematica, 36 byte

{##}&~Array~Table@##~Flatten~(#2-1)&

Tolong beritahu saya ada bonus 1/6 untuk tidak menggunakan [] s ... Atau mungkin untuk banyak penggunaan ##?