код

здание на @MBo отлично ответ, вот реализация двудольного сопоставления графов с помощью 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

Примечания

по словам документация:

словарь, возвращаемый maximum_matching (), содержит сопоставление для вершины как в левом, так и в правом множествах вершин.

это означает, что возвращенный дикт должно быть в два раза больше, чем A и B.

узлы преобразуются из

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

to:

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

во избежание коллизий между узлами от A и B. Идентификатор также добавляется для того, чтобы узлы отличались друг от друга в случае дубликатов.

эффективность

The maximum_matching способ использования алгоритм Хопкрофта-карпа, который работает в O(n**2.5) в худшем случае. Генерация графа является O(n**2), так что весь метод работает в O(n**2.5). Он должен отлично работать с большими массивами. Решение перестановки O(n!) и не сможет обрабатывать массивы с 20 элементами.

С схемы

если вы заинтересованы в диаграмме, показывающей лучшее соответствие, вы можете смешать matplotlib и 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

вот соответствующие диаграммы:

так как вы знакомы с математикой, я просто хочу добавить блеск к другим ответам. Условия для поиска указаны в полужирный.

проблема является экземпляром перестановки с ограниченными позициями и там много, что можно сказать о них. В общем, ноль-один NxN матрица M можно построить где M[i][j] это 1 тогда и только тогда, когда позиция j допускается для элемента первоначально в позиции i. Элемент из различных перестановок, удовлетворяющих всем ограничениям, тогда постоянный на M (определяется так же, как и определитель, за исключением того, что все термины неотрицательны).

увы-в отличие от Определителя-нет известных общих способов вычислить постоянный быстрее, чем экспоненциальный в N. Однако существуют алгоритмы полиномиального времени для определения того, является ли перманент 0.

И вот где ответы вы получили start ;-) вот хороший отчет о том, как "постоянный 0?"вопрос эффективно решается путем рассмотрения совершенных соответствий в двудольных графах:

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

таким образом, на практике вряд ли вы найдете какой-либо общий подход быстрее, чем тот, который @Eric Duminil дал в своем ответе.

Примечание, добавлено позже: я должен сделать эта последняя часть яснее. Учитывая любую матрицу "ограниченной перестановки"M, легко построить целочисленные "списки делимости", соответствующие ему. Поэтому ваша конкретная проблема не легче общей проблемы - если, возможно, нет чего-то особенного, о котором целые числа могут появиться в ваших списках.

например,M и

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

просмотр строк, представляющих первые 4 простых числа, которые также являются значениями в B:

B = [2, 3, 5, 7]

первая строка тогда "говорит", что B[0] (= 2) не могу разделить A[0], но надо делить A[1],A[2] и A[3]. И так далее. По конструкции

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

соответствует M. И есть permanent(M) = 9 способы перестановки B таких, что каждый элемент A делится на соответствующий элемент перестановки B.

это не окончательный ответ, но я думаю, что это может быть что-то стоящее. Вы можете сначала перечислить факторы (1 и сам включен) всех элементов в списке [(1,2,5,10),(1,2,3,6,12),(1,2,3,6),(1,5),(1,3,7,21),(1,5,25)]. Список, который мы ищем, должен иметь один из факторов в нем (чтобы равномерно разделить). Поскольку у нас нет некоторых факторов в списке, мы проверяем их ([2,7,5,3,12,3]) этот список может быть отфильтрован как:

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

здесь, 5 необходимо два места(где у нас нет никаких вариантов на все), но у нас есть только 5, поэтому мы можем в значительной степени остановиться здесь и сказать, что случай здесь ложный.

допустим, у нас было [2,7,5,3,5,3] вместо:

тогда у нас был бы вариант как таковой:

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

так как 5 требуется в двух местах:

[(2),(2,3),(2,3),{5},(3,7),{5}] здесь {} означает обеспечить положение.

также обеспечивается 2:

[{2},(2,3),(2,3),{5},(3,7),{5}] теперь, так как 2 берется два места из 3 являются обеспечено:

[{2},{3},{3},{5},(3,7),{5}] теперь, конечно, 3 и 7 обеспечивается:

[{2},{3},{3},{5},{7},{5}]. которые по-прежнему соответствуют нашим списка, так КАС, это правда. Помните, что мы будем смотреть на последовательности с нашим списком в каждой итерации, где мы можем легко вырваться.

вы можете попробовать это:

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

выход:

True

еще пример:

l1 = [10, 12, 6, 5, 21, 25]
l2 = [2, 7, 5, 3, 12, 3]

print(potentially_divisible(l1, l2))

выход:

False