67 votes

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

Problème

Disons que vous avez deux listes A = [a_1, a_2, ..., a_n] et B = [b_1, b_2, ..., b_n] d'entiers. Nous disons A est potentiellement divisible par B s'il existe une permutation de l' B qui fait a_i divisible par b_i tous i. Le problème est alors: est-il possible de les réorganiser (c'est à dire permuter) B afin a_i est divisible par b_i tous i? Par exemple, si vous avez

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

Alors, la réponse serait" True, comme B peuvent être réorganisés pour être B = [3, 6, 4] et nous aurions alors que a_1 / b_1 = 2, a_2 / b_2 = 2, et a_3 / b_3 = 2, qui sont tous des entiers, A est potentiellement divisible par B.

Comme un exemple qui devrait sortie False, on pourrait avoir:

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

La raison de ce qui est False , c'est que nous ne pouvons pas réorganiser B , de 25 et 5 sont en A, mais le seul diviseur en B serait de 5, donc on peut être laissé de côté.

Approche

Évidemment, l'approche simple serait d'obtenir toutes les permutations de l' B et voir si l'un serait à même de satisfaire le potentiel de la divisibilité, quelque chose le long des lignes 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)

Question

Quel est le moyen le plus rapide pour savoir si une liste est potentiellement divisible par une autre liste? Toutes les pensées? Je pensais que si il y a une manière habile de faire cela avec les nombres premiers, mais je ne pouvais pas venir avec une solution.

Beaucoup apprécié!


Edit: Ce n'est probablement pas pertinente pour la plupart d'entre vous, mais par souci d'exhaustivité, je vais vous expliquer ma motivation. Dans la Théorie des groupes, il est une conjecture sur les groupes simples finis sur si oui ou non il existe une bijection de caractères irréductibles et conjugacy classes du groupe, de telle sorte que chaque personnage degré divise la classe correspondante de la taille. Par exemple, pour les U6(4) voici ce que l' A et B ressemblerait. Assez grand des listes, vous l'esprit!

69voto

MBo Points 11630

Construire graphe biparti structure - se connecter a[i] avec tous ses diviseurs de b[]. enter image description here

Ensuite, trouver le maximum de correspondance et de vérifier si elle est parfaite correspondance (nombre d'arêtes dans l'appariement est égal au nombre de paires (si le graphe est orienté) ou à doublé le nombre).

Arbitraire choisi Kuhn algorithme de mise en œuvre ici.

Upd:
@Eric Duminil fait de grands concis Python de mise en œuvre ici

Cette approche a polynôme complexité de O(n^2) à O(n^3) selon le correspondant à l'algorithme et le nombre d'arêtes (division paires) contre factorielle de la complexité de la force brute de l'algorithme.

30voto

Eric Duminil Points 38857

Code

Bâtiment sur @MBo est une excellente réponse, voici une implémentation de graphe biparti correspondant à 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 documentation:

Le dictionnaire retourné par maximum_matching() comprend une cartographie pour de sommets en deux gauche et à droite de vertex ensembles.

Cela signifie que le retour de l'dict devrait être deux fois plus grand que A et B.

Les nœuds sont convertis à partir de

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

pour:

[('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 d' A et B. L'id est également ajoutée afin de garder les nœuds distincts en cas de doublon.

L'efficacité

L' maximum_matching méthode utilise Hopcroft-Karp algorithmequi s'exécute en O(n**2.5) dans le pire des cas. Le graphique de génération est - O(n**2), donc l'ensemble de la méthode s'exécute en O(n**2.5). Il devrait fonctionner correctement avec de grands tableaux. La permutation de la solution est - O(n!) et ne sera pas en mesure de traiter les tableaux avec 20 éléments.

Avec des diagrammes

Si vous êtes intéressé par un diagramme montrant la meilleure correspondance, vous pouvez mélanger 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 correspondant:

enter image description here enter image description here enter image description here

17voto

Tim Peters Points 16225

Puisque vous êtes à l'aise avec les mathématiques, je veux juste ajouter un éclat à l'autre des réponses. Termes de recherche sont affichés en caractères gras.

Le problème, c'est une instance de permutations dont les positions, et il y a beaucoup de choses qui peut être dit à propos de ces. En général, un zéro-un, NxN de la matrice M peut être construit où les M[i][j] est 1 si et seulement si la position j est autorisé pour l'élément à l'origine à la position i. Le nombre de permutations distinctes réunion de toutes les restrictions à l'est puis la permanente de M (défini de la même manière que le déterminant, sauf que tous les termes sont non-négatives).

Hélas, à la différence que pour le déterminant - il n'y a pas connue général manières de calculer l'permanent plus rapide que l'exponentielle en N. Cependant, il existe des algorithmes polynomiaux en temps pour déterminer si le permanent est de 0.

Et c'est là que les réponses que vous avez commencer ;-) Voici un bon compte de la façon dont la "a, en permanence, 0?" la question est répondu de manière efficace en considérant parfait couplages dans les graphes bipartites:

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

Donc, dans la pratique, il est peu probable que vous trouverez toute approche générale plus rapide que l' @Eric Duminil a donné dans leur réponse.

Remarque, a ajouté plus tard: je doit faire cette dernière partie plus claire. Compte tenu de tout "restreint permutation" matrice M, il est facile de construire integer "la divisibilité des listes de" correspondant. Par conséquent, votre problème n'est pas plus facile que le problème général - sauf peut-être il y a quelque chose de spécial à propos de laquelle les entiers peuvent apparaître dans vos listes.

Par exemple, supposons M est

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

Afficher les lignes comme représentant les 4 premiers nombres premiers, qui sont aussi les valeurs en B:

B = [2, 3, 5, 7]

La première ligne, puis "dit" qu' B[0] (= 2) peut pas diviser A[0], mais il doit diviser A[1], A[2], et 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 à l' M. Et il y a permanent(M) = 9 façons de permuter B , de sorte que chaque élément de l' A est divisible par l'élément correspondant de la permutées B.

3voto

officialaimm Points 373

Ce n'est pas la réponse ultime, mais je pense que cela pourrait être quelque chose worthful. Vous pouvez tout d'abord la liste des 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 recherchons doit avoir l'un des facteurs(à répartir uniformément). Puisque nous n'avons pas de certains facteurs dans la liste que nous arre de la vérification([2,7,5,3,12,3]) Cette liste peut être filtrée comme:

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

Ici, 5 deux endroits(où nous n'avons pas d'options), mais nous n'avons que 5, donc, nous pouvons très bien s'arrêter là et dire que l'affaire est faux ici.

Disons que nous avons eu [2,7,5,3,5,3] à la place:

Nous aurions alors l'option en tant que tel:

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

Depuis le 5 est nécessaire à deux endroits:

[(2),(2,3),(2,3),{5},(3,7),{5}]{} signifie veillé à ce poste.

Aussi 2 est assurée:

[{2},(2,3),(2,3),{5},(3,7),{5}] Depuis maintenant 2 est pris les deux places de 3 sont assurées:

[{2},{3},{3},{5},(3,7),{5}] Maintenant, bien sûr, 3 sont prises et 7 est assurée:

[{2},{3},{3},{5},{7},{5}]. ce qui est encore compatible avec notre liste de sorte que la casse est vrai. N'oubliez pas que nous doit être à la recherche à la cohérence avec notre liste à chaque itération où l'on peut facilement sortir.

2voto

Ajax1234 Points 42210

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
 

Un autre exemple:

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

print(potentially_divisible(l1, l2))
 

Sortie:

 False
 

Prograide.com

Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.

Powered by: