Une liste est-elle (potentiellement) divisible par une autre ?

Question

Problème

Supposons que vous ayez deux listes A = [a_1, a_2, ..., a_n] y B = [b_1, b_2, ..., b_n] de nombres entiers. Nous disons A es potentiellement divisible por B s'il existe une permutation de B qui rend a_i divisible par b_i pour tous i . Le problème est alors le suivant : est-il possible de réorganiser (c'est-à-dire de permuter) B de sorte que a_i est divisible par b_i pour tous i ? Par exemple, si vous avez

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

La réponse serait alors True , comme B peuvent être réordonnées pour être B = [3, 6, 4] et nous aurions alors cette a_1 / b_1 = 2 , a_2 / b_2 = 2 y a_3 / b_3 = 2 qui sont tous des entiers, donc A est potentiellement divisible par B .

A titre d'exemple, qui devrait produire False Nous aurions pu le faire :

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

La raison en est la suivante False est que nous ne pouvons pas réorganiser B comme 25 et 5 sont dans A mais le seul diviseur dans B serait de 5, il en resterait donc un.

Approche

Il est évident que l'approche la plus simple consisterait à obtenir toutes les permutations de B et voir si l'une d'entre elles satisferait potentiel-divisibilité , quelque chose du genre :

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)

Question

Quel est le moyen le plus rapide de savoir si une liste est potentiellement divisible par une autre liste ? Des idées ? Je me demandais s'il n'y avait pas un moyen astucieux de le faire avec premiers mais je n'ai pas trouvé de solution.

C'est très apprécié !

---

Editar : C'est probablement sans intérêt pour la plupart d'entre vous, mais par souci d'exhaustivité, je vais expliquer ma motivation. En théorie des groupes, il existe une conjecture sur les groupes simples finis qui consiste à savoir s'il existe ou non une bijection entre les caractères irréductibles et les classes de conjugaison du groupe telle que chaque degré de caractère divise la taille de la classe correspondante. Par exemple, pour U6(4) Voici ce que A y B ressemblerait à ce qui suit. Des listes assez conséquentes, d'ailleurs !

Answer 1

Construire une structure de graphe bipartite - connecter a[i] avec tous ses diviseurs de b[] .

Trouvez ensuite correspondance maximale et vérifier s'il est correspondance parfaite (le nombre d'arêtes dans l'appariement est égal au nombre de paires (si le graphe est orienté) ou au nombre doublé).

Arbitraire choisi Mise en œuvre de l'algorithme de Kuhn ici .

Mise à jour :
@Eric Duminil a fait une grande concision Implémentation Python ici

Cette approche présente une complexité polynomiale de O(n^2) à O(n^3) en fonction de l'algorithme d'appariement choisi et du nombre d'arêtes (paires de divisions) par rapport à la complexité factorielle de l'algorithme de force brute.

Answer 2

Código

En s'appuyant sur l'excellent travail de @MBo répondre Voici une implémentation de l'appariement de graphes bipartites à l'aide de 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

Notes

Selon la la documentation :

Le dictionnaire retourné par maximum_matching() inc dans les ensembles de sommets de gauche et de droite.

Cela signifie que le dict renvoyé doit être deux fois plus grand que A y B .

Les nœuds sont convertis de

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

à :

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

afin d'éviter les collisions entre les nœuds de A y B . L'identifiant est également ajouté afin de distinguer les nœuds en cas de doublons.

Efficacité

En maximum_matching La méthode utilise Algorithme de Hopcroft-Karp qui fonctionne en O(n**2.5) dans le pire des cas. La génération du graphe est O(n**2) , de sorte que toute la méthode s'exécute en O(n**2.5) . Elle devrait fonctionner correctement avec des tableaux de grande taille. La solution de permutation est O(n!) et ne sera pas en mesure de traiter des tableaux de 20 éléments.

Avec des diagrammes

Si vous souhaitez obtenir un diagramme montrant les meilleures correspondances, vous pouvez combiner matplotlib et 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

Voici les diagrammes correspondants :

