PROBLEM SETUP

I am using the following code to generate an array that contains arrays which have a given length and whose elements' sums equal to some given value (Note that repetition of digits is allowed):-

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))

For example,

If the sum, sum_value, is 4, and the length, len_value, is 2, the output this code produces is:-

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

---

THE ACTUAL PROBLEM

This code works perfectly - it contains all the combinations that I was expecting. But the problem here is that the order of the array is incorrect.

That is,

In the previous example, where the required sum was 4, and the length was 2, the output should have been this:-

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

So if the required sum is 4, and the length is 3, the output that this code produces is:-

[
    (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),
]

But the order of the expected output is:-

[
    (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),
    ...,
]

So my question is, how can I arrange the elements of this array such that it matches this pattern?

---

P.S. - You can refer to the , from which this one is inspired.

CodePudding user response：

You could sort the array by decreasing variance (deviation from the elements mean):

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

"numpy.var" calculates the variance of each element. Since the variance is the squared standard deviation, a huge outlier like 4 in (4, 0, 0) produces a huge variance. The "-" sorts in decreasing order.

If you need the same number combinations (like (4, 0, 0) and (0, 4, 0), which produces the same variance) in a specific order you could very slightly weight your elements by adding a small number to the element that should be sorted first:

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

CodePudding user response：

Try this idea:

• Start from the largest possible value (to get (sum_len, 0, ..., 0) as the first entry)
• then, produce all possible rotations and add them to the result (I achieve this using the double ended queue structure)
• last, you keep track of the visited tuples (to avoid duplicates)

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:
                    continue
                
                result.append(t_pair)
                result_s.add(t_pair)
                pair.rotate()
                
    return result