Вдохновленный (с объяснением украдено у) это

Фон

Скажем, у вас есть два списка A = [a_1, a_2, ..., a_n]и B = [b_1, b_2, ..., b_n]целых чисел. Мы говорим, Aчто потенциально делим на то, Bесли есть перестановка, Bкоторая делает a_iделимым b_iна всех i. Тогда возникает проблема: можно ли изменить порядок (т. Е. Переставить), Bчтобы a_iон делился b_iна всех i? Например, если у вас есть

A = [6, 12, 8]
B = [3, 4, 6]

Тогда ответ будет True, так как Bможет быть заказана быть , B = [3, 6, 4]и тогда мы бы что a_1 / b_1 = 2, a_2 / b_2 = 2и a_3 / b_3 = 2, все из которых являются целыми числами, поэтому Aпотенциально-кратно B.

В качестве примера, который должен выводить False, мы могли бы иметь:

A = [10, 12, 6, 5, 21, 25]
B = [2, 7, 5, 3, 12, 3]

Причина в Falseтом, что мы не можем переупорядочить, Bкогда 25 и 5 A, но единственным делителем Bбудет 5, так что один будет опущен.

Твое задание

Ваша задача, очевидно, определить, являются ли два списка (заданных в качестве входных данных) потенциально делимыми. Вы можете принимать входные данные любым приемлемым способом, как при выводе.

Дубликаты в списках возможны, и единственное ограничение размера на целые числа - это ваш язык. Все целые числа в обоих списках будут больше 0, и оба списка будут одинакового размера.

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

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

Контрольные примеры

Input, input => output

[6, 12, 8], [3, 4, 6] => True
[10, 5, 7], [1, 5, 100] => False
[14, 10053, 6, 9] [1,1,1,1] => True
[12] [7] => False
[0, 6, 19, 1, 3] [2, 3, 4, 5, 6] => undefined

Желе , 5 байт

Œ!%ḄẠ

Возвращает 0 для True , 1 для False .

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

Как это устроено

Œ!%ḄẠ  Main link. Arguments: A, B (arrays)

Œ!     Generate all permutations of A.
  %    Take each permutation modulo B (element-wise).
   Ḅ   Convert all resulting arrays from binary to integer.
       This yields 0 iff the permutation is divisible by B.
    Ạ  All; yield 0 if the result contains a 0, 1 otherwise.

Шелуха , 7 6 5 байт

Сохранено 2 байта благодаря @Zgarb

▼▲‡¦P

Принимает аргументы в обратном порядке и возвращает 1для Trueи 0для False.

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

объяснение

    P     -- Permutations of the first argument
  ‡       -- Deep zip (vectorises function) with second argument
   ¦      --   Does x divide y
 ▲        -- Get the maximum of that list, returns [1,1...1] if present
▼         -- Get the minimum of that list, will return 0 unless the list is all 1s

05AB1E , 7 байтов

Входные данные: принимает списки B и A (обратный порядок).
Выходные данные: 1, если истина, 0 в противном случае

œvIyÖPM

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

Пояснения:

œvIyÖPM    Complete program
œ          Pushes all permutations of B as a list
 v         For each permutation
  I        Pushes last input on top of the stack
   yÖ      Computes a % b == 0 for each element of A and B
     P     Pushes the total product of the list
      M    Pushes the largest number on top of the stack

MATL , 8 7 6 байт

1 байт, используя идею ответа от желе Денниса

Y@\!aA

Входы есть B, тогда A. Вывод 0если делится или 1если нет.

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

объяснение

Y@     % Implicit input: row vector B. Matrix of all permutations, each on a row
\      % Implicit input: row vector A. Modulo, element-wise with broadcast. Gives
       % a matrix in which each row contains the moduli of each permutation of B
       % with respect to A
!a     % True for rows that contain at least a nonzero value
A      % True if all values are true. Implicit display

Mathematica, 52 байта

