Декартово произведение списка с собой n раз

10

Когда вам дан список значений и положительное целое число n, ваш код должен вывести декартово произведение списка вместе с его nвременами.

Например, в псевдокоде ваша функция может быть похожа на:

for x1 in list:
    for x2 in list:
        for x3 in list:
            ...
            for xn in list:
                print x1, x2, x3, ... , xn

Пример: 

repeated_cart([1,2,3], 3)

1 1 1  
1 1 2  
1 1 3  
1 2 1  
1 2 2  
1 2 3  
1 3 1  
1 3 2  
1 3 3  
2 1 1  
2 1 2  
2 1 3  
2 2 1  
2 2 2  
2 2 3  
2 3 1  
2 3 2  
2 3 3  
3 1 1  
3 1 2  
3 1 3  
3 2 1  
3 2 2  
3 2 3  
3 3 1  
3 3 2  
3 3 3

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

Входы и выходы должны быть разделены, но могут быть приняты любым разумным способом.

порядок вывода результатов не имеет значения, но дубликаты не допускаются.

Я впервые пишу вопрос, поэтому, если я сделал что-то ужасно неправильно, пожалуйста, сообщите мне.

code-golf math array-manipulation combinatorics JoshM
источник
5
Добро пожаловать в PPCG! В этом нет ничего ужасного, но найдите время, чтобы взглянуть на этот пост и ответы.
Чего
4
и чтобы следить за точкой зрения @JayCe, вы можете (должны) опубликовать сообщение в «Песочнице», чтобы получить обратную связь, прежде чем задавать вопрос :-)
Джузеппе
@Giuseppe Хорошо, я сделаю это с этого
момента
1
Пограничный обман на codegolf.stackexchange.com/q/125104/194
Питер Тейлор
1
Наборы @Jakob должны быть хорошими
JoshM

Ответы:

6

Common Lisp , 146 байт

(defun f(l n)(if(< n 2)(loop for x in l collect(list x))(loop for a in l nconc(loop for b in(f l(1- n))collect(cons a b)))))(princ(f(read)(read)))

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

ungolfed

(defun nloops (lst n)
  (if (< n 1)
      '(())
      (if (< n 2)
          (loop for x in lst collect (list x))
          (loop for a in lst
                nconc (loop for b in (nloops lst (1- n))
                            collect (cons a b))))))
JoshM
источник
2
как правило, мы предлагаем подождать других заявок, прежде чем публиковать свои собственные :-)
Джузеппе
1
@Giuseppe Хорошо, спасибо за совет :)
JoshM
1
Вы не должны иметь оператор print в представлении, так как функция разрешена
только ASCII
1
итак: 96
только ASCII
1
90
Только для ASCII
6

R , 41 байт

function(l,n)unique(t(combn(rep(l,n),n)))

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

combnэто определенно не декартово встроенное произведение, так как оно вычисляет все nкомбинации его входных данных.

R , 40 байт

function(l,n)expand.grid(rep(list(l),n))

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

expand.grid вероятно, декартово произведение встроено.

Giuseppe
источник
Похоже, порядок перестановок в вашем основном представлении неверен.
Кирилл Л.
@KirillL. Есть ли конкретная причина важности заказа? Я интерпретировал выходную спецификацию как достаточно гибкую, чтобы разрешить их в любом порядке.
Джузеппе
есть комментарий ОП «убедитесь, что вывод в правильном порядке», я предположил, «правильно» означает то же, что и в примере.
Кирилл Л.
@KirillL. Ах. Не видел этого; это не в теле вопроса, поэтому я не знал, что он существует! Я попрошу, чтобы его поместили туда для разъяснений.
Джузеппе
4

Perl 6 , 16 байт

{[X,] $^a xx$^b}

Попробуй это

Expnded:

{  # bare block lambda with placeholder parameters $a and $b

  [X,]         #reduce using Cross meta op combined with comma op

    $^a xx $^b # list repeat $a, by $b times
}
Брэд Гилберт b2gills
источник
3

K (нгн / к) , 10 байтов

