Является ли список (потенциально) делимым другим?

Проблема

Скажем, у вас есть два списка A = [a_1, a_2, ..., a_n] и B = [b_1, b_2, ..., b_n] целых чисел. Скажем, A потенциально-делимый на B, если существует перестановка B, которая делает a_i делимой на b_i для всех i. Тогда возникает проблема: можно ли переупорядочить (т.е. Переставить) B, чтобы a_i делится на b_i для всех i? Например, если у вас есть

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

Тогда ответ будет True, так как B можно переупорядочить как B = [3, 6, 4], а затем мы будем иметь a_1 / b_1 = 2, a_2 / b_2 = 2 и a_3 / b_3 = 2, все из которых являются целыми числами, поэтому A является потенциально делящимся на B.

В качестве примера, который должен выводить False, мы могли бы иметь:

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

Причина, по которой это False, заключается в том, что мы не можем изменить порядок B, так как 25 и 5 находятся в A, но единственным делителем в B будет 5, поэтому можно было бы оставить без изменений.

Подход

Очевидно, что простой подход состоял бы в том, чтобы получить все перестановки B и посмотреть, будет ли удовлетворять делимости потенциала, что-то вроде строк:

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)

Вопрос

Каков самый быстрый способ узнать, является ли список потенциально делящимся другим списком? Есть предположения? Я думал, если есть умный способ сделать это с помощью простых чисел, но я не смог найти решение.

Очень ценно!

Изменить: Это, вероятно, не имеет отношения к большинству из вас, но, ради полноты, я объясню свою мотивацию. В теории групп существует гипотеза о конечных простых группах о том, существует ли биекция из неприводимых характеров и классов сопряженности группы такая, что каждая степень характера делит соответствующий размер класса. Например, для U6 (4) вот как выглядят A и B. Довольно большие списки, заметьте!

Ответ 1

Создайте двухстороннюю структуру графа - соедините a[i] со всеми своими делителями от b[].

Затем найдите максимальное соответствие и проверьте, соответствует ли оно совершенному соответствию (количество ребер в сопоставлении равно количество пар (если граф направлен) или удвоенное число).

Произвольная выбранная реализация алгоритма Kuhn здесь.

Upd:
@Eric Duminil сделал замечательную реализацию Python здесь

Этот подход имеет полиномиальную сложность от O (n ^ 2) до O (n ^ 3) в зависимости от выбранного алгоритма соответствия и числа ребер (пар деления) от факторной сложности для алгоритма грубой силы.

Ответ 2

Код

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

Примечания

В соответствии с documentation:

Словарь, возвращаемый функцией maximum_matching(), включает отображение для вершины как в левом, так и в правом множестве вершин.

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

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

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

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

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

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

В методе 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

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

Ответ 3

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

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

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

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

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

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

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

Например, предположим, что M есть

Просмотр строк как представляющих первые 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.

Ответ 4

Это не окончательный ответ, но я думаю, что это может быть что-то достойное. Вы можете сначала перечислить факторы (1 и сам включенный) из всех элементов в списке [(1,2,5,10),(1,2,3,6,12),(1,2,3,6),(1,5),(1,3,7,21),(1,5,25)]. В списке, который мы ищем, должен быть один из факторов (равномерно распределить). Поскольку у нас нет некоторых факторов в списке, мы проверяем arre против ([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}]. который по-прежнему соответствует нашему списку, так что касса истинна. Помните, что мы будем рассматривать консистенции с нашим списком на каждой итерации, где мы можем легко вырваться.

Ответ 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