Answer 3

Puisque vous êtes à l'aise avec les mathématiques, je voudrais juste ajouter une précision aux autres réponses. Les termes à rechercher sont indiqués dans audacieux .

Le problème est une instance de permutations avec positions restreintes et il y a beaucoup de choses à dire à ce sujet. En général, un zéro-un NxN matrice M peut être construit dans le cas où M[i][j] est 1 si et seulement si la position j est autorisé pour l'élément situé à l'origine à la position i . Les nombre de permutations distinctes répondant à toutes les restrictions est alors la permanent de M (défini de la même manière que le déterminant, sauf que tous les termes sont non négatifs).

Hélas, contrairement à ce qui se passe pour le déterminant, il n'existe pas de méthode générale connue pour calculer l'exponentielle permanente plus rapide que l'exponentielle en N . Cependant, il existe des algorithmes en temps polynomial pour déterminer si la permanente est 0 ou non.

Et c'est là que les réponses que vous avez obtenues commencer ;-) Voici un bon compte-rendu de la manière dont on répond efficacement à la question "le 0 est-il permanent ?" en considérant les correspondances parfaites dans les graphes bipartis :

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

En pratique, il est donc peu probable que vous trouviez une approche générale plus rapide que celle proposée par @Eric Duminil dans sa réponse.

Note, ajoutée ultérieurement : Je devrais rendre cette dernière partie plus claire. Étant donné une matrice de "permutation restreinte" quelconque M il est facile de construire des "listes de divisibilité" en nombres entiers qui lui correspondent. Par conséquent, votre problème spécifique n'est pas plus facile que le problème général - à moins qu'il n'y ait quelque chose de spécial à propos des entiers qui peuvent apparaître dans vos listes.

Supposons par exemple que M es

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

Les lignes représentent les 4 premiers nombres premiers, qui sont également les valeurs de B :

B = [2, 3, 5, 7]

La première ligne "dit" alors que B[0] (= 2) ne peut pas diviser A[0] mais doit diviser A[1] , A[2] y A[3] . Et ainsi de suite. Par construction,

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

correspond à M . Et il y a permanent(M) = 9 façons de permuter B tel que chaque élément de A est divisible par l'élément correspondant de l'ensemble permuté de B .

Answer 4

Ce n'est pas la réponse ultime, mais je pense que cela peut être utile. Vous pouvez d'abord énumérer les facteurs (1 et lui-même inclus) de tous les éléments de la liste [(1,2,5,10),(1,2,3,6,12),(1,2,3,6),(1,5),(1,3,7,21),(1,5,25)] . La liste que nous cherchons doit contenir l'un des facteurs (pour diviser uniformément). Puisque nous n'avons pas certains facteurs dans la liste que nous vérifions( [2,7,5,3,12,3] ) Cette liste peut être filtrée comme suit :

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

Ici, le 5 est nécessaire à deux endroits (où nous n'avons aucune option), mais nous n'avons qu'un 5, donc nous pouvons nous arrêter là et dire que le cas est faux ici.

Supposons que nous ayons [2,7,5,3,5,3] au lieu de cela :

Nous aurions alors une option en tant que telle :

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

Puisque 5 est nécessaire à deux endroits :

[(2),(2,3),(2,3),{5},(3,7),{5}] Où {} signifie que la position est assurée.

Le point 2 est également assuré :

[{2},(2,3),(2,3),{5},(3,7),{5}] Maintenant que le 2 est pris, les deux places du 3 sont assurées :

[{2},{3},{3},{5},(3,7),{5}] Bien entendu, 3 sont prises et 7 sont assurées :

[{2},{3},{3},{5},{7},{5}] . ce qui est toujours cohérent avec notre liste, donc le cas est vrai. N'oubliez pas que nous examinerons la cohérence avec notre liste à chaque itération où nous pouvons facilement nous en détacher.

Answer 5

Vous pouvez essayer ceci :

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

Sortie :

True

Autre exemple :

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

print(potentially_divisible(l1, l2))

Sortie :

False