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]
źródło
{}∪Sort/@Range@#~Tuples~#2&
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ładn=3
,k=2
:Możemy obliczyć
n+k-1 C k
:a następnie odejmij
0 1 ... k-1
od każdego wiersza:Wyjaśnienie:
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
Xn
należy go zmienić naXN
.źródło
JavaScript (Firefox 30-57), 71 bajtów
I dostać się do wykorzystania
keys()
na raz.źródło
Rubin,
5655 bajtówDwa rozwiązania, zaskakująco oba o tej samej długości:
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
!źródło
Pyth, 7 bajtów
Używa tego samego algorytmu co odpowiedź Piotra.
źródło
Python, 63 bajty
Metoda rekurencyjna. Aby dokonać MultiSet z
k
elementów,1
don
, możemy zdecydować się na:n
i pozostanie, aby utworzyć zbiór wieluk-1
elementów od1
don
n
, a pozostanie tworzenie wielu fragmentówk
od do1
don-1
Wypowiedzieć kiedy albo
k
czyn
biegu0
, a jeślik
osiągnięta0
, dajemy przypadek bazowy pustej listy. Jeśli nie, mamy niewłaściwą liczbę elementów, dlatego podaj pustą listę.źródło
Python 3,
8180Rozwiązanie rekurencyjne:
Funkcja
t(n, k, b)
zwraca listę wszystkichk
podzestawów wszystkich elementów z zakresu odb
don
. Ta lista jest pusta, jeślik <= 0
. W przeciwnym razie rozwiążemy problem na podstawie najmniejszego elementu wielu podzbiorów, który oznaczamyi
.Dla każdego
i
z zakresu odb
don
generujemy wszystkiek
-multi-podzbiory z najmniejszym elementemi
, zaczynając od,[i]
a następnie dołączając każdy(k-1)
-multi-podzbiór zakresu odi
don
, który otrzymujemy przez rekurencyjne wywołaniet(n, k-1, i)
.źródło
Dyalog APL , 22 bajty
Wymaga
⎕IO←0
, co jest domyślne w wielu systemach APL. Traktuje k jako lewy argument, n jako prawy argument.⍳⍺*⍵
0 1 2 ... kⁿ⍺⊥⍣¯1
konwertuj na podstawową k⍉
transponuj↓
uczyń macierz na liście list{⍵[⍋⍵]}¨
sortuj każdą ...∪
unikalnąźródło
J, 18 bajtów
Podobne podejście zastosowano w rozwiązaniu @ Adám .
Inne podejście wykorzystujące produkt kartezjański
{
dla 24 bajtów. Bierzek
na LHS in
na RHS.Stosowanie
Wyjaśnienie
źródło
Clojure, 94 bajty
Zwróć uwagę na zmienioną kolejność parametrów: 1. jest
k
i 2. jestn
. Zapisano 1 bajt(f(dec k)n)
.źródło
Mathematica, 36 bajtów
Proszę mi powiedzieć, że to 1/6 premii za korzystanie nie [] s ... A może dla wielu zastosowań ##?
źródło