如何从 Python 列表中获取所有唯一组合及其重数？

Question

我知道 itertools 有一个生成组合的方法，如下所述：Get unique combinations of elements from a python list。但是，我正在寻找一个迭代器，它给出了独特的组合 and 它们的多重性。

示例：我有一个表达式，它仅取决于我 select 来自列表 L = [2,1,2,2] 的 2 个元素的组合。我需要对所有组合的结果求和。我想要的是一个迭代器，它给出例如(([1,2], 3), ([2,2], 3))。这样，我可以只计算 2 个唯一组合的表达式并乘以 3，而不是计算所有 6 个组合，其中许多组合给出相同的结果。

Answer 1

您可以组合 itertools.combinations with collections.Counter.

import itertools
import collections  

L =  [2,1,2,2]
c = collections.Counter()
c.update(map(tuple, map(sorted, itertools.combinations(L, 2))))

c.items() 然后给出：

>>> c.items()
[((1, 2), 3), ((2, 2), 3)]

为了分解它，itertools.combinations(L, 2) 给出长度为 2 的 L 的所有有序组合。然后我们使用 sorted 使它们具有可比性，因为 collections.Counter 将使用散列和平等计数。最后，因为 list 个对象不可散列，我们将它们转换为 tuple 个对象。

Answer 2

最后，我的代码花了太长时间来显式地计算每一种可能的组合，所以我想出了一种方法来只找到唯一的组合，然后分析计算它们的重数。它基于以下想法：调用输入列表 A 和每个子集中的元素数 k。首先对列表进行排序，并初始化k个指针指向A的前k个元素。然后反复尝试将最右边的指针向右移动，直到遇到新值。每次移动除最右边的另一个指针时，其右边的所有指针都将设置为它的邻居，例如如果指针 1 移动到索引 6，则指针 2 移动到索引 7，依此类推。

任何组合C的重数可以通过乘以二项式系数(N_i, m_i)得到，其中N_i和m_i是出现的次数分别在 A 和 C 中的元素 i.

下面是一个暴力方法的实现，以及一个利用唯一性的方法。

此图比较了蛮力计数与我的方法的运行时间。当输入列表有大约 20 个元素时，计数变得不可行。

# -*- coding: utf-8 -*-
from __future__ import division

from itertools import combinations
from collections import Counter
from operator import mul
import numpy as np
from scipy.special import binom

def brute(A, k):
    '''This works, but counts every combination.'''
    A_sorted = sorted(A)
    d = {}
    for comb in combinations(A_sorted, k):
        try:
            d[comb] += 1
        except KeyError:
            d[comb] = 1
        #
    return d


def get_unique_unordered_combinations(A, k):
        '''Returns all unique unordered subsets with size k of input array.'''
    # If we're picking zero elements, we can only do it in one way. Duh.
    if k < 0:
        raise ValueError("k must be non-negative")

    if k == 0 or k > len(A):
        yield ()
        return  # Done. There's only one way to select zero elements :)

    # Sorted version of input list
    A = np.array(sorted(A))
    # Indices of currently selected combination
    inds = range(k)
    # Pointer to the index we're currently trying to increment
    lastptr = len(inds) - 1

    # Construct list of indices of next element of A different from current.
    # e.g. [1,1,1,2,2,7] -> [3,3,3,5,5,6] (6 falls off list)
    skipper = [len(A) for a in A]
    prevind = 0
    for i in xrange(1, len(A)):
        if A[i] != A[prevind]:
            for j in xrange(prevind, i):
                skipper[j] = i
            prevind = i
        #

    while True:
        # Yield current combination from current indices
        comb = tuple(A[inds])
        yield comb

        # Try attempt to change indices, starting with rightmost index
        for p in xrange(lastptr, -1 , -1):
            nextind = skipper[inds[p]]
            #print "Trying to increment index %d to %d"  % (inds[p], nextind)
            if nextind + (lastptr - p) >= len(A):
                continue  # No room to move this pointer. Try the next
            #print "great success"
            for i in xrange(lastptr-p+1):
                inds[p+i] = nextind + i
            break
        else:
            # We've exhausted all possibilities, so there are no combs left
            return

如何从 Python 列表中获取所有唯一组合及其重数？

How do I get all unique combinations and their multiplicities from a Python list?

python

combinatorics