Перечислите все комбинации с заменой (или комбинации с повторением) размера k из набора из n элементов.

Комбинация с заменой является неупорядоченным мультимножеством, что каждый элемент в нем также находится в наборе из n элементов. Обратите внимание, что:

• Это неупорядочено. Поэтому ранее напечатанный набор с другим порядком не должен быть напечатан снова.
• Это мультимножество. Один и тот же элемент может (но не обязательно) появляться более одного раза. Это единственная разница между комбинацией с заменой и нормальной комбинацией.
• Множество должно иметь ровно k элементов.

Альтернативно, это также подмножество размера k мультимножества, которое содержит каждый из n элементов k раз.

Входные данные должны быть либо n и k , где элементы - это первые n положительных или неотрицательных целых чисел, либо n элементов и k , где можно предположить, что все n элементов отличаются друг от друга.

Выходными данными должен быть список всех комбинаций с заменой размером k из заданного набора. Вы можете распечатать их и элементы в каждом из них в любом порядке.

Вы не можете использовать встроенные генерирующие комбинации с заменой. Но вы можете использовать встроенные функции для генерации нормальных комбинаций, перестановок, кортежей и т. Д.

Это код-гольф, самый короткий код выигрывает.

пример

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

Желе, 4 байта

Спасибо Sp3000 за сохранение 2 байта.

ṗṢ€Q

Ввод nи kкак аргументы командной строки в этом порядке. Использует элементы 1для n.

Попробуйте онлайн!

объяснение

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

CJam (8 байт)

{m*:$_&}

Онлайн демо

рассечение

{    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 байт

Спасибо Симмонсу за сохранение 2 байта.

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

Неименованная функция, принимающая nи в kкачестве целочисленных аргументов в указанном порядке и возвращающая список списков. Элементы будут 1к n. Работает так же, как ответ Питера на CJam.

MATL , 11 байт

(Существует 9-байтовое решение, основанное на декартовой мощности, но Питер Тейлор уже сделал это . Давайте попробуем что-то другое).

Комбинации с заменой могут быть сведены к комбинациям без замены следующим образом. Мы хотим , чтобы n Cr k, например , с n=3, k=2:

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

Мы можем вычислить n+k-1 C k:

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

а затем вычтите 0 1 ... k-1из каждой строки:

+q:2GXn2G:-

Объяснение:

+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

Код работает в версии 13.1.0 языка / компилятора, который является более ранним, чем вызов.

Вы можете попробовать это онлайн! Обратите внимание, что онлайн-компилятор обновлен до версии 14.0.0, поэтому его Xnнеобходимо изменить на XN.

JavaScript (Firefox 30-57), 71 байт

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

Я использую keys()на этот раз.

Рубин, 56 55 байт

Два решения, на удивление оба одинаковой длины:

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

Эй, ты же сказал, что мы можем использовать встроенные перестановки ...

Это просто генерирует все повторяющиеся перестановки (вторая генерирует повторяющиеся декартовы произведения) и удаляет те, которые не в отсортированном порядке.

Спасибо Мартину за сохранение байта с 0...n-> 1..n!

Pyth, 7 байт

{SM^UQE

Использует тот же алгоритм, что и ответ Питера.

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

Python, 63 байта

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

Рекурсивный метод. Для того, чтобы мультимножество kэлементов, 1к n, мы выбираем либо:

• Включите еще один экземпляр n, и осталось сделать мультимножество k-1элементов из 1вn
• Не включайте другой экземпляр n, и осталось сделать мультимножество kэлементов от 1кn-1

Мы выключили , когда либо kили nдостигаем 0, и если она kдостигнута 0, мы даем базовый случай пустого списка. Если нет, то у нас неверное количество элементов, и поэтому выдаем пустой список.

Питон 3, 81 80

Рекурсивное решение:

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

Функция t(n, k, b)возвращает список всех kмногоэлементных подмножеств диапазона в диапазоне от bдо n. Этот список пуст, если k <= 0. В противном случае мы разбиваем проблему на основе наименьшего элемента мульти-подмножества, который мы обозначаем через i.

Для каждого iв диапазоне от bдо nмы генерируем все k-multi-подмножества с наименьшим элементом i, начиная с, [i]а затем добавляя каждое (k-1)-multi-подмножество диапазона от iдо n, которое мы получаем рекурсивным вызовом t(n, k-1, i).

Дьялог АПЛ , 22 байта

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

Требуется ⎕IO←0, что по умолчанию во многих системах APL. Принимает k в качестве левого аргумента, n в качестве правого аргумента.

⍳⍺*⍵0 1 2 ... kⁿ
⍺⊥⍣¯1преобразовать в базу k
⍉транспонировать
↓сделать матрицу в список списков
{⍵[⍋⍵]}¨отсортировать каждый ...
∪уникальный

J, 18 байт

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

Аналогичный подход используется в @ Адамов растворе .

Другой подход, использующий декартово произведение {для 24 байтов. Принимает kна LHS и nна RHS.

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

Применение

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

объяснение

[:~.#~<@/:~@#: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 байта

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

Обратите внимание на измененный порядок параметров: 1-й - это, kа 2-й - это n. Это спасло 1 байт (f(dec k)n).

Mathematica, 36 байт

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

Пожалуйста, скажите мне, что есть бонус 1/6 за использование без [] s ... Или, может быть, за многократное использование ##?