北京SEO百度排名_网络推广_网站建设_专业网站优化【启点网络】

网站制作SEO优化推广10年,客户1200+

SEO算法_搜索引擎正排索引_生成排列与生成子集

文章分类: SEO方案资讯 文章来源: 北京启点网络 文章作者: 北京SEO顾问 时间: 2018-06-05 17:43:32浏览热度:


[导读]:

排列或子集的生成,可以使用递归构造,也可以直接生成。直接生成的方法时

排列或子集的生成,可以使用递归构造,也可以直接生成。直接生成的方法时间复杂度高,无法进行适当的剪枝,如果想减小时间复杂度,可以使用回溯法进行递归构造。

1、排列的递归构造很简单,伪码如下:

print_permutation(序列R,集合S)
    if(S为空)
        print 序列R
        return
    for s in 集合S
        print_permutation(序列R + s, 集合S - s)

该伪码假设集合S中的元素不重复,如果需要生成可重集的排列,则需要在循环中对集合S中每个“不同元素”进行“该元素在R中出现的次数小于在S中出现的次数”的判断。

2、排列的直接生成可以使用STL中的next_permutation(),示例代码如下:

#include <iostream>
#include <algorithm>

int main() {
    //test1
    int myints[] = {1, 2, 3};
    std::sort(myints, myints + 3);
    std::cout << "The 3! possible permutations with 3 elements:\n";
    do {
        std::cout << myints[0] << ' ' << myints[1] << ' ' << myints[2] << '\n';
    } while(std::next_permutation(myints, myints + 3));
    std::cout << "After loop: " << myints[0] << ' ' << myints[1] << ' ' << myints[2] << '\n';
    
    //test2
    std::string s = "aba";
    std::sort(s.begin(), s.end());
    do {
        std::cout << s << '\n';
    } while(std::next_permutation(s.begin(), s.end()));

    return 0;
}

3、子集的生成可以使用位向量法,递归方式,参考代码如下:

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

void print_subset(vector<int> &R, vector<int> &S, int index) {
    if(index == R.size()) {
        for(int i = 0; i < S.size(); i++)
            if(S[i]) printf("%d ", R[i]);
        printf("\n");
        return;
    }
    S[index] = 0;
    print_subset(R, S, index + 1);
    S[index] = 1;
    print_subset(R, S, index + 1);
}

int main() {
    vector<int> R{1,2, 3};
    vector<int> S(R.size(), 0);
    print_subset(R, S, 0);

    return 0;
}

4、子集的直接生成可以使用二进制法,参考代码如下:

void print_subset(vector<int> &S) {
    for(int i = 0; i < (1 << S.size()); i++) {
        for(int j = 0; j < S.size(); j++) {
            if(i & (1 << j)) printf("%d ", S[j]);
        }
        printf("\n");
    }
}

此方法虽然简洁,但要求集合S的元素不超过int的位数。


标题:SEO算法_搜索引擎正排索引_生成排列与生成子集
地址:http://www.seozoe.com/news/zx/538.html _北京SEO
声明:非特殊说明,本文为本站原创(翻译)文章,转载请注明:本文转自:北京SEO启点网络_启点


请您留下您的小脚印:

服务支持

我们珍惜您每一次在线询盘,有问必答,用专业的态度,贴心的服务。

让您真正感受到我们的与众不同!

合作流程

合作流程

网站制作流程从提出需求到网站制作报价,再到网页制作,每一步都是规范和专业的。

常见问题

常见问题

提供什么是网站定制?你们的报价如何?等网站建设常见问题。

常见问题

售后保障

网站制作不难,难的是一如既往的热情服务及技术支持。我们知道:做网站就是做服务,就是做售后。