遍历不同的大小为k的子集

Question

我有一个包含n个整数（可以不唯一）的数组，我想迭代所有大小为k的子集。但我想要排除所有重复的子集。

例如：

array = {1,2,2,3,3,3,3}, n = 7, k = 2

那么我想要迭代的子集（每个子集只迭代一次）是：

{1,2},{1,3},{2,2},{2,3},{3,3}

什么是高效的算法来完成这个任务？递归方法是否最有效/优雅？

如果您有特定于语言的答案，我正在使用C ++。

- Alex

---

为什么你不能先对原始数组进行去重，然后再使用标准解决方案枚举所有子集呢？ - Kerrek SB

@KerrekSB 这将删除 {2,2} 和 {3,3}。 - Barry

@KerrekSB 我不会错过 {2,2} 和 {3,3} 吗？编辑：哦，你更快。还有那些给我投反对票的人，我的问题有什么问题吗？ - Alex

嗯，离题了，应该发到CS上吧？ - Kerrek SB

我认为这并不完全是离题，因为它可能部分或完全地被标准库算法所覆盖。例如，对于一个稍微不同的问题，“std::next_permutation”可以成为答案的一部分。这个问题的答案涉及到以一种受限制的方式进行计数（仅增加数字序列），但我不认为标准库能够帮助解决这个问题。 - Cheers and hth. - Alf

Answer 1

同样（或几乎相同）的算法可用于按字典顺序生成唯一值集合的组合，也可用于按字典顺序生成多重集合的组合。通过这种方式可以避免去重，这是非常昂贵的操作，并且也避免了维护所有生成的组合的必要性。但需要注意的是原始值列表需要进行排序。

以下简单实现以平均时间复杂度（和最坏情况下）O(n) 的时间找到多重集合中n个值的下一个k-组合。它期望传入两个区间：第一个区间是已排序的k-组合，第二个区间是已排序的多重集合。（如果任一区间未排序或第一个区间中的值不构成第二个区间的子(multi)set，则行为未定义；没有进行健全性检查。）

只使用了第二个区间的尾迭代器，但我认为这使得调用约定有些奇怪。

template<typename BidiIter, typename CBidiIter,
         typename Compare = std::less<typename BidiIter::value_type>>
int next_comb(BidiIter first, BidiIter last,
              CBidiIter /* first_value */, CBidiIter last_value,
              Compare comp=Compare()) {
  /* 1. Find the rightmost value which could be advanced, if any */
  auto p = last;
  while (p != first && !comp(*(p - 1), *--last_value)) --p;
  if (p == first) return false;
  /* 2. Find the smallest value which is greater than the selected value */
  for (--p; comp(*p, *(last_value - 1)); --last_value) { }
  /* 3. Overwrite the suffix of the subset with the lexicographically smallest
   *    sequence starting with the new value */
  while (p != last) *p++ = *last_value++;
  return true;
}

明显地，步骤1和步骤2结合最多需要O(n)次比较，因为n个值中每个值最多只使用一次。步骤3最多复制O(k)个值，我们知道k≤n。

如果没有重复的值，这可以改进为O(k)，方法是将当前组合维护为值列表的迭代器容器而不是实际值。这也避免了复制值，但代价是额外的解引用。如果我们还缓存将每个值迭代器关联到下一个较大值第一个实例的函数，那么我们可以消除步骤2并将算法减少到O(k)，即使有重复的值也是如此。如果有大量的重复项并且比较很昂贵，这可能是值得的。

以下是一个简单的使用示例：

std::vector<int> values = {1,2,2,3,3,3,3};
/* Since that's sorted, the first subset is just the first k values */
const int k = 2;
std::vector<int> subset{values.cbegin(), values.cbegin() + k};

/* Print each combination */
do {
  for (auto const& v : subset) std::cout << v << ' ';
  std::cout << '\n';
} while (next_comb(subset.begin(),  subset.end(),
                   values.cbegin(), values.cend()));

在 coliru 上实时运行

- rici

---

谢谢。我最终缓存了下一个最大整数的索引，就像你建议的那样。我喜欢这不依赖于“集合”的方法。 - Alex

Answer 2

我喜欢使用位运算来解决这个问题。当然，这会限制你的向量中只能有32个元素，但这仍然很酷。

首先，给定一个位掩码，确定下一个位掩码排列（来源：source）：

uint32_t next(uint32_t v) {
    uint32_t t = v | (v - 1);
    return (t + 1) | (((~t & -~t) - 1) >> (__builtin_ctz(v) + 1));  
}

接下来，给定一个 vector 和一个位掩码，根据该掩码生成一个新的 vector：

std::vector<int> filter(const std::vector<int>& v, uint32_t mask) {
    std::vector<int> res;
    while (mask) {
        res.push_back(v[__builtin_ctz(mask)]);
        mask &= mask - 1;
    }   
    return res;
}

接下来，我们只需要一个循环：

std::set<std::vector<int>> get_subsets(const std::vector<int>& arr, uint32_t k) {   
    std::set<std::vector<int>> s;
    uint32_t max = (1 << arr.size());
    for (uint32_t v = (1 << k) - 1; v < max; v = next(v)) {
        s.insert(filter(arr, v));
    }
    return s;
}

int main()
{
    auto s = get_subsets({1, 2, 2, 3, 3, 3, 3}, 2);
    std::cout << s.size() << std::endl; // prints 5
}

- Barry

---

在这里插入有关使用位掩码快速迭代的注释，但最终仍将结果放入set<vector>中。 - Barry

