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