python - prime - ¿Es una lista(potencialmente) divisible por otra?

python get prime numbers

Question

Problema

Supongamos que tiene dos listas A = [a_1, a_2, ..., a_n] y B = [b_1, b_2, ..., b_n] de enteros. Decimos que A es potencialmente divisible por B si hay una permutación de B que hace que a_i sea ​​divisible por b_i para todo i . El problema es entonces: ¿es posible reordenar (es decir, permutar) B para que a_i sea ​​divisible por b_i para todo i ? Por ejemplo, si tienes

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

Entonces la respuesta sería True , ya que B puede reordenarse para que sea B = [3, 6, 4] y entonces tendríamos que a_1 / b_1 = 2 , a_2 / b_2 = 2 , y a_3 / b_3 = 2 , todos que son enteros, por lo que A es potencialmente divisible por B

Como ejemplo que debería mostrar False , podríamos tener:

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

La razón por la que esto es False es que no podemos reordenar B ya que 25 y 5 están en A , pero el único divisor en B sería 5, por lo que uno quedaría fuera.

Enfoque

Obviamente, el enfoque directo sería obtener todas las permutaciones de B y ver si uno satisfaría la divisibilidad potencial , algo en la línea de:

import itertools
def is_potentially_divisible(A, B):
perms = itertools.permutations(B)
divisible = lambda ls: all( x % y == 0 for x, y in zip(A, ls))
return any(divisible(perm) for perm in perms)

Pregunta

¿Cuál es la forma más rápida de saber si una lista es potencialmente divisible por otra lista? ¿Alguna idea? Estaba pensando si hay una manera inteligente de hacer esto con los números primos , pero no pude encontrar una solución.

¡Muy apreciado!

Editar : Probablemente sea irrelevante para la mayoría de ustedes, pero en aras de la exhaustividad, explicaré mi motivación. En la teoría de grupos, existe una conjetura sobre grupos simples finitos sobre si existe o no una biyección de los caracteres irreducibles y las clases de conjugación del grupo, de modo que cada grado de carácter divide el tamaño de clase correspondiente. Por ejemplo, para U6 (4), aquí se muestran cómo se verían A y B Bastante grandes listas, ¡cuidado!

Answer 1

Código

Sobre la base de la excelente answer @ MBo, aquí hay una implementación de la coincidencia de gráficos bipartitos usando networkx .

import networkx as nx
def is_potentially_divisible(multiples, divisors):
if len(multiples) != len(divisors):
return False
g = nx.Graph()
g.add_nodes_from([(''A'', a, i) for i, a in enumerate(multiples)], bipartite=0)
g.add_nodes_from([(''B'', b, j) for j, b in enumerate(divisors)], bipartite=1)
edges = [((''A'', a, i), (''B'', b, j)) for i, a in enumerate(multiples)
for j, b in enumerate(divisors) if a % b == 0]
g.add_edges_from(edges)
m = nx.bipartite.maximum_matching(g)
return len(m) // 2 == len(multiples)
print(is_potentially_divisible([6, 12, 8], [3, 4, 6]))
# True
print(is_potentially_divisible([6, 12, 8], [3, 4, 3]))
# True
print(is_potentially_divisible([10, 12, 6, 5, 21, 25], [2, 7, 5, 3, 12, 3]))
# False

Notas

De acuerdo con la documentation :

El diccionario devuelto por maximum_matching () incluye una asignación para vértices en los conjuntos de vértices izquierdo y derecho.

Significa que el dict devuelto debe ser el doble de grande que A y B

Los nodos se convierten de

[10, 12, 6, 5, 21, 25]

a:

[(''A'', 10, 0), (''A'', 12, 1), (''A'', 6, 2), (''A'', 5, 3), (''A'', 21, 4), (''A'', 25, 5)]

para evitar colisiones entre nodos de A y B La identificación también se agrega para mantener los nodos distintos en caso de duplicados.

Eficiencia

El método maximum_matching utiliza el algoritmo Hopcroft-Karp , que se ejecuta en O(n**2.5) en el peor de los casos. La generación del gráfico es O(n**2) , por lo que todo el método se ejecuta en O(n**2.5) . Debería funcionar bien con matrices grandes. La solución de permutación es O(n!) Y no podrá procesar matrices con 20 elementos.

Con diagramas

Si está interesado en un diagrama que muestre la mejor coincidencia, puede mezclar matplotlib y networkx:

import networkx as nx
import matplotlib.pyplot as plt
def is_potentially_divisible(multiples, divisors):
if len(multiples) != len(divisors):
return False
g = nx.Graph()
l = [(''l'', a, i) for i, a in enumerate(multiples)]
r = [(''r'', b, j) for j, b in enumerate(divisors)]
g.add_nodes_from(l, bipartite=0)
g.add_nodes_from(r, bipartite=1)
edges = [(a,b) for a in l for b in r if a[1] % b[1]== 0]
g.add_edges_from(edges)
pos = {}
pos.update((node, (1, index)) for index, node in enumerate(l))
pos.update((node, (2, index)) for index, node in enumerate(r))
m = nx.bipartite.maximum_matching(g)
colors = [''blue'' if m.get(a) == b else ''gray'' for a,b in edges]
nx.draw_networkx(g, pos=pos, arrows=False, labels = {n:n[1] for n in g.nodes()}, edge_color=colors)
plt.axis(''off'')
plt.show()
return len(m) // 2 == len(multiples)
print(is_potentially_divisible([6, 12, 8], [3, 4, 6]))
# True
print(is_potentially_divisible([6, 12, 8], [3, 4, 3]))
# True
print(is_potentially_divisible([10, 12, 6, 5, 21, 25], [2, 7, 5, 3, 12, 3]))
# False