挺酷的，看起来能用！反正我觉得32个元素足够了。我猜这要求我的数组事先是排序好的（如果没有的话）？ - Alex

@Alex Er，我想去重逻辑是相当正确的。无论如何，这个解决方案唯一好的地方就是很酷。你肯定可以做得更好。 - Barry

Answer 3

与之前的答案不同，这种方法并不高效，也没有像许多位操作那样精妙。但是它不限制您的数组大小或子集大小。

此解决方案使用std::next_permutation生成组合，并利用std::set的唯一性属性。

#include <algorithm>
#include <vector>
#include <set>
#include <iostream>
#include <iterator>

using namespace std;

std::set<std::vector<int>> getSubsets(const std::vector<int>& vect, size_t numToChoose)
{
    std::set<std::vector<int>> returnVal;
    // return the whole thing if we want to
    // choose everything 
    if (numToChoose >= vect.size())
    {
        returnVal.insert(vect);
        return returnVal;
    }

    // set up bool vector for combination processing
    std::vector<bool> bVect(vect.size() - numToChoose, false);

    // stick the true values at the end of the vector
    bVect.resize(bVect.size() + numToChoose, true); 

    // select where the ones are set in the bool vector and populate
    // the combination vector
    do
    {
        std::vector<int> combination;
        for (size_t i = 0; i < bVect.size() && combination.size() <= numToChoose; ++i)
        {
            if (bVect[i])
                combination.push_back(vect[i]);
        }
        // sort the combinations
        std::sort(combination.begin(), combination.end());

        // insert this new combination in the set
        returnVal.insert(combination);
    } while (next_permutation(bVect.begin(), bVect.end()));
    return returnVal;
}

int main()
{
    std::vector<int> myVect = {1,2,2,3,3,3,3};

    // number to select
    size_t numToSelect = 3;

    // get the subsets
    std::set<std::vector<int>> subSets = getSubsets(myVect, numToSelect);

    // output the results
    for_each(subSets.begin(), subSets.end(), [] (const vector<int>& v) 
    { cout << "subset "; copy(v.begin(), v.end(), ostream_iterator<int>(cout, " ")); cout << "\n"; });
}

现场演示: http://coliru.stacked-crooked.com/a/beb800809d78db1a

基本上，我们设置了一个布尔向量，并使用与布尔向量中的true项位置相对应的值填充了一个向量。然后我们对其进行排序并将其插入到一个集合中。 std::next_permutation会在布尔数组中随机排列true值，我们只需重复执行即可。

不可否认，这种方法不够复杂，很可能比之前的答案慢，但它应该能完成工作。

- PaulMcKenzie

Answer 4

这个解决方案的基本思想是一个像next_permutation函数一样的函数，但它生成下一个“数字”的升序序列。这里称为ascend_ordered。

template< class It >
auto ascend_ordered( const int n_digits, const It begin, const It end )
    -> bool
{
    using R_it = reverse_iterator< It >;
    const R_it r_begin  = R_it( end );
    const R_it r_end    = R_it( begin );

    int max_digit = n_digits - 1;
    for( R_it it = r_begin ; it != r_end; ++it )
    {
        if( *it < max_digit )
        {
            ++*it;
            const int n_further_items = it - r_begin;
            for( It it2 = end - n_further_items; it2 != end; ++it2 )
            {
                *it2 = *(it2 - 1) + 1;
            }
            return true;
        }
        --max_digit;
    }
    return false;
}

案例的主程序如下：

auto main() -> int
{
    vector<int> a = {1,2,2,3,3,3,3};
    assert( is_sorted( begin( a ), end( a ) ) );
    const int k = 2;
    const int n = a.size();
    vector<int> indices( k );
    iota( indices.begin(), indices.end(), 0 );      // Fill with 0, 1, 2 ...
    set<vector<int>> encountered;
    for( ;; )
    {
        vector<int> current;
        for( int const i : indices ) { current.push_back( a[i] ); }
        if( encountered.count( current ) == 0 )
        {
            cout << "Indices " << indices << " -> values " << current << endl;
            encountered.insert( current );
        }
        if( not ascend_ordered( n, begin( indices ), end( indices ) ) )
        {
            break;
        }
    }
}

支持包含和输入/输出：

#include <algorithm>
using std::is_sorted;

#include <assert.h>

#include <iterator>
using std::reverse_iterator;

#include <iostream>
using std::ostream; using std::cout; using std::endl;

#include <numeric>
using std::iota;

#include <set>
using std::set;

#include <utility>
using std::begin; using std::end;

#include <vector>
using std::vector;

template< class Container, class Enable_if = typename Container::value_type >
auto operator<<( ostream& stream, const Container& c )
    -> ostream&
{
    stream << "{";
    int n_items_outputted = 0;
    for( const int x : c )
    {
        if( n_items_outputted >= 1 ) { stream << ", "; }
        stream << x;
        ++n_items_outputted;
    }
    stream << "}";
    return stream;
}

- Cheers and hth. - Alf

---

对于 {1,2,2,3,3,3,4} 和 k=3，它生成了两次 {1,2,3}。 - Alex

谢谢！很抱歉那是一个错误。我错误地想象了集合总是按升序生成，但这只对索引成立...通过跟踪所有遇到的集合来解决问题。 - Cheers and hth. - Alf

还修复了一个标题的问题：使用<algorithm>编译std::iota时，g++存在问题，但是Visual C++在这里显然更准确地遵循标准，因此需要包含<numeric>。 - Cheers and hth. - Alf