給定一個陣列 arr，我們可以重新排列它以形成另一個陣列，我們稱之為 rerranged_arr。陣列的大小定義為索引 i 的數量，0 <= i < n，其中 reraranged_arr[i] > arr[i]。即重排后放置的元素大于該索引處預設的初始值
給定初始陣列 arr，找到可以通過對陣列進行一些重新排列來實作的最大可能值
示例 arr = [1,3,5,2,1,3,1]
[1,3,5,2,1,3,1] -> 原始 arr
[ 2 , 5 ,1, 3 , 3 ,1,1] -> 最佳重排_arr
在索引 0、1、3 和 4 處以粗體顯示，rearraned_arr[i] > arr[i]。可以證明這是最大可能的偉大。因此答案是 4我的解決方案不好，出現記憶體錯誤
import itertools
def findMaximumGreatness(arr):
a = list(itertools.permutations(arr, len(arr)))
dict = {}
for i in a:
c = 0
for j in range(len(i)):
if i[j] > arr[j]:
c = 1
dict[i] = c
return max(dict.values())
這是錯誤：
a = list(itertools.permutations(arr, len(arr)))
MemoryError
我想要一些幫助來優化代碼/不同的方法
uj5u.com熱心網友回復：
這是一種記憶體效率高且速度快的東西，但它最大化了陣列元素之間的差異，結果與您的最佳陣列略有不同。不過可能會有所幫助。
arr = [1, 3, 5, 2, 1, 3, 1]
lookup = sorted(arr)
result_arr = [0] * len(arr)
greatness = 0
for i, m in sorted(enumerate(arr), key=lambda x: x[1]):
for j, n in enumerate(lookup):
if n > m and not result_arr[i]:
result_arr[i] = n
greatness = 1
del lookup[j]
break
else:
result_arr[i] = lookup[-1]
del lookup[-1]
print(result_arr, greatness)
輸出：
[2, 1, 1, 5, 3, 1, 3] 4
uj5u.com熱心網友回復：
根據您對更快執行比較的要求，我提出了以下建議：
import itertools as it
import numpy as np
t = [1,3,5,2,1,3,1]
def rearrange1(t): # initial rearrange
perm = it.permutations(t)
max = 0
rel = []
for p in perm:
tmp = [i for i, j in zip(p,t) if i>j]
if len(tmp) > max:
max = len(tmp)
rel = p
return rel
rearrange1(t)
def rearrange2(t):
t = np.array(t)
perm = np.array(list(it.permutations(t)))
k = np.argmax(np.sum(perm >t, axis = 1))
return perm[k]
rearrange2(t)
在對它們進行基準測驗后，我已經能夠以近 40% 的速度加快該程序。
基準：
Best of 7 trials with 1000 function calls per trial:
Function `rearrange1` ran in average of 0.00509 seconds.
Best of 7 trials with 1000 function calls per trial:
Function `rearrange2` ran in average of 0.00313 seconds.
但請注意，如果您有多個解決方案，比如說 4，則只會列出一個，而不是全部。
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/430966.html