我有一个包含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 ++。
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;
}
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 上实时运行
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
}
set<vector>
中。 - Barrystd::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
值,我们只需重复执行即可。
不可否认,这种方法不够复杂,很可能比之前的答案慢,但它应该能完成工作。
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;
}
<algorithm>
编译std::iota
时,g++存在问题,但是Visual C++在这里显然更准确地遵循标准,因此需要包含<numeric>
。 - Cheers and hth. - Alf
{2,2}
和{3,3}
。 - Barry