Énumérez toutes les combinaisons avec remplacement (ou combinaisons avec répétition) de taille k à partir d'un ensemble de n éléments.
Une combinaison avec remplacement est un multiset non ordonné dont chaque élément est également dans l'ensemble de n éléments. Notez que:
- Ce n'est pas ordonné. Par conséquent, un ensemble précédemment imprimé avec un ordre différent ne doit plus être imprimé.
- Il s'agit d'un multiset. Le même élément peut (mais n'est pas requis) apparaître plusieurs fois. C'est la seule différence entre une combinaison avec remplacement et une combinaison normale.
- L'ensemble doit avoir exactement k éléments.
Alternativement, c'est également un sous-ensemble taille- k du multiset qui contient chacun des n éléments k fois.
L'entrée doit être soit n et k , où les éléments sont les n premiers entiers positifs ou non négatifs, soit les n éléments et k , où vous pouvez supposer que les n éléments sont tous différents les uns des autres.
La sortie doit être une liste de toutes les combinaisons avec remplacement de taille k de l'ensemble donné. Vous pouvez les imprimer et les éléments dans chacun d'eux dans n'importe quel ordre.
Vous ne pouvez pas utiliser de combinaisons génératrices intégrées avec remplacement. Mais vous pouvez utiliser des fonctions intégrées pour générer des combinaisons, permutations, tuples normaux, etc.
C'est le code-golf, le code le plus court gagne.
Exemple
Input: 4 2
Output: [0 0] [0 1] [0 2] [0 3] [1 1] [1 2] [1 3] [2 2] [2 3] [3 3]
la source
{}∪Sort/@Range@#~Tuples~#2&
MATL , 11 octets
(Il existe une solution à 9 octets basée sur la puissance cartésienne, mais Peter Taylor l'a déjà fait . Essayons quelque chose de différent).
Les combinaisons avec remplacement peuvent être réduites à des combinaisons sans remplacement comme suit. Nous voulons
n Cr k
, par exemple avecn=3
,k=2
:Nous pouvons calculer
n+k-1 C k
:puis soustrayez
0 1 ... k-1
de chaque ligne:Explication:
Le code fonctionne dans la version 13.1.0 du langage / compilateur, qui est antérieure au défi.
Vous pouvez l' essayer en ligne! Notez que le compilateur en ligne a été mis à jour vers la version 14.0.0 et
Xn
doit donc être remplacé parXN
.la source
JavaScript (Firefox 30-57), 71 octets
Je peux utiliser
keys()
pour une fois.la source
Rubis,
5655 octetsDeux solutions, étonnamment toutes deux de même longueur:
Hé, vous avez dit que nous pourrions utiliser builtins de permutation ...
Cela génère simplement toutes les permutations répétées (la seconde génère des produits cartésiens répétés) et supprime ceux qui ne sont pas triés.
Merci à Martin d'avoir sauvé un octet avec
0...n
->1..n
!la source
Pyth, 7 octets
Utilise le même algorithme que la réponse de Peter.
la source
Python, 63 octets
Une méthode récursive. Pour faire un multiset d'
k
éléments,1
pourn
, nous choisissons soit:n
, et il reste à faire un multi-ensemble d'k-1
éléments de1
àn
n
, et il reste à faire un multi-ensemble d'k
éléments de à1
àn-1
Nous terminons lorsque l'un
k
ou l' autren
atteint0
et s'ilk
atteint0
, nous donnons un cas de base de la liste vide. Sinon, nous avons le mauvais nombre d'éléments, et donnons donc la liste vide.la source
Python 3,
8180Solution récursive:
La fonction
t(n, k, b)
renvoie la liste de tousk
les sous-ensembles multi-éléments de la plage deb
àn
. Cette liste est vide sik <= 0
. Sinon, nous décomposons le problème en nous basant sur le plus petit élément du multi-sous-ensemble, que nous désignons pari
.Pour chacun
i
dans la plage deb
àn
, nous générons tous lesk
-multi-sous-ensembles avec le plus petit élémenti
en commençant par[i]
puis en ajoutant chaque(k-1)
-multi-sous-ensemble de la plage dei
àn
, que nous obtenons en appelant récursivementt(n, k-1, i)
.la source
Dyalog APL , 22 octets
Requiert
⎕IO←0
, qui est par défaut dans de nombreux systèmes APL. Prend k comme argument de gauche, n comme argument de droite.⍳⍺*⍵
0 1 2 ... kⁿ⍺⊥⍣¯1
convertir en base k⍉
transposer↓
faire la matrice en liste de listes{⍵[⍋⍵]}¨
trier chacune ...∪
l'uniquela source
J, 18 octets
Approche similaire utilisée dans la solution de @ Adám .
Une autre approche utilisant un produit cartésien
{
pour 24 octets. Prendk
le LHS etn
le RHS.Usage
Explication
la source
Clojure, 94 octets
Notez l'ordre des paramètres modifié: 1er est
k
et 2e estn
. Cela a permis d'économiser 1 octet(f(dec k)n)
.la source
Mathematica, 36 octets
S'il vous plaît, dites-moi qu'il y a un bonus de 1/6 pour l'utilisation de no [] s ... Ou peut-être pour les nombreuses utilisations de ##?
la source