As listas são divisíveis?

20

Inspirado (com a explicação roubada) desta

fundo

Digamos que você tenha duas listas A = [a_1, a_2, ..., a_n]e B = [b_1, b_2, ..., b_n]números inteiros. Dizemos que Aé potencialmente divisível por Bse existe uma permutação Bque torna a_idivisível por b_itodos i. O problema é então: é possível reordenar (isto é, permutar) Bpara que a_iseja divisível por b_itodos i? Por exemplo, se você tiver

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

Então a resposta seria True, como Bpodem ser reordenados para ser B = [3, 6, 4]e então teríamos que a_1 / b_1 = 2, a_2 / b_2 = 2e a_3 / b_3 = 2, todos os quais são inteiros, então Aé potencialmente divisível por B.

Como um exemplo que deve Falsegerar, poderíamos ter:

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

A razão Falseé que não podemos reordenar, Bpois 25 e 5 estão dentro A, mas o único divisor em Bseria 5, então um seria deixado de fora.

Sua tarefa

Sua tarefa é, obviamente, determinar se duas listas (fornecidas como entrada) são potencialmente divisíveis. Você pode receber informações de qualquer maneira aceita, como na saída.

As duplicatas nas listas são uma possibilidade e as únicas restrições de tamanho nos números inteiros são o seu idioma. Todos os números inteiros nas duas listas serão maiores que 0 e as duas listas terão o mesmo tamanho.

Como em todos os valores de saída devem ser 2 valores distintos que representam verdadeiro e falso.

Este é um então o código mais curto vence!

Casos de teste

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
caird coinheringaahing
fonte
3
@Shaggy da questão: ambas as listas serão de igual tamanho
Caird coinheringaahing
2
Por que o último caso de teste não está definido?
Dennis
1
@Dennis uma das listas tem um 0 nele
caird coinheringaahing
1
Direita. (Não sei por que, 0 é divisível por todos os números inteiros.) As duas saídas precisam ser verdadeiras e falsas ou consistentes?
Dennis
@ Dennis 1) é em caso 0 está na segunda lista, para evitar 0 erros de divisão 2) apenas consistente
caird coinheringaahing

Respostas:

10

Gelatina , 5 bytes

Œ!%ḄẠ

Retorna 0 para True , 1 para False .

Experimente online!

Como funciona

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

Casca , 7 6 5 bytes

Guardado 2 bytes graças a @Zgarb

▼▲‡¦P

Toma argents na ordem inversa e retorna 1para Truee 0para False.

Experimente online!

Explicação

    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
H.PWiz
fonte
VΠMz¦Pdeve funcionar para 6 bytes.
Zgarb 27/08/17
Esses são considerados "dois valores distintos"?
geokavel
Ah, e Mzpode ser .
Zgarb 27/08/17
Eu acho que você precisa em ▼▲vez de ▲▼. Boa idéia em qualquer caso!
Zgarb 27/08/17
5

05AB1E , 7 bytes

Entrada: aceita as listas B e A (ordem inversa)
Saída: 1 quando verdadeiro, 0 caso contrário

œvIyÖPM

Experimente online!

Explicações:

œ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
escoteiro
fonte
5

MATL , 8 7 6 bytes

1 byte usando uma ideia da resposta de Dennis 'Jelly

Y@\!aA

Entradas são B, então A. A saída é 0divisível ou 1não.

Experimente online!

Explicação

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
Luis Mendo
fonte
3

Mathematica, 52 bytes

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

obrigado @ngenisis por -5 bytes

