Wymień wszystkie kombinacje z zastąpieniem (lub kombinacje z powtórzeniem) rozmiaru k z zestawu n elementów.

Kombinacja z zamiennikiem to nieuporządkowany multiset, który zawiera każdy element w zestawie n elementów. Uwaga:

• To jest nieuporządkowane. Tak więc wcześniej wydrukowany zestaw w innym porządku nie powinien być ponownie drukowany.
• To jest multiset. Ten sam element może (ale nie jest wymagany) pojawiać się więcej niż jeden raz. Jest to jedyna różnica między kombinacją z wymianą a normalną kombinacją.
• Zestaw powinien mieć dokładnie k elementów.

Alternatywnie jest to również podzbiór rozmiaru k multiset, który zawiera każdy z n elementów k razy.

Dane wejściowe powinny mieć wartość n i k , gdzie elementy są pierwszymi n dodatnimi lub nieujemnymi liczbami całkowitymi, lub n elementów i k , gdzie można założyć, że n elementów różni się od siebie.

Wyjściem powinna być lista wszystkich kombinacji z zamianą na rozmiar k z podanego zestawu. Możesz wydrukować je i elementy w każdym z nich w dowolnej kolejności.

Nie możesz używać wbudowanych generujących kombinacje z zamianą. Ale możesz używać wbudowanych funkcji do generowania normalnych kombinacji, permutacji, krotek itp.

To jest golf, najkrótszy kod wygrywa.

Przykład

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

Galaretka, 4 bajty

Dzięki Sp3000 za oszczędność 2 bajtów.

ṗṢ€Q

Dane wejściowe są ni kjako argumenty wiersza polecenia w tej kolejności. Wykorzystuje elementy 1do n.

Wypróbuj online!

Wyjaśnienie

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

CJam (8 bajtów)

{m*:$_&}

Demo online

Sekcja

{    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 bajtów

Dzięki A Simmons za zapisanie 2 bajtów.

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

Nienazwana funkcja przyjmująca ni kjako argumenty liczb całkowitych w tej kolejności i zwracająca listę list. Elementy będą 1do n. Działa tak samo jak odpowiedź CJam Petera.

MATL , 11 bajtów

(Istnieje 9-bajtowe rozwiązanie oparte na potędze kartezjańskiej, ale Peter Taylor już to zrobił . Spróbujmy czegoś innego).

Połączenia z zamianą można zredukować do kombinacji bez zamiany w następujący sposób. Chcemy n Cr k, na przykład n=3, k=2:

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

Możemy obliczyć n+k-1 C k:

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

a następnie odejmij 0 1 ... k-1od każdego wiersza:

+q:2GXn2G:-

Wyjaśnienie:

+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

Kod działa w wersji 13.1.0 języka / kompilatora, która jest wcześniejsza niż wyzwanie.

Możesz spróbować online! Pamiętaj, że kompilator online został zaktualizowany do wersji 14.0.0, dlatego Xnnależy go zmienić na XN.

JavaScript (Firefox 30-57), 71 bajtów

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

I dostać się do wykorzystania keys()na raz.

Rubin, 56 55 bajtów

Dwa rozwiązania, zaskakująco oba o tej samej długości:

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

Hej, nie mówią, moglibyśmy użyć poleceń wbudowanych permutacji ...

To po prostu generuje wszystkie powtarzające się permutacje (drugie generuje powtarzające się produkty kartezjańskie) i usuwa te, które nie są posortowane.

Dzięki Martin za zapisanie bajtu za pomocą 0...n-> 1..n!

Pyth, 7 bajtów

{SM^UQE

Używa tego samego algorytmu co odpowiedź Piotra.

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

Python, 63 bajty

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

Metoda rekurencyjna. Aby dokonać MultiSet z kelementów, 1do n, możemy zdecydować się na:

• Dołącz inne wystąpienie ni pozostanie, aby utworzyć zbiór wielu k-1elementów od 1don
• Nie dołączaj innego wystąpienia n, a pozostanie tworzenie wielu fragmentów kod do 1don-1

Wypowiedzieć kiedy albo kczy nbiegu 0, a jeśli kosiągnięta 0, dajemy przypadek bazowy pustej listy. Jeśli nie, mamy niewłaściwą liczbę elementów, dlatego podaj pustą listę.

Python 3, 81 80

Rozwiązanie rekurencyjne:

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)]

Funkcja t(n, k, b)zwraca listę wszystkich kpodzestawów wszystkich elementów z zakresu od bdo n. Ta lista jest pusta, jeśli k <= 0. W przeciwnym razie rozwiążemy problem na podstawie najmniejszego elementu wielu podzbiorów, który oznaczamy i.

Dla każdego iz zakresu od bdo ngenerujemy wszystkie k-multi-podzbiory z najmniejszym elementem i, zaczynając od, [i]a następnie dołączając każdy (k-1)-multi-podzbiór zakresu od ido n, który otrzymujemy przez rekurencyjne wywołanie t(n, k-1, i).

Dyalog APL , 22 bajty

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

Wymaga ⎕IO←0, co jest domyślne w wielu systemach APL. Traktuje k jako lewy argument, n jako prawy argument.

⍳⍺*⍵0 1 2 ... kⁿ
⍺⊥⍣¯1konwertuj na podstawową k
⍉transponuj
↓uczyń macierz na liście list
{⍵[⍋⍵]}¨sortuj każdą ...
∪unikalną

J, 18 bajtów

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

Podobne podejście zastosowano w rozwiązaniu @ Adám .

Inne podejście wykorzystujące produkt kartezjański {dla 24 bajtów. Bierze kna LHS i nna RHS.

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

Stosowanie

   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│
└───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘

Wyjaśnienie

[:~.#~<@/:~@#: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 bajty

(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))))))

Zwróć uwagę na zmienioną kolejność parametrów: 1. jest ki 2. jest n. Zapisano 1 bajt (f(dec k)n).

Mathematica, 36 bajtów

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

Proszę mi powiedzieć, że to 1/6 premii za korzystanie nie [] s ... A może dla wielu zastosowań ##?