没有重复和排序问题的组合或数组元素的排列 [英] Combinations without repeat and ordering matters or Permutations of array elements

问题描述

对于1D NumPy数组，我希望获得组合，而不会在组合中重复相同的元素.顺序很重要.因此，[a,b]和[b,a]是两个不同的组合.由于我们不希望重复，因此[a,a]和[b,b]不是有效的组合.为简单起见，让我们将每个组合的元素保留为两个.因此，输出将是具有2列的2D NumPy数组.

For a 1D NumPy array, I am looking to get the combinations without the same elements being repeated in a combination. The order is important. So, [a,b] and [b,a] would be two distinct combinations. Since we don't want repeats, [a,a] and [b,b] aren't valid combinations. For simplicity, let's keep it to two elements per combination. Thus, the output would be a 2D NumPy array with 2 columns.

所需结果与itertools.product输出基本相同，除了我们需要掩盖重复的组合.这样，我们可以解决一个示例案例，就像这样-

The desired result would be essentially same as itertools.product output except that we need to mask out the combinations that are repeated. As such, we can solve it for a sample case, like so -

In [510]: import numpy as np

In [511]: a = np.array([4,2,9,1,3])

In [512]: from itertools import product

In [513]: np.array(list(product(a,repeat=2)))[~np.eye(len(a),dtype=bool).ravel()]
Out[513]: 
array([[4, 2],
       [4, 9],
       [4, 1],
       [4, 3],
       [2, 4],
       [2, 9],
       [2, 1],
       [2, 3],
       [9, 4],
       [9, 2],
       [9, 1],
       [9, 3],
       [1, 4],
       [1, 2],
       [1, 9],
       [1, 3],
       [3, 4],
       [3, 2],
       [3, 9],
       [3, 1]])

但是，创建那个巨大的数组然后屏蔽掉并因此不使用某些元素，对我来说似乎并不是很有效.

But, creating that huge array and then masking out and hence not using some elements, doesn't look too efficient to me.

这让我开始思考是否 numpy.ndarray.strides 可以在这里使用.我想到了一个解决方案，打算将其发布为答案，但也希望看到其他有效的解决方案.

That got me thinking if numpy.ndarray.strides could be leveraged here. I have one solution with that idea in mind, which I will be posting as an answer post, but would love to see other efficient ones.

在用法方面-我们遇到了带有邻接矩阵的这些情况，我认为解决这样的问题会很好.为了更轻松，更有效地实现其他问题的即插即用，最好的最终输出不是某些中间数组的 view .

In terms of usage - We come across these cases with adjacency matrices among others and I thought it would be good to solve such a problem. For easier and efficient plug-n-play into other problems, it would be nice to have the final output that's not a view of some intermediate array.

推荐答案

类似

Seems like np.lib.stride_tricks.as_strided could be used to maximize the efficiency of views and we delay the copying until the final stage, where we assign into an initialized array. The implementation would be in two steps, with some work needed for the second column (as shown in the sample case in the question), which we are calling as one-cold (fancy name that denotes one element missing per sequence / is cold in a each interval of len(input_array) - 1)

def onecold(a):
    n = len(a)
    s = a.strides[0]
    strided = np.lib.stride_tricks.as_strided
    b = np.concatenate((a,a[:-1]))
    return strided(b[1:], shape=(n-1,n), strides=(s,s))

要展示，onecold带有示例盒-

In [563]: a
Out[563]: array([4, 2, 9, 1, 3])

In [564]: onecold(a).reshape(len(a),-1)
Out[564]: 
array([[2, 9, 1, 3],
       [4, 9, 1, 3],
       [4, 2, 1, 3],
       [4, 2, 9, 3],
       [4, 2, 9, 1]])

为解决原始问题，我们将像这样使用它-

To solve the original problem, we will use it like so -

def combinations_without_repeat(a):
    n = len(a)
    out = np.empty((n,n-1,2),dtype=a.dtype)
    out[:,:,0] = np.broadcast_to(a[:,None], (n, n-1))
    out.shape = (n-1,n,2)
    out[:,:,1] = onecold(a)
    out.shape = (-1,2)
    return out  

样品运行-

In [574]: a
Out[574]: array([4, 2, 9, 1, 3])

In [575]: combinations_without_repeat(a)
Out[575]: 
array([[4, 2],
       [4, 9],
       [4, 1],
       [4, 3],
       [2, 4],
       [2, 9],
       [2, 1],
       [2, 3],
       [9, 4],
       [9, 2],
       [9, 1],
       [9, 3],
       [1, 4],
       [1, 2],
       [1, 9],
       [1, 3],
       [3, 4],
       [3, 2],
       [3, 9],
       [3, 1]])

对于ints-

In [578]: a = np.random.randint(0,9,(1000))

In [579]: %timeit combinations_without_repeat(a)
100 loops, best of 3: 2.35 ms per loop

很乐意见到其他人！

这篇关于没有重复和排序问题的组合或数组元素的排列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！