Listen Sie alle Kombinationen mit Ersetzung (oder Kombinationen mit Wiederholung) der Größe k aus einer Menge von n Elementen auf.

Eine Kombination mit Ersetzung ist ein ungeordnetes Multiset, bei dem sich jedes Element auch in der Menge von n Elementen befindet. Beachten Sie, dass:

• Es ist ungeordnet. Ein zuvor gedrucktes Set mit einer anderen Reihenfolge sollte daher nicht erneut gedruckt werden.
• Es ist ein Multiset. Das gleiche Element kann (muss aber nicht) mehrmals vorkommen. Dies ist der einzige Unterschied zwischen einer Kombination mit Ersatz und einer normalen Kombination.
• Die Menge sollte genau k Elemente haben.

Alternativ ist es auch eine Teilmenge der Größe k des Multisets, die jedes der n Elemente k- mal enthält.

Die Eingabe sollte entweder n und k sein , wobei die Elemente die ersten n positiven oder nicht negativen ganzen Zahlen sind, oder die n Elemente und k , wobei Sie annehmen können, dass sich die n Elemente alle voneinander unterscheiden.

Die Ausgabe sollte eine Liste aller Kombinationen mit Ersetzung durch Größe k aus dem angegebenen Satz sein. Sie können sie und die Elemente in jeder von ihnen in beliebiger Reihenfolge drucken.

Sie dürfen keine eingebauten Kombinationen mit Ersatz verwenden. Sie können jedoch integrierte Funktionen verwenden, um normale Kombinationen, Permutationen, Tupel usw. zu generieren.

Dies ist Code-Golf, kürzester Code gewinnt.

Beispiel

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

Gelee, 4 Bytes

Vielen Dank an Sp3000 für das Speichern von 2 Bytes.

ṗṢ€Q

Die Eingabe erfolgt nund kals Befehlszeilenargumente in dieser Reihenfolge. Verwendet Elemente 1zu n.

Probieren Sie es online aus!

Erläuterung

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

CJam (8 Bytes)

{m*:$_&}

Online-Demo

Präparation

{    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 Bytes

Vielen Dank an A Simmons für das Speichern von 2 Bytes.

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

Eine unbenannte Funktion, die nund kals ganzzahlige Argumente in dieser Reihenfolge verwendet und eine Liste von Listen zurückgibt. Die Elemente werden zu 1sein n. Funktioniert genauso wie Peters CJam-Antwort.

MATL , 11 Bytes

(Es gibt eine 9-Byte-Lösung, die auf kartesischer Leistung basiert, aber Peter Taylor hat das bereits getan . Versuchen wir etwas anderes.)

Kombinationen mit Ersatz können wie folgt auf Kombinationen ohne Ersatz reduziert werden. Wir wollen n Cr kzum Beispiel mit n=3, k=2:

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

Wir können berechnen n+k-1 C k:

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

und dann 0 1 ... k-1von jeder Zeile subtrahieren :

+q:2GXn2G:-

Erläuterung:

+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

Der Code funktioniert in Version 13.1.0 der Sprache / des Compilers, die früher als die Herausforderung ist.

Sie können es online versuchen! Beachten Sie, dass der Online-Compiler auf Version 14.0.0 aktualisiert wurde und daher Xnin geändert werden muss 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]]:[[]]

Ich darf es keys()einmal benutzen .

Ruby, 56 55 Bytes

Zwei Lösungen, überraschenderweise beide gleich lang:

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

Hey, du hast gesagt, wir könnten eingebaute Permutationen verwenden ...

Dies erzeugt einfach alle wiederholten Permutationen (die zweite erzeugt wiederholte kartesische Produkte) und entfernt diejenigen, die nicht in sortierter Reihenfolge sind.

Vielen Dank an Martin für das Speichern eines Bytes mit 0...n-> 1..n!

Pyth, 7 Bytes

{SM^UQE

Verwendet den gleichen Algorithmus wie Peters Antwort.

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

Python, 63 Bytes

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

Eine rekursive Methode. Um eine Vielzahl von kElementen 1zu erstellen n, wählen wir entweder:

• Fügen Sie eine weitere Instanz von hinzu n, und es bleibt eine Vielzahl von k-1Elementen von 1bis zu erstellenn
• Fügen Sie keine weitere Instanz von hinzu n, und es bleibt eine Vielzahl von kElementen von bis 1zun-1

Wir beenden, wenn entweder koder nerreicht 0, und wenn es kerreicht ist 0, geben wir einen Basisfall der leeren Liste an. Wenn nicht, haben wir die falsche Anzahl von Elementen und geben daher die leere Liste an.

Python 3, 81 80

Rekursive Lösung:

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

Die Funktion t(n, k, b)gibt die Liste aller kMulti-Teilmengen aller Elemente des Bereichs von bbis zurück n. Diese Liste ist leer, wenn k <= 0. Andernfalls teilen wir das Problem anhand des kleinsten Elements der Multi-Teilmenge auf, das wir mit bezeichnen i.

Für jede iim Bereich von bbis ngenerieren wir alle k-multi-Teilmengen mit dem kleinsten Element, iindem wir mit [i]jeder (k-1)-multi-Teilmenge des Bereichs von ibis beginnen und diese dann anhängen n, die wir durch rekursives Aufrufen erhalten t(n, k-1, i).

Dyalog APL , 22 Bytes

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

Erforderlich ⎕IO←0, was in vielen APL-Systemen Standard ist. Nimmt k als linkes Argument, n als rechtes Argument.

⍳⍺*⍵0 1 2 ... kⁿ
⍺⊥⍣¯1in Basis konvertieren k
⍉transponieren
↓machen Matrix in Liste von Listen
{⍵[⍋⍵]}¨sortieren jeweils ...
∪das Einzigartige

J, 18 Bytes

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

Ein ähnlicher Ansatz wird in der Lösung von @ Adám verwendet .

Ein anderer Ansatz, bei dem ein kartesisches Produkt {für 24 Bytes verwendet wird. Übernimmt kdie LHS und ndie RHS.

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

Verwendungszweck

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

Erläuterung

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

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

Beachten Sie die geänderte Parameterreihenfolge: 1. ist kund 2. ist n. Dies sparte 1 Byte in (f(dec k)n).

Mathematica, 36 Bytes

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

Bitte sag mir, dass es einen 1/6 Bonus für die Verwendung von no [] s gibt ... Oder vielleicht für die vielen Verwendungen von ##?