如何排列/排序数组的元素以使其匹配特定模式？

Question

问题设置

我正在使用以下代码生成一个数组，该数组包含具有给定长度且其元素的总和等于某个给定值的数组（请注意，允许重复数字）：-

from itertools import product
  
def find_combinations(sum_value, len_value):
    lst = range(sum_value + 1)

    return [
        pair 
        for pair in product(lst, repeat=len_value) 
        if sum(pair) == sum_value
    ]

# ----------------------------------------- #

sum_value = # some value
len_value = # some value

print(find_combinations(sum_value, len_value))

例如，

如果总和 sum_value 为 4，长度 len_value 为 2，此代码生成的输出为：-

[
    (0, 4),
    (1, 3),
    (2, 2),
    (3, 1),
    (4, 0),
]

实际问题

此代码运行完美 - 它包含我所期望的所有组合。 但是这里的问题是数组的顺序不正确.

即

在前面的示例中，所需的 sum 是 4，length 是 2，输出应该是这样的：-

[
    (4, 0),
    (0, 4),
    (3, 1),
    (1, 3),
    (2, 2),
]

因此，如果所需的 sum 是 4，并且 length 是 3，则此代码产生的输出是：-

[
    (0, 0, 4),
    (0, 1, 3),
    (0, 2, 2),
    (0, 3, 1),
    (0, 4, 0),
    (1, 0, 3),
    (1, 1, 2),
    (1, 2, 1),
    (1, 3, 0),
    (2, 0, 2),
    (2, 1, 1),
    (2, 2, 0),
    (3, 0, 1),
    (3, 1, 0),
    (4, 0, 0),
]

但是预期输出的顺序是：-

[
    (4, 0, 0),
    (0, 4, 0),
    (0, 0, 4),
    (3, 1, 0),
    (0, 3, 1),
    (1, 0, 3),
    (1, 3, 0),
    (0, 1, 3),
    (3, 0, 1),
    (2, 1, 1),
    ...,
]

所以我的问题是，我怎样才能排列这个数组的元素以匹配这个模式？

P.S。 - 你可以参考，这篇文章的灵感来自于

Answer 1

您可以通过递减 variance（与元素平均值的偏差）对数组进行排序：

sorted(all_combinations, key=lambda combi: -np.var(combi))

"numpy.var" 计算每个元素的方差。由于方差是标准差的平方，因此 (4, 0, 0) 中的 4 之类的巨大异常值会产生巨大的方差。 "-" 降序排列。

如果您需要特定顺序的相同数字组合（例如 (4, 0, 0) 和 (0, 4, 0)，它们会产生相同的方差），您可以通过添加应该首先排序的元素的小数字：

sorted(all_combinations, key=lambda combi: -np.var(np.array(combi) + np.linspace(0.01, 0, num=len(all_combinations[0]))))

Answer 2

试试这个想法：

从最大的可能值开始（得到 (sum_len, 0, ..., 0) 作为第一个条目）
然后，生成所有可能的旋转并将它们添加到结果中（我使用双端队列结构实现此目的）
最后，您跟踪访问过的元组（以避免重复）

import itertools
import collections

  
def find_combinations(sum_value, len_value):
    lst = range(sum_value, -1, -1)
    
    result = list()
    result_s = set()
    for pair in itertools.product(lst, repeat=len_value):
        if pair in result_s:
            continue
        
        if sum(pair) == sum_value:
            pair = collections.deque(pair)
            for i in range(len_value):
                t_pair = tuple(pair)
                if t_pair in result_s:
                    pair.rotate()
                    continue
                
                result.append(t_pair)
                result_s.add(t_pair)
                pair.rotate()
                
    return result

如何排列/排序数组的元素以使其匹配特定模式？

How to arrange / sort the elements of an array such that it matches a specific pattern?

python

python-3.x

sorting

问题设置

实际问题