목록은 (잠재적으로) 다른 것으로 나눌 수 있습니까?

목록은 (잠재적으로) 다른 것으로 나눌 수 있습니까?

---

문제

두 개의 목록 A = [a_1, a_2, ..., a_n]과 B = [b_1, b_2, ..., b_n]정수 가 있다고 가정합니다 . 우리는 말씀 A입니다 잠재적으로 나눌 가 B있는 경우의 순열 B그 수 a_i로 나누어 b_i모두를 위해 i. 그렇다면 문제는 다음과 같습니다. 모두 를 위해 나눌 수 B있도록 재정렬 (즉, 영구) a_i이 가능 합니까? 예를 들어,b_ii

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

그런 대답이 될 것 True같은 B일을 다시 정렬 할 수 있습니다 B = [3, 6, 4]그리고 우리가있을 것입니다 a_1 / b_1 = 2, a_2 / b_2 = 2그리고 a_3 / b_3 = 2정수 모두, 그래서, A에 의해 잠재적으로 나눌 수있다 B.

출력해야하는 예로서 다음과 같이 False할 수 있습니다.

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

그 이유는 25와 5가에 있으므로 False재정렬 할 수 없지만 유일한 제수는 5이므로 하나는 생략됩니다.BAB

접근하다

분명히 간단한 접근 방식은 모든 순열을 얻고 잠재적 분할 가능성B 을 충족하는지 확인하는 것 입니다.

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)

질문

목록이 잠재적으로 다른 목록으로 나눌 수 있는지 확인하는 가장 빠른 방법은 무엇입니까? 이견있는 사람? 소수로 이것을 수행하는 영리한 방법이 있다고 생각 했지만 해결책을 찾지 못했습니다.

매우 감사!

---

편집 : 아마도 대부분의 사람들과 관련이 없지만 완전성을 위해 제 동기를 설명하겠습니다. 그룹 이론에서는 모든 문자 정도가 해당 클래스 크기를 나누도록 그룹의 축소 할 수없는 문자와 켤레 클래스에서 이분법이 있는지 여부에 대한 유한 단순 그룹에 대한 추측이 있습니다. 예를 들어, 대한 U6 (4) 여기에서 무엇 A과 B같을 것이다. 꽤 큰 목록입니다.

---

이분 그래프 구조를 구축 - 연결 a[i]에서 모든 약수와 b[].

그런 다음 최대 일치를 찾아 완벽하게 일치 하는지 확인합니다 ( 일치하는 모서리 수가 쌍의 수와 같거나 (그래프가 지시 된 경우) 또는 두 배의 숫자).

여기에서 임의의 Kuhn 알고리즘 구현을 선택 했습니다 .

Upd :
@Eric Duminil이 여기에서 간결한 Python 구현을 만들었습니다.

이 접근 방식은 무차별 대입 알고리즘에 대한 요인 복잡도에 대한 선택한 일치 알고리즘 및 에지 수 (나누기 쌍)에 따라 O (n ^ 2)에서 O (n ^ 3)까지의 다항식 복잡도를 갖습니다.

---

암호

@MBo의 탁월한 답변을 바탕으로 여기에 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

메모

문서 에 따르면 :

maximum_matching ()에 의해 반환 된 사전에는 왼쪽 및 오른쪽 정점 세트 모두의 정점에 대한 매핑이 포함됩니다.

이는 반환 된 dict가 Aand 보다 두 배 커야 함을 의미합니다 B.

노드는 다음에서 변환됩니다.

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

에:

[('A', 10, 0), ('A', 12, 1), ('A', 6, 2), ('A', 5, 3), ('A', 21, 4), ('A', 25, 5)]

A및의 노드 간의 충돌을 방지하기 위해 B. 중복되는 경우 노드를 구별하기 위해 ID도 추가됩니다.

능률

이 maximum_matching방법은 최악의 경우에 실행되는 Hopcroft-Karp 알고리즘을 사용합니다 O(n**2.5). 그래프 생성은 O(n**2)이므로 전체 방법은 O(n**2.5). 큰 배열에서 잘 작동합니다. 순열 솔루션은 O(n!)20 개의 요소가있는 배열을 처리 할 수 ​​없으며 처리 할 수 ​​없습니다.

다이어그램으로

최상의 매칭을 보여주는 다이어그램에 관심이 있다면 matplotlib와 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

다음은 해당 다이어그램입니다.

---

당신은 수학에 익숙하기 때문에 다른 답변에 광택을 더하고 싶습니다. 검색 할 용어는 굵게 표시 됩니다.

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.

---

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}]. 그것은 여전히 ​​우리 목록과 일치하므로 casse가 사실입니다. 우리가 쉽게 탈피 할 수있는 모든 반복에서 목록과 함께 일관성을 살펴볼 것임을 기억하십시오.

---

이것을 시도 할 수 있습니다.

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

산출:

True

또 다른 예:

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

print(potentially_divisible(l1, l2))

산출:

False

참고 URL : https://stackoverflow.com/questions/45906747/is-a-list-potentially-divisible-by-another