{x@+!y##x}

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

{ }это функция с аргументами xиy

#x длина x

y##xдлина xповторяющихся yвремен

!y##x все кортежи длины y более 0,1, ..., length (x) -1 в качестве транспонированной матрицы

+ транспонирования

x@элементы xпо этим показателям

СПП
источник
3

APL (Dyalog Classic) , 18 12 байт

{⍺[↑,⍳⍵⍴≢⍺]}

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

-6 байт благодаря @ngn!

Zachary
источник
Вы можете использовать ⍳с векторным аргументом для генерации индексов, а затем ⍺[ ]для получения соответствующих значений
ngn
Я получил, RANK ERRORкогда я пытался это сделать.
Захари
⍺[↑,⍳⍵⍴≢⍺]
нгн
единственный улов с ⍵ = 1, в этом случае ⍳ возвращает простой вектор, а не вектор вложенных векторов длины-1, как можно было бы ожидать; это одна из тех ошибок, которые никогда не исправляются по причинам обратной совместимости
ngn
3

Рубин , 53 байта

f=->l,n{n<2?l:l.flat_map{|i|f[l,n-1].map{|j|[i,*j]}}}

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

Рекурсивный подход, не такой короткий, но гарантированно свободный от каких-либо встроенных функций.

Заманчиво использовать методы перестановки, но это, вероятно, не считается, и документы фактически не дают никаких гарантий правильности порядка, хотя, кажется, работают на практике:

Рубин , 35 байт

->l,n{[*l.repeated_permutation(n)]}

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

Кирилл Л.
источник
2

Ракетка, 92 байта

(define(f l n)(if(> n 0)(apply append(map(λ(r)(map(λ(e)(cons e r))l))(f l(- n 1))))'(())))

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

Ungolfed

(define (f l n)
    (if (> n 0)
        (apply append
            (map
                (λ (r)
                    (map (λ (e) (cons e r)) l)
                )
                (f l (- n 1))
            )
        )
        '(())
    )
)
Jakob
источник
2

Желе , 11 9 7 байт

³;þẎƊ’¡

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

объяснение

³;þẎƊ’¡
³;þẎ    **Implements** the cartesian product of a value with the input
    Ɗ   Groups those together
     ’¡ Repeat (n-1) times
Zachary
источник
Посмотрите на комментарий ОП: р
Захари
Мой комментарий, к которому я привел это, звучит так: «Я также предполагаю, что встроенные функции для всего вызова также недопустимы», поэтому я просто предположил, что это нормально.
Захари
Что ж, давайте тогда подождем OP
Захари
@ Zacharý извините, функция декартовой власти не разрешена
JoshM
3
Я не знаю, два вложенных для таких циклов - это в основном определение декартового произведения. Я не говорю, что вы должны изменить это, я просто думаю, что запрет встроенного в этом вызове неясен.
Дилнан
2

Pure Bash (без внешних утилит), 57

printf -vn %0$1d
a=${n//0/{$2\}}
eval echo ${a//\}{/\},{}

Ввод дается в качестве параметров командной строки; 1-й n, 2-й - список через запятую.

printf -vn %0$1d         ;# Create a string of n "0"s in the variable v
a=${n//0/{$2\}}          ;# Replace each "0" with "{a,b,...m}"
eval echo ${a//\}{/\},{} ;# Replace each "}{" with "},{" and evaluate the resulting brace expansion

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

Цифровая травма
источник
2

Java 10, 19 + 135 = 154 байта

import java.util.*;

List<List>f(Set l,int n){var o=new Stack();if(n<1)o.add(new Stack());else for(var t:l)for(var i:f(l,n-1)){i.add(t);o.add(i);}return o;}

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

Ungolfed

List<List> f(Set l, int n) {
    var o = new Stack();
    if (n < 1)
        o.add(new Stack());
    else
        for (var t : l)
            for (var i : f(l, n - 1)) {
                i.add(t);
                o.add(i);
            }
    return o;
}

Подтверждения

  • порт на Java 10 благодаря Кевину Круйссену
Jakob
источник
Если вы используете Java 10 вместо 8, вы можете изменить Objectи Listв наличии для каждых петель varдля -4 байт. Кроме того, вы можете перейти Set<List>fк List<List>fи Set o=new HashSet();на var o=new Stack();дополнительный -1 байт. Попробуйте онлайн.
Кевин Круйссен
Хм. пропускает типы для лямбда больше не действительны
только ASCII
@ Только для ASCII Нет, нетипичные лямбды разрешены. Я не мог использовать лямбду здесь, потому что решение использует рекурсию.
Якоб
@Jakob ах, верно> _>
только для ASCII
2

Oracle SQL, 177 байт

Создайте тип коллекции (31 байт):

CREATE TYPE t IS TABLE OF INT;

Затем используйте запрос (146 байт):

WITH n(a,b,c)AS(SELECT a,b,t()FROM i UNION ALL SELECT a,b-1,c MULTISET UNION t(COLUMN_VALUE)FROM n,TABLE(n.a)WHERE b>=0)SELECT c FROM n WHERE b=0

Предполагая, что входные параметры находятся в таблице iсо столбцами aи b:

CREATE TABLE i (a t,b INT) NESTED TABLE a STORE AS t_a;
INSERT INTO i VALUES ( t(1,2,3), 3 );

SQL Fiddle

Результаты :

|     C |
|-------|
| 1,1,1 |
| 1,1,2 |
| 1,1,3 |
| 1,2,1 |
| 1,2,2 |
| 1,2,3 |
| 1,3,1 |
| 1,3,2 |
| 1,3,3 |
| 2,1,1 |
| 2,1,2 |
| 2,1,3 |
| 2,2,1 |
| 2,2,2 |
| 2,2,3 |
| 2,3,1 |
| 2,3,2 |
| 2,3,3 |
| 3,1,1 |
| 3,1,2 |
| 3,1,3 |
| 3,2,1 |
| 3,2,2 |
| 3,2,3 |
| 3,3,1 |
| 3,3,2 |
| 3,3,3 |
mt0
источник
1

Баш , 61 байт

N=$1
shift
IFS=,
printf echo\\t%${N}s ""|sed "s/ /{$*},/g"|sh

Попробуйте онлайн! Я нашел повторяющиеся строки и списки с запятыми на удивление трудно сделать в bash.

Нил
источник
1

Javascript (Node) , 75 байт

c=(m,n,a,i)=>a.length-n?m.map((_,j)=>c(m,n,[...a,m[j]],i+1)):console.log(a)

Рекурсивная функция, которая выводит список на консоль. Где aнаходится пустой массив, и он iравен 0 (не уверен, что это все еще квалифицируется):

c([1,2,3], 3, [], 0);

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

Asleepace
источник
1
Я думаю, что вам придется сделать(m,n,a=[],i=0)=>
Artyer
1

J , 17 байт

]{~(##)#:#@]i.@^[

Как это работает?

Я перечисляю все числа n-digit в системе счисления с основанием длины списка.

            i.         - creates a list from zero to (not including)
         #@]           - the length of the list 
              @^       - to the power of
                [      - n (left argument)
   (##)                - creates a list of n times the length of the list (for the bases)
       #:              - converts all the numbers into lists of digits in the new base
]{~                    - use the digits as indices into the list

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

Гален Иванов
источник
1

CJam , 26 байтов

q~(_"m*:e_"*\'_*@\~W$~:p];

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

Если бы только у CJam были односимвольные команды для декартового произведения и сплющивания.

maxb
источник