There are two arrays of length n ( a and b ) consisting of integers> 2.
At each turn, I want to remove an integer from each array ( a[i] and b[j] ), given that a certain condition about them is true (for example, that they are not compatible). (If the condition is wrong, I will try to remove another combination)
In the end, I want to find the maximum number of turns, I can achieve this (until there is a possible combination for deletion that matches the condition). Let me call this the optimal number of turns.
I tried to solve this using a search algorithm and PriorityQueue using Python:
def search(n, a, b): q = queue.PriorityQueue() encountered = set() encountered.add((tuple(a), tuple(b))) q.put((number_of_coprime_combinations(a, b), a, b)) while q: cost, a, b = q.get() combs = not_coprime_combinations(a, b) if not combs: return n - len(a) for a, b in combs: if not (tuple(a), tuple(b)) in encountered: q.put((number_of_coprime_combinations(a, b), a, b)) encountered.add((tuple(a), tuple(b)))
number_of_coprime_combinations(a, b) returns the number of possible co-prime combinations given by arrays a and b . This is used as the cost of a given state of two arrays.
def number_of_coprime_combinations(a, b): n = 0 for idx_a, x in enumerate(a): for idx_b, y in enumerate(b): if is_coprime(x, y): n += 1 return n
not_coprime_combinations(a, b) returns a list of possible states where the combination of incompatibilities has been removed from a and b :
def not_coprime_combinations(a, b): l = [] for idx_a, x in enumerate(a): for idx_b, y in enumerate(b): if not is_coprime(x, y): u, v = a[:], b[:] del(u[idx_a]) del(v[idx_b]) l.append((u, v)) return l >>> not_coprime_combinations([2,3],[5,6]) [([3], [5]), ([2], [5])]
The problem is that this solution is extremely inefficient for large arrays of large integers. Therefore, I am wondering if there is a better solution to this problem.
Example:
n = 4 a = [2, 5, 6, 7] b = [4, 9, 10, 12]
Can be deleted:
(2, 4) (5, 10) (6, 9)
This will lead to an optimal solution:
a = [7] b = [12]
But if you delete:
(6, 12) (2, 10)
could go to a non-optimal solution:
a = [5, 7] b = [4, 9]
The algorithm should always find the optimal number of revolutions (in this example 3).