重新排列数组 A,以便在进行一对一比较时,A 赢得与数组 B 的最大比较次数
Rearrange an array A so that A wins maximum number of comparisons with array B when comparison is done one-on-one
假设我有一个数组 A = [3, 6, 7, 5, 3, 5, 6, 2, 9, 1]
和 B = [2, 7, 0, 9, 3, 6, 0, 6, 2, 6]
重新排列数组 A 的元素,这样当我们按元素比较 3 与 2 和 6 与 7 等等时,我们有最大的胜利(A[i] > B[i]
最大的组合 (0<=i<len(A))
).
我尝试了以下方法:
def optimal_reorder(A,B,N):
tagged_A = [('d',i) for i in A]
tagged_B = [('a',i) for i in B]
merged = tagged_A + tagged_B
merged = sorted(merged,key=lambda x: x[1])
max_wins = 0
for i in range(len(merged)-1):
print (i)
if set((merged[i][0],merged[i+1][0])) == {'a','d'}:
if (merged[i][0] == 'a') and (merged[i+1][0] == 'd'):
if (merged[i][1] < merged[i+1][1]):
print (merged[i][1],merged[i+1][1])
max_wins += 1
return max_wins
引用自
但是这种方法似乎没有给出给定 A 和 B 的正确答案,即如果 A = [3, 6, 7, 5, 3, 5, 6, 2, 9, 1]
和 B = [2, 7, 0, 9, 3, 6, 0, 6, 2, 6]
那么最大获胜数是 7,但我的算法给出了 5.
这里有什么我遗漏的吗?
按照@chqrlie
的建议修改了解决方案
def optimal_reorder2(A,B):
arrA = A.copy()
C = [None] * len(B)
for i in range(len(B)):
k = i + 1
all_ele = []
while (k < len(arrA)):
if arrA[k] > B[i]:
all_ele.append(arrA[k])
k += 1
if all_ele:
e = min(all_ele)
else:
e = min(arrA)
C[i] = e
arrA.remove(e)
return C
这个算法怎么样:
- 从空数组开始
C
。
- 对于
range(len(B))
中的每个索引 i
。
- 如果
A
的剩余元素至少有一个大于B[i]
,则选择e
作为这些元素中最小的,否则选择e
作为A
. 的最小元素
- 设置
C[i] = e
并从 A
中删除 e
。
C
应该是 A
的重新排序,以最大化真实比较的数量 C[i] > B[i]
.
可能有比这更好的算法,但您可以将其视为最大二分匹配问题。将数组视为二分图中的两组节点,然后如果 A[i] > B[j],则添加一条从 A[i] 到 B[j] 的边。然后,任何匹配都会告诉您如何将 A 的元素与 B 的元素配对,以便 A 元素“胜过”B 元素,而最大匹配会告诉您如何执行此操作以最大化获胜次数。
我相信有更好的方法可以做到这一点,我很高兴看到其他人想出了什么办法。但这至少表明你可以在多项式时间内解决这个问题。
假设我有一个数组 A = [3, 6, 7, 5, 3, 5, 6, 2, 9, 1]
和 B = [2, 7, 0, 9, 3, 6, 0, 6, 2, 6]
重新排列数组 A 的元素,这样当我们按元素比较 3 与 2 和 6 与 7 等等时,我们有最大的胜利(A[i] > B[i]
最大的组合 (0<=i<len(A))
).
我尝试了以下方法:
def optimal_reorder(A,B,N):
tagged_A = [('d',i) for i in A]
tagged_B = [('a',i) for i in B]
merged = tagged_A + tagged_B
merged = sorted(merged,key=lambda x: x[1])
max_wins = 0
for i in range(len(merged)-1):
print (i)
if set((merged[i][0],merged[i+1][0])) == {'a','d'}:
if (merged[i][0] == 'a') and (merged[i+1][0] == 'd'):
if (merged[i][1] < merged[i+1][1]):
print (merged[i][1],merged[i+1][1])
max_wins += 1
return max_wins
引用自
A = [3, 6, 7, 5, 3, 5, 6, 2, 9, 1]
和 B = [2, 7, 0, 9, 3, 6, 0, 6, 2, 6]
那么最大获胜数是 7,但我的算法给出了 5.
这里有什么我遗漏的吗?
按照@chqrlie
的建议修改了解决方案def optimal_reorder2(A,B):
arrA = A.copy()
C = [None] * len(B)
for i in range(len(B)):
k = i + 1
all_ele = []
while (k < len(arrA)):
if arrA[k] > B[i]:
all_ele.append(arrA[k])
k += 1
if all_ele:
e = min(all_ele)
else:
e = min(arrA)
C[i] = e
arrA.remove(e)
return C
这个算法怎么样:
- 从空数组开始
C
。 - 对于
range(len(B))
中的每个索引i
。- 如果
A
的剩余元素至少有一个大于B[i]
,则选择e
作为这些元素中最小的,否则选择e
作为A
. 的最小元素
- 设置
C[i] = e
并从A
中删除e
。
- 如果
C
应该是 A
的重新排序,以最大化真实比较的数量 C[i] > B[i]
.
可能有比这更好的算法,但您可以将其视为最大二分匹配问题。将数组视为二分图中的两组节点,然后如果 A[i] > B[j],则添加一条从 A[i] 到 B[j] 的边。然后,任何匹配都会告诉您如何将 A 的元素与 B 的元素配对,以便 A 元素“胜过”B 元素,而最大匹配会告诉您如何执行此操作以最大化获胜次数。
我相信有更好的方法可以做到这一点,我很高兴看到其他人想出了什么办法。但这至少表明你可以在多项式时间内解决这个问题。