按照给定的分布对列表进行排序

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]

- Abhijit

---

定义“更容易解决这个问题的方法”。 - Woot4Moo

@Woot4Moo：基于关键字的单一排序，而不是多重排序，并像我的示例中所做的那样存储和检索索引。 - Abhijit

Answer 1

from numpy import take,argsort

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

或者不使用import:

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)

- root

---

哈哈，比我的方法简单多了。 - Brenden Brown

看起来很有趣。在回复之前，我需要先进行一些实验。 - Abhijit

不幸的是，在zip和numpy的情况下，第三个例子似乎有点偏离轨道。 3 实际上应该与最高的pct分布相对应，即 0.4。我认为你的numpy解决方案很优雅，非常接近，但我们都忽略了一些明显的东西。在寻找其他解决方案之前，我会稍微调整一下你的numpy解决方案。 - Abhijit

@Abhijit：我最初误解了目标，现在已经更正了我的回答。 - root

现在已经非常完美了。非常感谢您的努力 :-) - Abhijit

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

现在，我不确定我能说这个方法更“简单”。我没有测试过它，而且我确定在上一段逻辑上出错了。事实上，我正在尝试给元组赋值，所以我知道至少有一个错误。但这是一个不同的方法。

- Brenden Brown