根据给定分布对列表进行排序

Question

在回答一个Question时，我最终遇到了一个问题，我认为这是一种拐弯抹角的解决方法，本可以用更好的方法来解决，但我当时一无所知

有两个列表

percent = [0.23, 0.27, 0.4, 0.1]
optimal_partition = [3, 2, 2, 1]

optimal_partition，是数字8分成4部分的整数部分之一

我希望对optimal_partition进行排序，使百分比分布尽可能接近，这意味着单个分区应该与百分比大小尽可能接近

所以3 -> 0.4，2 -> 0.27，0.23和1 -> 0.1

所以最终的结果应该是

[2, 2, 3, 1]

我最终解决这个问题的方法是

>>> percent = [0.23, 0.27, 0.4, 0.1]
>>> optimal_partition = [3, 2, 2, 1]
>>> optimal_partition_percent = zip(sorted(optimal_partition),
                    sorted(enumerate(percent),
                       key = itemgetter(1)))
>>> optimal_partition = [e for e, _ in sorted(optimal_partition_percent,
                          key = lambda e: e[1][0])]
>>> optimal_partition
[2, 2, 3, 1]

你能建议一个更简单的方法来解决这个问题吗？

我的意思是更简单，不需要实现多个排序，存储和稍后基于索引的重新排列。

再举几个例子：

percent = [0.25, 0.25, 0.4, 0.1]
optimal_partition = [3, 2, 2, 1]
result = [2, 2, 3, 1]

percent = [0.2, 0.2, 0.4, 0.2]
optimal_partition = [3, 2, 2, 1]
result = [1, 2, 3, 2]

Answer 1

from numpy import take,argsort

take(opt,argsort(argsort(perc)[::-1]))

或者不使用导入：

zip(*sorted(zip(sorted(range(len(perc)), key=perc.__getitem__)[::-1],opt)))[1]

#Test

l=[([0.23, 0.27, 0.4, 0.1],[3, 2, 2, 1]),
   ([0.25, 0.25, 0.4, 0.1],[3, 2, 2, 1]),
   ([0.2,  0.2,  0.4, 0.2],[3, 2, 2, 1])]

def f1(perc,opt):
    return take(opt,argsort(argsort(perc)[::-1]))

def f2(perc,opt):
    return zip(*sorted(zip(sorted(range(len(perc)),
             key=perc.__getitem__)[::-1],opt)))[1]       

for i in l:
    perc, opt = i
    print f1(perc,opt), f2(perc,opt)

# output:
# [2 2 3 1] (2, 2, 3, 1)
# [2 2 3 1] (2, 2, 3, 1)
# [1 2 3 2] (1, 2, 3, 2)

Answer 2

使用百分比总和为1的事实：

percent = [0.23, 0.27, 0.4, 0.1]
optimal_partition = [3, 2, 2, 1]
total = sum(optimal_partition)
output = [total*i for i in percent]

现在，您需要找出一种方法，以某种方式重新分配分数部分。畅所欲言：

from operator import itemgetter
intermediate = [(i[0], int(i[1]), i[1] - int(i[1])) for i in enumerate(output)]
# Sort the list by the fractional component
s = sorted(intermediate, key=itemgetter(2))
# Now, distribute the first item's fractional component to the rest, starting at the top:
for i, tup in enumerate(s):
    fraction = tup[2]
    # Go through the remaining items in reverse order
    for index in range(len(s)-1, i, -1):
        this_fraction = s[index][2]
        if fraction + this_fraction >= 1:
            # increment this item by 1, clear the fraction, carry the remainder
            new_fraction = fraction + this_fraction -1
            s[index][1] = s[index][1] + 1
            s[index][2] = 0
            fraction = new_fraction
        else:
            #just add the fraction to this element, clear the original element
            s[index][2] = s[index][2] + fraction

现在，我不确定我会说这是“更容易”。我还没有测试过它，我确信我在最后一节中的逻辑是错误的。实际上，我正在尝试对元组赋值，所以我知道至少有一个错误。但这是一种不同的方法。