[已解决]如何求数列的子数列个数

RIXO

数列就是一串数字的集合，子数列就是他不改变相对顺序下的子集

例如 （1，2，1）
子数列为 （1）（2）（1，2）（2，1）（1，1）（1，2，1）
个数为6

我的数列是无序数列，且里面的每个值都小于等于5，即可能值为 0，1，2，3，4，5

想求一个效率高一点的算法。

如果可以尽量用C和C++，java我还没学。

最佳答案

月排行榜 / 总排行榜

Croper

2019-4-16 10:42:58

使用动态规划解决，效率要高得多

#include <vector>
#include <unordered_map>
#include <iostream>

using namespace std;
//动态规划
//从size为1的子集开始，now记录以当前节点结束的新增子集的数目
//当size增加时，now变为pre，并通过pre推出新的now


int GetSubArrCount(vector<int> v) {
        vector<int> pre(v.size()+1, 0);
        pre[0] = 1;              //当子集的size为0时，只有1个子集，空集
        int sum = 0;         
        for (int i = 0; i <= v.size(); ++i) {
                vector<int> now(v.size() - i, 0);
                for (int j = 0; j < pre.size()-1; ++j) {  //遍历pre的元素，当元素不为0时，考虑此元素与之后的每一个不重复的元素都能构成新的不重复子集
                        if (pre[j] == 0) continue;
                        unordered_map<int, bool> map;
                        for (int k = 0; k < pre.size()-1 - j; ++k) {
                                int a = v[i + j + k];
                                if (map[a] == false) {
                                        map[a] = true;
                                        now[j + k] += pre[j];
                                        sum += pre[j];
                                }
                        }
                }
                pre = move(now);
        }
        return sum;
}
int main() {
        vector<int> v = { 1,3,2,5,3,1,4,2,5};
        int i = GetSubArrCount(v);
        cout << i;
        system("pause");
}

跳转到最佳答案楼层

Croper

使用动态规划解决，效率要高得多

#include <vector>
#include <unordered_map>
#include <iostream>

using namespace std;
//动态规划
//从size为1的子集开始，now记录以当前节点结束的新增子集的数目
//当size增加时，now变为pre，并通过pre推出新的now


int GetSubArrCount(vector<int> v) {
        vector<int> pre(v.size()+1, 0);
        pre[0] = 1;              //当子集的size为0时，只有1个子集，空集
        int sum = 0;         
        for (int i = 0; i <= v.size(); ++i) {
                vector<int> now(v.size() - i, 0);
                for (int j = 0; j < pre.size()-1; ++j) {  //遍历pre的元素，当元素不为0时，考虑此元素与之后的每一个不重复的元素都能构成新的不重复子集
                        if (pre[j] == 0) continue;
                        unordered_map<int, bool> map;
                        for (int k = 0; k < pre.size()-1 - j; ++k) {
                                int a = v[i + j + k];
                                if (map[a] == false) {
                                        map[a] = true;
                                        now[j + k] += pre[j];
                                        sum += pre[j];
                                }
                        }
                }
                pre = move(now);
        }
        return sum;
}
int main() {
        vector<int> v = { 1,3,2,5,3,1,4,2,5};
        int i = GetSubArrCount(v);
        cout << i;
        system("pause");
}

Croper

如果没有不重复的要求德话直接套公式n*(n+1)/2就好了啊

//====================================分割线================================
上电脑端，看了一下，你的要求好像是要求子序列不重复且子序列是非连续子序列

首先提供一个使用stl的办法

#include <vector>
#include <set>
#include <iostream>

using namespace std;
//这种方法的思路相当直接：求出所有子序列，加入set，set的大小就是不重复子序列的数量
//但是效率可能稍低
int GetSubArrCount(vector<int> v) {
        set<vector<int>> SubArrSet;
        int N = 1 << v.size();
        for (int i = 1; i < N; ++i) {
                int a = i;
                vector<int> SubArr;
                for (int j = 0; a != 0; j++, a >>= 1) {
                        if ((a & 1) == 1) {
                                SubArr.push_back(v[j]);
                        }
                }
                SubArrSet.insert(SubArr);
        }
        return SubArrSet.size();
}

int main() {
        vector<int> v = { 1,2,1};
        int i = GetSubArrCount(v);
        cout << i;
        system("pause");
}

micolar

如果下午六点前没人给你更好的代码 我就给出我的思路 挺好的 差实现了

RIXO

micolar 发表于 2019-4-16 13:42
如果下午六点前没人给你更好的代码 我就给出我的思路 挺好的 差实现了

呃，你还回复不，不回复我明天可就设他为最佳答案了