Aquí están los diagramas correspondientes:

Answer 2

Como te sientes cómodo con las matemáticas, solo quiero agregar un brillo a las otras respuestas. Los términos para buscar se muestran en negrita .

El problema es una instancia de permutaciones con posiciones restringidas , y hay mucho que decir sobre ellas. En general, se puede construir una matriz NxN cero M donde M[i][j] es 1 si y solo si se permite la posición j para el elemento originalmente en la posición i . El número de permutaciones distintas que cumplen todas las restricciones es entonces el permanente de M (definido de la misma manera que el determinante, excepto que todos los términos son no negativos).

Por desgracia, a diferencia del determinante, no hay formas generales conocidas de calcular el permanente más rápido que el exponencial en N Sin embargo, existen algoritmos de tiempo polinomiales para determinar si el permanente es o no 0.

Y ahí es donde comienzan las respuestas que obtuviste ;-) Aquí hay una buena cuenta de cómo el "¿es el 0 permanente?" La pregunta se responde de manera eficiente al considerar coincidencias perfectas en gráficos bipartitos:

https://cstheory.stackexchange.com/questions/32885/matrix-permanent-is-0

Entonces, en la práctica, es poco probable que encuentres un enfoque general más rápido que el que @Eric Duminil dio en su respuesta.

Nota, agregada más tarde: debería aclarar esa última parte. Dada cualquier matriz de "permutación restringida" M , es fácil construir "listas de divisibilidad" enteras que le correspondan. Por lo tanto, su problema específico no es más fácil que el problema general, a menos que tal vez haya algo especial sobre qué números enteros pueden aparecer en sus listas.

Por ejemplo, supongamos que M es

0 1 1 1
1 0 1 1
1 1 0 1
1 1 1 0

Vea las filas como representando los primeros 4 primos, que también son los valores en B :

B = [2, 3, 5, 7]

La primera fila "dice" que B[0] (= 2) no puede dividir A[0] , pero debe dividir A[1] , A[2] y A[3] . Y así. Por construcción,

A = [3*5*7, 2*5*7, 2*3*7, 2*3*5]
B = [2, 3, 5, 7]

corresponde a M Y hay permanent(M) = 9 formas de permutar B tal manera que cada elemento de A es divisible por el elemento correspondiente de B permutado.

Answer 3

Construir estructura de gráfico bipartito: conecte a[i] con todos sus divisores de b[] .

Luego encuentre la coincidencia máxima y verifique si es una coincidencia perfecta (el número de aristas en la coincidencia es igual al número de pares (si se dirige el gráfico) o al número duplicado).

Implementación arbitraria del algoritmo Kuhn elegido aquí .

Upd:
@Eric Duminil hizo una gran implementación concisa de Python aquí

Este enfoque tiene una complejidad polinómica de O (n ^ 2) a O (n ^ 3) dependiendo del algoritmo de coincidencia elegido y el número de aristas (pares de división) contra la complejidad factorial para el algoritmo de fuerza bruta.

Answer 4

Esta no es la respuesta definitiva, pero creo que podría ser algo valioso. Primero puede enumerar los factores (1 y él incluido) de todos los elementos en la lista [(1,2,5,10),(1,2,3,6,12),(1,2,3,6),(1,5),(1,3,7,21),(1,5,25)] . La lista que estamos buscando debe tener uno de los factores (para dividir equitativamente). Dado que no tenemos algunos factores en la lista que estamos comprobando ( [2,7,5,3,12,3] ) Esta lista se puede filtrar como:

[(2,5),(2,3,12),(2,3),(5),(3,7),(5)]

Aquí, se necesitan 5 dos lugares (donde no tenemos ninguna opción), pero solo tenemos un 5, por lo que podemos detenernos aquí y decir que el caso es falso aquí.

Digamos que teníamos [2,7,5,3,5,3] lugar:

Entonces tendríamos la opción como tal:

[(2,5),(2,3),(2,3),(5),(3,7),(5)]

Como se necesita 5 en dos lugares:

[(2),(2,3),(2,3),{5},(3,7),{5}] Donde {} significa posición asegurada.

También 2 está asegurado:

[{2},(2,3),(2,3),{5},(3,7),{5}] Ahora, dado que se toma 2, se aseguran los dos lugares de 3:

[{2},{3},{3},{5},(3,7),{5}] Ahora, por supuesto, se toman 3 y se garantiza 7:

[{2},{3},{3},{5},{7},{5}] . que todavía es consistente con nuestra lista, por lo que el caso es cierto. Recuerde que estaremos observando las consistencias con nuestra lista en cada iteración donde podamos salir fácilmente.

Answer 5

Puedes probar esto:

import itertools
def potentially_divisible(A, B):
A = itertools.permutations(A, len(A))
return len([i for i in A if all(c%d == 0 for c, d in zip(i, B))]) > 0
l1 = [6, 12, 8]
l2 = [3, 4, 6]
print(potentially_divisible(l1, l2))

Salida:

True

Otro ejemplo:

l1 = [10, 12, 6, 5, 21, 25]
l2 = [2, 7, 5, 3, 12, 3]
print(potentially_divisible(l1, l2))

Salida:

False