Cases[Permutations@#2,p_/;And@@IntegerQ/@(#/p)]!={}& 

спасибо @ngenisis за -5 байт

JavaScript (ES6), 67 63 байта

Возвращает логическое значение.

f=([x,...a],b)=>!x||b.some((y,i)=>x%y?0:f(a,c=[...b],c[i]=1/0))

Контрольные примеры

f=([x,...a],b)=>!x||b.some((y,i)=>x%y?0:f(a,c=[...b],c[i]=1/0))

console.log(f([6, 12, 8],[3, 4, 6]))        // true
console.log(f([10, 5, 7],[1, 5, 100]))      // false
console.log(f([14, 10053, 6, 9],[1,1,1,1])) // true
console.log(f([12],[7]))                    // false

Haskell , 79 74 68 62 61 байт

import Data.List
f a=any((<1).sum.zipWith rem a).permutations

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

Сохранено 1 байт благодаря @nimi

R + комбинат , 69 66 58 байт

-3 байта благодаря Ярко Дуббелдаму

еще -8 байт благодаря Ярко

function(a,b)any(combinat::permn(b,function(x)all(!a%%x)))

как ни странно, R не имеет встроенной функции для генерации всех перестановок. Возвращает логическое значение.

Кроме того, со вторым улучшением Ярко приводит anyсписок к вектору logicalс предупреждением.

Попробуйте онлайн! (Г-скрипка)

Mathematica, 42 байта

MemberQ[Permutations@#2,a_/;And@@(a∣#)]&

Желе , 7 байт

Œ!ọẠ€1e

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

Факторная сложность в длине списка.

Pyth - 11 байт

sm!s%Vdvz.p

Тестовый пакет .

J, 27 байт

0=[:*/(A.~i.@!@#)@]+/@:|"1[

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

Принимает первый список в качестве левого аргумента и второй список в качестве правого.

CJam, 20 17 байт

:A;e!{A\.%:+!}#W>

Тестовая версия

Функция, которая принимает массив B в качестве первого аргумента и массив A в качестве второго аргумента. Обратите внимание, что в тестовой версии я переключаю порядок на A, а затем B.

JavaScript (ES6), 100 байт

f=(a,b)=>!a[0]||a.some((c,i)=>b.some((d,j)=>c%d<1&f(e=[...a],d=[...b],e.splice(i,1),d.splice(j,1))))

Несколько неэффективно; дополнительный &ускорит это.

PHP, 112 180 178 байт

Я думал слишком коротко.

function($a,$b){for($p=array_keys($b);++$i<count($b);){foreach($b as$k=>$x)$f|=$a[$k]%$x;if($f=!$f)return 1;$p[$i]?[$b[$j],$b[$i],$i]=[$b[$i],$b[$j=$i%2*--$p[$i]],0]:$p[$i]=$i;}}

анонимная функция принимает два массива, возвращает NULLложное и 1правдивое.
Выдает ошибку, если второй массив содержит 0.

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

C (gcc) , 191 байт

#define F(v)for(i=0;i<v;++i){
#define X if(f(s,n,a,b))return 1
j;f(s,n,a,b,i)int*a,*b;{if(--n){F(n)X;j=i*(n%2);b[j]^=b[n];b[n]^=b[j];b[j]^=b[n];}X;}else{F(s)if(a[i]%b[i])return 0;}return 1;}}

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

Использование: f(int size, int size, int *a, int *b)

возвращает, 1если делится,0 противном случае. Смотрите пример использования на TIO.

(Должен делать перестановки трудный путь в C, так что это вряд ли конкурентно)

Perl 6 , 38 байт

На самом деле ответ @ nwellnhof кажется слишком читабельным, поэтому я решил следовать хорошей традиции Perl, заключающейся в коде только для записи :—).

1 байт сохранен благодаря @nwellnhof.

{min max (@^a,) XZ%% @^b.permutations}

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

Что он делает: это анонимная функция, которая принимает два аргумента списка. Когда мы говорим @^a, мы имеем в виду первое, когда @^bэто второе.

(@^a,)список , содержащий список @^a. @^b.permutationsсписок всех перестановок @^b. Оператор "XZ %%" создает все возможные пары из этого одного списка слева и все перестановки справа и использует для них оператор "Z %%", который является стандартной операцией "zip" с использованием оператора делимости %%.

maxОператор дает наибольший элемент списка (в данном случае это список , который имеет наиболее True«S в нем). Затем мы уменьшаем его, используя логический оператор AND, чтобы увидеть, все ли элементы этого «наиболее верного» списка истинны, и это результат. Это почти точная копия того, что написал @nwellnhof, просто используя неясные операторы, чтобы сбрить байты.

Брахилог , 6 байт

pᵐz%ᵛ0

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

Предикат успешно выполняется, если два списка потенциально делимы, и не выполняется, если это не так.

pᵐ        For some pair of permutations of the two input lists,
  z       for each pair of corresponding elements
   %ᵛ0    the first mod the second is always zero.

Python 2 , 92 байта

lambda a,b:any(all(x%y<1for x,y in zip(a,p))for p in permutations(b))
from itertools import*

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

Ваша базовая реализация.

Python 2 , 90 байт

lambda a,b:any(sum(map(int.__mod__,a,p))<1for p in permutations(b))
from itertools import*

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

Рубин , 56 байт

->x,y{x.permutation.any?{|p|p.zip(y).all?{|a,b|a%b==0}}}

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

Довольно просто, использует тот факт, что permutationсуществует.

Скала, 60 байт

Golfed:

a=>b=>b.permutations exists(a zip _ forall(p=>p._1%p._2==0))

Ungolfed:

a=>b=>         // Function literal taking 2 lists of integers, a and b.
b.permutations // All permutations of b.
exists(        // Whether the given function is true for any element.
a zip _        // Zips a and the current permutation of b into a list of pairs.
forall(        // Whether the given function is true for all elements.
p=>            // Function literal taking a pair of integers.
p._1%p._2==0)) // If the remainder of integer division between the members of the pair is 0.

Джапт , 12 11 байт

Выходы trueили false.

Vá de@gY vX

Проверь это

объяснение

Неявный ввод массивов U& V( A& B, соответственно)

Vá

Создать массив всех перестановок V.

d

Проверьте, возвращает ли какой-либо из элементов (подмассивов) значение true.

e@

Проверьте, возвращает ли каждый элемент в текущем подмассиве значение true, когда передается через следующую функцию, Xпричем текущий элемент и Yтекущий индекс.

gY

Получить элемент в Uиндекс Y.

vX

Проверьте, если это делится на X.