Código

Basándose en la excelente respuesta de @MBo, aquí hay una implementación de coincidencia de grafos 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

Según la documentación :

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 dictado devuelto debe ser el doble de grande que A y B.

El los nodos se convierten desde

[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. El id 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 arreglos grandes. La solución de permutación es O(n!) y no será capaz de 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:

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

El problema es una instancia de permutaciones con posiciones restringidas, y hay mucho que se puede decir sobre ellas. En general, se puede construir una matriz de cero-uno NxN M donde M[i][j] es 1 si y solo si se permite position j para el elemento originalmente en position i. El número de las permutaciones que cumplen todas las restricciones son 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, hay algoritmos de tiempo polinómico para determinar si el permanente es 0 o no.

Y ahí es donde las respuestas que tienes comienzan; -) Aquí hay una buena cuenta de cómo el " es el permanente 0?"la pregunta se responde eficientemente considerando emparejamientos perfectos en gráficos bipartitos:

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

Así que, 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, añadida más adelante: Debería aclarar esa última parte. Dada cualquier matriz de" permutación restringida " M, es fácil construir enteros "listas de divisibility" correspondientes a él. 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é 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 luego "dice" que B[0] (= 2) no puede dividir A[0], pero debe dividir A[1], A[2], y A[3]. Y así sucesivamente. 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 tales que cada elemento de A es divisible por el elemento correspondiente de la permutada B.

Esta no es la respuesta definitiva, pero creo que esto podría ser algo valioso. Primero puede enumerar los factores (1 y sí mismo incluidos) de todos los elementos de 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 en ella(dividir uniformemente). Dado que no tenemos algunos factores en la lista que estamos comprobando ([2,7,5,3,12,3]), Esta lista puede filtrarse como:

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

Aquí, 5 se necesitan dos lugares (donde no tenemos ninguna opción en absoluto), pero solo tenemos un 5, por lo tanto, podemos más o menos parar aquí y decir que el caso es falso aquí.

Digamos que tuvimos [2,7,5,3,5,3] en su lugar:

, Entonces tendríamos la opción como tal:

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

Dado que 5 se necesita en dos lugares:

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

También se garantiza 2:

[{2},(2,3),(2,3),{5},(3,7),{5}] Ahora, puesto que se toma 2, los dos lugares de 3 están asegurados:

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

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

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