Zainspirowany (z wyjaśnieniem skradzione) to

tło

Załóżmy, że masz dwie listy A = [a_1, a_2, ..., a_n]i B = [b_1, b_2, ..., b_n]liczby całkowite. Mówimy, że Ajest potencjalnie podzielna przez, Bjeśli istnieje permutacja, Bktóra czyni a_ipodzielną przez b_iwszystkich i. Problem polega zatem na tym: czy można zmienić kolejność (tj. Permutację), Baby wszyscy mogli ją a_ipodzielić ? Na przykład jeśli maszb_ii

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

Wtedy będzie odpowiedź True, jak Bmożna być zreorganizowane B = [3, 6, 4]i wtedy mamy, że a_1 / b_1 = 2, a_2 / b_2 = 2i a_3 / b_3 = 2, z których wszystkie są liczbami całkowitymi, więc Ajest potencjalnie podzielna przez B.

Jako przykład, który powinien wypisać False, możemy mieć:

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

Powodem jest Falseto, że nie możemy zmienić kolejności, Bponieważ 25 i 5 są w Aśrodku, ale jedynym dzielnikiem Bbędzie 5, więc jeden zostanie pominięty.

Twoje zadanie

Twoim zadaniem jest oczywiście ustalenie, czy dwie listy (podane jako dane wejściowe) są potencjalnie podzielne. Możesz przyjmować dane wejściowe w dowolny zaakceptowany sposób, tak jak w przypadku danych wyjściowych.

Możliwe są duplikaty na listach, a jedynym ograniczeniem wielkości liczb całkowitych jest Twój język. Wszystkie liczby całkowite na obu listach będą większe niż 0, a obie listy będą jednakowego rozmiaru.

Podobnie jak w przypadku wszystkich problemów decyzyjnych, wartości wyjściowe muszą być 2 odrębnymi wartościami, które reprezentują prawda i fałsz.

To jest golf golfowy, więc wygrywa najkrótszy kod!

Przypadki testowe

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

Galaretka , 5 bajtów

Œ!%ḄẠ

Zwraca 0 dla wartości True , 1 dla wartości False .

Wypróbuj online!

Jak to działa

Œ!%ḄẠ  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.

Łuska , 7 6 5 bajtów

Zaoszczędź 2 bajty dzięki @Zgarb

▼▲‡¦P

Bierze argenty w odwrotnej kolejności i zwraca 1za Truei 0za False.

Wypróbuj online!

Wyjaśnienie

    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 bajtów

Dane wejściowe: pobiera listy B i A (w odwrotnej kolejności) Dane
wyjściowe: 1, gdy jest prawdziwe, 0 w przeciwnym razie

œvIyÖPM

Wypróbuj online!

Objaśnienia:

œ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 bajtów

1 bajt off przy użyciu pomysłu z odpowiedzi Jelnisa ​​Jelly

Y@\!aA

Dane wejściowe są Bzatem A. Dane wyjściowe są 0podzielne lub 1nie.

Wypróbuj online!

Wyjaśnienie

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 bajty

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

dzięki @ngenisis za -5 bajtów

JavaScript (ES6), 67 63 bajtów

Zwraca wartość logiczną.

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

Przypadki testowe

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 bajtów

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

Wypróbuj online!

Zapisano 1 bajt dzięki @nimi

Kombinacja R + , 69 66 58 bajtów

-3 bajty dzięki Jarko Dubbeldam

kolejne -8 bajtów dzięki Jarko

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

co dziwne, R nie ma wbudowanego do generowania wszystkich permutacji. Zwraca wartość logiczną.

Dodatkowo, dzięki drugiej poprawce Jarko, anyprzymusza listę do wektora logicalz ostrzeżeniem.

Wypróbuj online! (skrzypce r)

Mathematica, 42 bajty

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

Galaretka , 7 bajtów

Œ!ọẠ€1e

Wypróbuj online!

Złożoność czynnikowa długości listy.

Pyth - 11 bajtów

sm!s%Vdvz.p

Pakiet testowy .

J, 27 bajtów

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

Wypróbuj online!

Pobiera pierwszą listę jako lewy argument, a drugą listę jako prawą.

CJam, 20 17 bajtów

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

Wersja testowa

Funkcja, która przyjmuje tablicę B jako pierwszy argument, a tablicę A jako drugi argument. Zauważ, że w wersji testowej zmieniam kolejność na A, a następnie B.

JavaScript (ES6), 100 bajtów

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

Nieco nieefektywne; dodatkowy &przyspieszyłby to.

PHP, 112 180 178 bajtów

Myślałem zbyt krótko.

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;}}

funkcja anonimowa przyjmuje dwie tablice, zwraca NULLza fałsz i 1za prawdę.
Zgłasza błąd, jeśli druga tablica zawiera0 .

Wypróbuj online .

C (gcc) , 191 bajtów

#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;}}

Wypróbuj online!

Stosowanie: f(int size, int size, int *a, int *b)

zwraca, 1jeśli podzielne, w 0przeciwnym razie. Zobacz przykładowe użycie w TIO.

(Muszę robić permutacje w sposób trudny w C, więc nie jest to konkurencyjne)

Perl 6 , 38 bajtów

Właściwie odpowiedź @ nwellnhof wydaje się zbyt czytelna, dlatego postanowiłem podążać za dobrą tradycją Perla polegającą na pisaniu kodu :—).

1 bajt zapisany dzięki @nwellnhof.

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

Wypróbuj online!

Co robi: Jest to anonimowa funkcja, która pobiera dwa argumenty z listy. Kiedy mówimy @^a, mamy na myśli pierwszy, kiedy@^b to drugi.

(@^a,)to lista zawierająca listę @^a. @^b.permutationsjest listą wszystkich permutacji @^b. Operator „XZ %%” tworzy wszystkie możliwe pary tej jednej listy po lewej stronie i wszystkie permutacje po prawej stronie oraz używa operatora „Z %%” na nich, który jest standardową operacją „zip” przy użyciu operatora podzielności %%.

maxOperator daje największy element listy (w tym przypadku jest to lista, która ma większość Truew niej jest). Następnie redukujemy go za pomocą logicznego operatora AND, aby sprawdzić, czy wszystkie elementy tej „najbardziej prawdziwej” listy są prawdziwe, i to jest wynik. To prawie dokładna kopia tego, co napisał @nwellnhof, po prostu używając niejasnych operatorów, aby zgolić bajty.

Brachylog , 6 bajtów

pᵐz%ᵛ0

Wypróbuj online!

Predykat się powiedzie, jeśli dwie listy są potencjalnie podzielne, a jeśli nie, to nie powiedzie się.

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 bajty

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

Wypróbuj online!

Twoja podstawowa implementacja.

Python 2 , 90 bajtów

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

Wypróbuj online!

Rubinowy , 56 bajtów

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

Wypróbuj online!

Dość proste, wykorzystuje fakt, który permutationistnieje.

Scala, 60 bajtów

Gra w golfa:

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

Nie golfowany:

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.

Japt , 12 11 bajtów

Wyjścia truelub false.

Vá de@gY vX

Sprawdź to

Wyjaśnienie

Niejawny wejście matryc Ui V( Ai B, odpowiednio)

Vá

Wygeneruj tablicę wszystkich permutacji V.

d

Sprawdź, czy którykolwiek z elementów (pod-tablic) zwraca wartość true.

e@

Sprawdź, czy każdy element w bieżącej pod-macierzy zwraca wartość true po przejściu przez następującą funkcję, Xbędąc bieżącym elementem i Ybieżącym indeksem.

gY

Pobierz element w Uindeksie Y.

vX

Sprawdź, czy można go podzielić X.