c++ - 如何生成数组 C++ 的所有长度为 k 的唯一子集

Question

我需要一种方法来生成数组长度为 k 的所有唯一子集，类似于 python 中的 itertools.combinations()。我正在尝试获取这些集以进行关联挖掘，直到支持度小于 2。任何通过 2 的集都被证明是令人头疼的。此外，不能为此使用任何 STL 函数。

如有任何见解，我们将不胜感激。

最接近我的问题的地方是:Generate all subsets of size k (containing k elements) in Python

P.S 集合(数组)中的每个元素都是整数。

主要是:

int temp = 0;
int setsize = 2;
int **testarray = subsets(itemset,itemsetSize,setsize);
for (int i = 0; i < 1300; i++)
{
    for(int j = 0; j < 10; j++)
    {
        cout<<testarray[i][j];
    }
}
cout<<endl;

在函数中:

int** subsets (int inputArray[],int arraySize, int k)
{
    size_t n = arraySize;

    int **resultArray = 0;
    resultArray = new int *[1000];

    size_t i = (1 << k) -1;

    while( !(i >> n) ) 
    {
        int pushBack = 0;
        int pushBack2 = 0;
        int v[500];
        for (size_t j = 0; j<n; j++)
        {
            if (i & (1 << j))
            {
                v[pushBack] = inputArray[j];
                pushBack++;
            }
        }
        resultArray[pushBack2] = v;
        pushBack2++;
        i = (i+(i&(-i)))|(((i^(i+(i&(-i))))>>2)/(i&(-i)));          
    }
    return resultArray;
}

Answer 1

#include <vector>
#include <iostream>
using namespace std;

vector<vector<int>> subsets(const vector<int>& input, int k)
{
    size_t n = input.size();

    vector<vector<int>> result;

    size_t i = (1 << k) - 1;

    while( !(i >> n) ) 
    {
        vector<int> v;

        for (size_t j = 0; j < n; j++)
           if (i & (1 << j))
                v.push_back(input[j]);

        result.push_back(v);

        i = (i+(i&(-i)))|(((i^(i+(i&(-i))))>>2)/(i&(-i))); 
    }

    return result;
}

int main()
{
    auto out = subsets({5,2,8,14,3,9,11}, 3);
    for (auto x : out)
    {
        for (auto y : x)
            cout << y << " ";
        cout << endl;
    }
}

输出:

5 2 8 
5 2 14 
5 8 14 
2 8 14 
5 2 3 
5 8 3 
2 8 3 
5 14 3 
2 14 3 
8 14 3 
5 2 9 
5 8 9 
2 8 9 
5 14 9 
2 14 9 
8 14 9 
5 3 9 
2 3 9 
8 3 9 
14 3 9 
5 2 11 
5 8 11 
2 8 11 
5 14 11 
2 14 11 
8 14 11 
5 3 11 
2 3 11 
8 3 11 
14 3 11 
5 9 11 
2 9 11 
8 9 11 
14 9 11 
3 9 11