# Is a list (potentially) divisible by another?

PythonAlgorithmNumbersPrimesDivision## Python Problem Overview

### Problem

Say you have two lists `A = [a_1, a_2, ..., a_n]`

and `B = [b_1, b_2, ..., b_n]`

of integers. We say `A`

is **potentially-divisible** by `B`

if there is a permutation of `B`

that makes `a_i`

divisible by `b_i`

for all `i`

. The problem is then: is it possible to reorder (i.e. permute) `B`

so that `a_i`

is divisible by `b_i`

for all `i`

?
For example, if you have

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

Then the answer would be `True`

, as `B`

can be reordered to be `B = [3, 6, 4]`

and then we would have that `a_1 / b_1 = 2 `

, `a_2 / b_2 = 2 `

, and `a_3 / b_3 = 2 `

, all of which are integers, so `A`

is potentially-divisible by `B`

.

As an example which should output `False`

, we could have:

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

The reason this is `False`

is that we can't reorder `B`

as 25 and 5 are in `A`

, but the only divisor in `B`

would be 5, so one would be left out.

### Approach

Obviously the straightforward approach would be to get all the permutations of `B`

and see if one would satisfy **potential-divisibility**, something along the lines of:

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

What is the fastest way to know if a list is potentially-divisible by another list? Any thoughts? I was thinking if there's is a clever way to do this with **primes**, but I couldn't come up with a solution.

Much appreciated!

*Edit*: It's probably irrelevant to most of you, but for the sake of completeness, I'll explain my motivation. In Group Theory there is a conjecture on finite simple groups on whether or not there is a bijection from irreducible characters and conjugacy classes of the group such that every character degree divides the corresponding class size. For example, for *U6(4)* here are what `A`

and `B`

would look like. Pretty big lists, mind you!

## Python Solutions

## Solution 1 - Python

Build bipartite graph structure - connect `a[i]`

with all its divisors from `b[]`

.

Then find maximum matching and check whether it is **perfect matching** (number of edges in matching is equal to the number of pairs (if graph is directed) or to doubled number).

Arbitrary chosen Kuhn algorithm implementation here.

Upd:

@Eric Duminil made great concise Python implementation here

This approach has polynomial complexity from O(n^2) to O(n^3) depending on chosen matching algorithm and number of edges (division pairs) against factorial complexity for brute-force algorithm.

## Solution 2 - Python

### Code

Building on @MBo's excellent answer, here's an implementation of bipartite graph matching using 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

According to the documentation:

> The dictionary returned by maximum_matching() includes a mapping for > vertices in both the left and right vertex sets.

It means that the returned dict should be twice as large as `A`

and `B`

.

The nodes are converted from

```
[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)]
```

in order to avoid collisions between nodes from `A`

and `B`

. The id is also added in order to keep nodes distinct in case of duplicates.

### Efficiency

The `maximum_matching`

method uses Hopcroft-Karp algorithm, which runs in `O(n**2.5)`

in the worst case. The graph generation is `O(n**2)`

, so the whole method runs in `O(n**2.5)`

. It should work fine with large arrays. The permutation solution is `O(n!)`

and won't be able to process arrays with 20 elements.

### With diagrams

If you're interested in a diagram showing the best matching, you can mix matplotlib and 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
```

Here are the corresponding diagrams:

## Solution 3 - Python

Since you're comfortable with math, I just want to add a gloss to the other answers. Terms to search for are shown in **bold**.

The problem is an instance of **permutations with restricted positions**, and there's a whole lot that can be said about those. In general, a zero-one `NxN`

matrix `M`

can be constructed where `M[i][j]`

is 1 if and only if position `j`

is allowed for the element originally at position `i`

. The *number* of distinct permutations meeting all the restrictions is then the **permanent** of `M`

(defined the same way as the determinant, except that all terms are non-negative).

Alas - unlike as for the determinant - there are no known general ways to compute the permanent quicker than exponential in `N`

. However, there are polynomial time algorithms for determining whether or not the permanent is 0.

And that's where the answers you got *start* ;-) Here's a good account of how the "is the permanent 0?" question is answered efficiently by considering perfect matchings in bipartite graphs:

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

So, in practice, it's unlikely you'll find any general approach faster than the one @Eric Duminil gave in their answer.

Note, added later: I should make that last part clearer. Given any "restricted permutation" matrix `M`

, it's easy to construct integer "divisibilty lists" corresponding to it. Therefore your specific problem is no easier than the general problem - unless perhaps there's something special about which integers may appear in your lists.

For example, suppose `M`

is

```
0 1 1 1
1 0 1 1
1 1 0 1
1 1 1 0
```

View the rows as representing the first 4 primes, which are also the values in `B`

:

```
B = [2, 3, 5, 7]
```

The first row then "says" that `B[0] (= 2)`

can't divide `A[0]`

, but must divide `A[1]`

, `A[2]`

, and `A[3]`

. And so on. By construction,

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

corresponds to `M`

. And there are `permanent(M) = 9`

ways to permute `B`

such that each element of `A`

is divisible by the corresponding element of the permuted `B`

.

## Solution 4 - Python

This is not the ultimate answer but I think this might be something worthful. You can first list the factors(1 and itself included) of all the elements in the list `[(1,2,5,10),(1,2,3,6,12),(1,2,3,6),(1,5),(1,3,7,21),(1,5,25)]`

. The list we are looking for must have one of the factors in it(to evenly divide).
Since we don't have some factors in the list we arre checking against(`[2,7,5,3,12,3]`

) This list can further be filtered as:

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

Here, 5 is needed two places(where we don't have any options at all), but we only have a 5, so, we can pretty much stop here and say that the case is false here.

Let's say we had `[2,7,5,3,5,3]`

instead:

Then we would have option as such:

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

Since 5 is needed at two places:

`[(2),(2,3),(2,3),{5},(3,7),{5}]`

Where `{}`

signifies ensured position.

Also 2 is ensured:

`[{2},(2,3),(2,3),{5},(3,7),{5}]`

Now since 2 is taken the two places of 3 are ensured:

`[{2},{3},{3},{5},(3,7),{5}]`

Now of course 3 are taken and 7 is ensured:

`[{2},{3},{3},{5},{7},{5}]`

. which is still consistent with our list so the casse is true. Remember we shall be looking at the consistencies with our list in every iteration where we can readily break out.

## Solution 5 - Python

You can try this:

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

Output:

```
True
```

Another example:

```
l1 = [10, 12, 6, 5, 21, 25]
l2 = [2, 7, 5, 3, 12, 3]
print(potentially_divisible(l1, l2))
```

Output:

```
False
```