J42161217
fonte
2
Casesé geralmente mais curto:Cases[Permutations@#2,p_/;And@@IntegerQ/@(#/p)]!={}&
ngenisis 27/08
3

JavaScript (ES6), 67 63 bytes

Retorna um booleano.

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

Casos de teste

Arnauld
fonte
3

Haskell , 79 74 68 62 61 bytes

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

Experimente online!

Guardado 1 byte graças a @nimi

jferard
fonte
1
61 bytes: f a=any((<1).sum.zipWith rem a).permutations.
nimi
3

R + combinado , 69 66 58 bytes

-3 bytes graças a Jarko Dubbeldam

mais -8 bytes graças ao Jarko

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

estranhamente, R não tem um builtin para gerar todas as permutações. Retorna um booleano.

Além disso, com o segundo aprimoramento de Jarko, anya lista é forçada a um vetor de logicalcom um aviso.

Experimente online! (r-violino)

Giuseppe
fonte
1
Tudo (x <1) é mais longo que qualquer (! X) e você deve ser capaz de substituir soma por qualquer outra coisa #
JAD
@JarkoDubbeldam good call. obrigado.
Giuseppe
Ah, e você pode omitir não listar, sim por coerção implícita.
JAD 28/08
@JarkoDubbeldam excellent.
27417 Giuseppe
2

Mathematica, 42 bytes

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

Geléia , 7 bytes

Œ!ọẠ€1e

Experimente online!

Complexidade fatorial no comprimento da lista.

Freira Furada
fonte
Jelly realmente não tem um anybuiltin? TIL
caird coinheringaahing 27/08/17
1

Pitão - 11 bytes

sm!s%Vdvz.p

Conjunto de Teste .

Maltysen
fonte
Você me venceu: (((- estava prestes a postar algo semelhante
Mr. Xcoder
1

J, 27 bytes

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

Experimente online!

Leva a primeira lista como argumento à esquerda e a segunda lista como a direita.

Cole
fonte
1
21 bytes(|"1~e.~0*[)i.@!@#A.]
milhas
1

CJam, 20 17 bytes

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

Versão de teste

Função que usa a matriz B como o primeiro argumento e a matriz A como o segundo argumento. Observe que, na versão de teste, alterno a ordem para A e depois para B.

geokavel
fonte
1

JavaScript (ES6), 100 bytes

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

Um pouco ineficiente; um extra &aceleraria.

Neil
fonte
1

PHP, 112 180 178 bytes

Eu estava pensando muito curto.

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

A função anônima recebe duas matrizes, retorna NULLpor falsidade e 1por verdade.
Lança um erro se a segunda matriz contiver 0.

Experimente online .

Titus
fonte
Imprime o resultado errado para $f([6,5],[3,5]).
Nwellnhof 28/08/19
@nwellnhof fixed. obrigado por perceber.
Titus
1

C (gcc) , 191 bytes

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

Experimente online!

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

retorna 1se divisível,0 caso contrário. Veja exemplo de uso no TIO.

(Preciso fazer permutações da maneira mais difícil em C, então isso não é competitivo)

Felix Palmen
fonte
1

Perl 6 , 38 bytes

Na verdade, a resposta do @ nwellnhof parece ser muito legível, então decidi seguir a boa tradição Perl do código somente para gravação :—).

1 byte salvo graças a @nwellnhof.

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

Experimente online!

O que faz: é uma função anônima que recebe dois argumentos de lista. Quando dizemos @^a, queremos dizer o primeiro, quando@^b , é o segundo.

(@^a,)é uma lista que contém a lista @^a. @^b.permutationsé a lista de todas as permutações de@^b . O operador "XZ %%" cria todos os pares possíveis dessa lista à esquerda e todas as permutações à direita e usa o operador "Z %%" neles, que é a operação "zip" padrão usando o operador de divisibilidade %%.

O maxoperador fornece o maior elemento da lista (nesse caso, é a lista que contém mais True). Em seguida, reduzimos isso usando o operador AND lógico para ver se todos os elementos dessa lista "mais verdadeira" são verdadeiros, e esse é o resultado. É uma cópia quase exata do que o @nwellnhof escreveu, apenas usando operadores obscuros para cortar bytes.

Ramillies
fonte
Ele diz permutationsque é claramente legível demais;)
caird coinheringaahing
Bem, o Perl 6 tem um modelo de introspecção realmente poderoso. Talvez eu pudesse estudá-lo para obscurecer essa ligação? : D
Ramillies
Substitua [&&]por minpara salvar outro byte.
Nwellnhof 28/08/19
Você pode remover os espaços ao redor doXZ%%
Jo King
Eu gostaria que algo como {all (@^a,)Z%%@^b.permutations.any}fosse possível
Jo King
1

Braquilog , 6 bytes

pᵐz%ᵛ0

Experimente online!

O predicado será bem-sucedido se as duas listas forem potencialmente divisíveis e falhará se não forem.

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.
String não relacionada
fonte
0

Python 2 , 92 bytes

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

Experimente online!

Sua implementação básica.

Chas Brown
fonte
0

Python 2 , 90 bytes

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

Experimente online!

ovs
fonte
0

Ruby , 56 bytes

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

Experimente online!

Bastante simples, explora o fato de que permutationexiste.

ymbirtt
fonte
0

Scala, 60 bytes

Golfe:

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.
Llew Vallis
fonte
0

Japonês , 12 11 bytes

Saídas trueou false.

Vá de@gY vX

Teste-o


Explicação

Entrada implícita de matrizes U& V( A& B, respectivamente)

Gere uma matriz de todas as permutações de V.

d

Verifique se algum dos elementos (sub-matrizes) retorna verdadeiro.

e@

Verifique se todos os elementos no sub-array atual retornam true quando passados ​​pela função a seguir, Xsendo o elemento atual e Yo índice atual.

gY

Coloque o elemento em Uindex Y.

vX

Verifique se é divisível por X.

Shaggy
fonte