组合学：包含替代元素的列表

Question

我有一个 python 列表，其中包含一个或多个元素的一维 numpy 数组作为元素。将每个数组元素视为相应列表元素的替代项。

一个例子：

[array([1]),array([2]),array([2,3]),array([3]),array([4]),array([3,4,5])]

我想要两样东西：

1) 所有选项的组合：

array([[1,2,2,3,4,3],
       [1,2,3,3,4,3],
       [1,2,2,3,4,4],
       [1,2,3,3,4,4],
       [1,2,2,3,4,5],
       [1,2,3,3,4,5]])

2.重复次数最少的组合：

array([1,2,2,3,4,5])

或

array([1,2,3,3,4,5]).

第二个应该不难得到，一旦有了第一个，但我不确定。

我还想使用更复杂的设置，例如

datasets_complete = [("iris1", iris1), ("iris2", iris2)]
percentages = [0.05, 0.1, 0.2, 0.5]
imputers = [SimpleFill(), KNN(k=3), SoftImpute(), MICE()]
gridWidths = [0.1, 0.2]

seq = [datasets_complete, percentages, imputers, gridWidths]
testgrid = all_combinations(seq)

其中 iris1 和 iris2 是 pandas 数据帧。

Answer 1

您可以像这样使用 itertools.product 函数：

import itertools
from numpy import array
test = [array([1]),array([2]),array([2,3]),array([3]),array([4]),array([3,4,5])]
combinations = [list(tup) for tup in itertools.product(*test)]
print(combinations)

这个returns:

[[1, 2, 2, 3, 4, 3], 
 [1, 2, 2, 3, 4, 4], 
 [1, 2, 2, 3, 4, 5], 
 [1, 2, 3, 3, 4, 3], 
 [1, 2, 3, 3, 4, 4], 
 [1, 2, 3, 3, 4, 5]]

第 2 部分不可解，因为可能存在非唯一解...

Answer 2

这是一个基于 NumPy 的方法 -

def all_combs(a):          # Parte-1
    num_combs = np.prod(list(map(len,a)))
    return np.array(np.meshgrid(*a)).reshape(-1,num_combs).T

def get_minrep_combs(a):   # Parte-2
    out = all_combs(a)
    counts = (np.diff(np.sort(out,axis=1),axis=1)==0).sum(1)
    return out[counts == counts.min()]

样本运行-

In [161]: a = [np.array([1]),np.array([2]),np.array([2,3]),np.array([3]),\
     ...:                                 np.array([4]),np.array([3,4,5])]

In [162]: all_combs(a)  # Part-1 results
Out[162]: 
array([[1, 2, 2, 3, 4, 3],
       [1, 2, 2, 3, 4, 4],
       [1, 2, 2, 3, 4, 5],
       [1, 2, 3, 3, 4, 3],
       [1, 2, 3, 3, 4, 4],
       [1, 2, 3, 3, 4, 5]])

In [163]: get_minrep_combs(a) # Part-2 results
Out[163]: 
array([[1, 2, 2, 3, 4, 5],
       [1, 2, 3, 3, 4, 5]])

只是为了让大家了解一下 all_combs，这里还有一些 "normal" 示例运行s -

In [166]: a = [np.array([2,3]), np.array([5,6,7])]

In [167]: all_combs(a)
Out[167]: 
array([[2, 5],
       [3, 5],
       [2, 6],
       [3, 6],
       [2, 7],
       [3, 7]])

In [164]: a = [np.array([2,3,4]), np.array([5,6,7,9])]

In [165]: all_combs(a)
Out[165]: 
array([[2, 5],
       [3, 5],
       [4, 5],
       [2, 6],
       [3, 6],
       [4, 6],
       [2, 7],
       [3, 7],
       [4, 7],
       [2, 9],
       [3, 9],
       [4, 9]])

性能

为了性能，我们可以避免 part-1 中的转置，并在 part-2 中沿列 (axis=0) 执行操作，还可以使用切片来避免 np.diff，因此有一个优化版本，像这样 -

def get_minrep_combs_optimized(a):   # Parte-1,2
    num_combs = np.prod(list(map(len,a)))
    out = np.array(np.meshgrid(*a)).reshape(-1,num_combs)  
    sorted_out = np.sort(out,axis=0)
    counts = (sorted_out[1:] == sorted_out[:-1]).sum(0)
    return out[:,counts == counts.min()].T

样本运行-

In [188]: a = [np.array([1]),np.array([2]),np.array([2,3]),np.array([3]),\
     ...:                                 np.array([4]),np.array([3,4,5])]

In [189]: get_minrep_combs_optimized(a)
Out[189]: 
array([[1, 2, 2, 3, 4, 5],
       [1, 2, 3, 3, 4, 5]])

运行时测试

这是创建样本输入数据的一种方法，它最多有 3 个元素，每个子列表有一些与其他子列表中的元素匹配 -

In [42]: lens = np.random.randint(1,4,(20))

In [43]: a = [np.random.randint(1,10,L) for L in lens]

In [44]: lens
Out[44]: array([1, 1, 2, 2, 2, 2, 1, 2, 3, 2, 1, 2, 2, 3, 1, 1, 3, 2, 2, 3])

In [45]: a
Out[45]: 
[array([8]),
 array([8]),
 array([7, 9]),
 array([5, 5]),
 array([6, 4]),
 array([3, 1]),
 array([8]),
 array([1, 9]),
 array([9, 5, 7]),
 array([1, 1]),
 array([3]),
 array([1, 5]),
 array([5, 5]),
 array([7, 9, 2]),
 array([5]),
 array([1]),
 array([3, 2, 9]),
 array([3, 7]),
 array([5, 3]),
 array([2, 7, 3])]

计时 -

In [46]: %timeit leastReps(combinations(a)) #@Daniel Forsman's soln
1 loops, best of 3: 330 ms per loop

In [47]: %timeit get_minrep_combs_optimized(a)
10 loops, best of 3: 28.7 ms per loop

让我们有更多的比赛-

In [50]: a = [np.random.randint(1,4,L) for L in lens]

In [51]: %timeit leastReps(combinations(a)) #@Daniel Forsman's soln
1 loops, best of 3: 328 ms per loop

In [52]: %timeit get_minrep_combs_optimized(a)
10 loops, best of 3: 29.5 ms per loop

性能差异没有太大变化。

Answer 3

def combinations(arrList):
    mesh=np.meshgrid(*arrList)
    mesh=[arr.ravel() for arr in mesh]
    return np.array(mesh).T

def leastReps(combs):
    uniques=np.array([np.unique(arr).size for arr in list(combs)])
    mostUni = (uniques == np.max(uniques))
    return combs[mostUni]

我的和Divakar的唯一区别是我不用提前计算产品的数量，我用的uniques最多，他用的repetitions最少，应该是等价的。

组合学：包含替代元素的列表

Combinatorics: list with alternative elements

python

numpy

combinatorics