Python/numpy中的n维网格 [英] n dimensional grid in Python / numpy

问题描述

我有一个未知数的变量n，其某些已知步骤s的范围可以从0到1，条件是它们的总和为1.我想创建一个所有组合的矩阵.例如，如果n=3和s=0.33333，则网格将为(顺序不重要):

I have an unknown number n of variables that can range from 0 to 1 with some known step s, with the condition that they sum up to 1. I want to create a matrix of all combinations. For example, if n=3 and s=0.33333 then the grid will be (The order is not important):

0.00, 0.00, 1.00
0.00, 0.33, 0.67
0.00, 0.67, 0.33
0.00, 1.00, 0.00
0.33, 0.00, 0.67
0.33, 0.33, 0.33
0.33, 0.67, 0.00
0.67, 0.00, 0.33
0.67, 0.33, 0.00
1.00, 0.00, 0.00

如何为任意n做到这一点?

How can I do that for an arbitrary n?

推荐答案

EDIT

这是一个更好的解决方案.它基本上 partitions 将步数转化为变量数量，以生成所有有效的组合:

Here is a better solution. It basically partitions the number of steps into the amount of variables to generate all the valid combinations:

def partitions(n, k):
    if n < 0:
        return -partitions(-n, k)
    if k <= 0:
        raise ValueError('Number of partitions must be positive')
    if k == 1:
        return np.array([[n]])
    ranges = np.array([np.arange(i + 1) for i in range(n + 1)])
    parts = ranges[-1].reshape((-1, 1))
    s = ranges[-1]
    for _ in range(1, k - 1):
        d = n - s
        new_col = np.concatenate(ranges[d])
        parts = np.repeat(parts, d + 1, axis=0)
        s = np.repeat(s, d + 1) + new_col
        parts = np.append(parts, new_col.reshape((-1, 1)), axis=1)
    return np.append(parts, (n - s).reshape((-1, 1)), axis=1)

def make_grid_part(n, step):
    num_steps = round(1.0 / step)
    return partitions(num_steps, n) / float(num_steps)

print(make_grid_part(3, 0.33333))

输出:

array([[ 0.        ,  0.        ,  1.        ],
       [ 0.        ,  0.33333333,  0.66666667],
       [ 0.        ,  0.66666667,  0.33333333],
       [ 0.        ,  1.        ,  0.        ],
       [ 0.33333333,  0.        ,  0.66666667],
       [ 0.33333333,  0.33333333,  0.33333333],
       [ 0.33333333,  0.66666667,  0.        ],
       [ 0.66666667,  0.        ,  0.33333333],
       [ 0.66666667,  0.33333333,  0.        ],
       [ 1.        ,  0.        ,  0.        ]])

为进行比较:

%timeit make_grid_part(5, .1)
>>> 338 µs ± 2.25 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
%timeit make_grid_simple(5, .1)
>>> 26.4 ms ± 806 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

make_grid_simple实际上，如果再往下推一点，就会耗尽内存.

make_grid_simple actually runs out of memory if you push it just a bit further.

这是一种简单的方法:

def make_grid_simple(n, step):
    num_steps = round(1.0 / step)
    vs = np.meshgrid(*([np.linspace(0, 1, num_steps + 1)] * n))
    all_combs = np.stack([v.flatten() for v in vs], axis=1)
    return all_combs[np.isclose(all_combs.sum(axis=1), 1)]

print(make_grid_simple(3, 0.33333))

输出:

[[ 0.          0.          1.        ]
 [ 0.33333333  0.          0.66666667]
 [ 0.66666667  0.          0.33333333]
 [ 1.          0.          0.        ]
 [ 0.          0.33333333  0.66666667]
 [ 0.33333333  0.33333333  0.33333333]
 [ 0.66666667  0.33333333  0.        ]
 [ 0.          0.66666667  0.33333333]
 [ 0.33333333  0.66666667  0.        ]
 [ 0.          1.          0.        ]]

但是，这并不是最有效的方法，因为它只是简单地进行所有可能的组合，然后仅选择相加为1的组合，而不是首先仅生成正确的组合.对于较小的步长，可能会导致内存成本过高.

However, this is not the most efficient way to do it, since it is simply making all the possible combinations and then just picking the ones that add up to 1, instead of generating only the right ones in the first place. For small step sizes, it may incur in too high memory cost.

这篇关于Python/numpy中的n维网格的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！