# Is a list (potentially) divisible by another?

# 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!

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.

From: stackoverflow.com/q/45906747

**★ Back to homepage or read more recommendations:**