Posts Tagged Algorithm

排列字典序算法

Posted by MatRush in Algorithm on 2009年12月5日

今天学校圣诞编程组队网络赛出了道排列题，于是在这里记录一下解决全排列及第N个排列问题的字典序算法。
字典序算法中，对于数字1、2、3……n的排列，不同排列的先后关系是从左到右逐个比较对应的数字的先后来决定的。例如对于5个数字的排列12354和12345，排列12345在前，排列12354在后。按照这样的规定，5个数字的所有的排列中最前面的是12345，最后面的是54321。
字典序算法如下：
设P是1~n的一个全排列:P = P1P2……Pn = P1P2……Pj-1PjPj+1……Pk-1PkPk+1……Pn
（1）从排列的最右端开始，找出第一个比右边数字小的数字的序号j（j从左端开始计算），即 j=max{i|pi （2）在Pj的右边的数字中，找出所有比Pj大的数中最小的数字Pk，即 k=max{i|Pi>Pj}（右边的数从右至左是递增的，因此k是所有大于Pj的数字中序号最大者）
（3）对换Pj，Pk
（4）再将Pj+1……Pk-1PkPk+1Pn反转，即得到排列P的下一个排列。

以下是模拟STL函数next_permutation(num,num+n)实现的代码：


#include <iostream>
#include <algorithm>
using namespace std;
int n,m,i;
int num[1024];
bool next(int n)
{
    int j = -1;
    for (int i = n-2;i >= 0;i--)
        if (num[i] < num[i+1])
        {
            j = i;
            break;
        }//找到第一个比自己后面的元素小的元素，赋给j
    if (j < 0)
        return 0;
    int k;
    for (int i = n-1;i > j;i--)
        if (num[i] > num[j])
        {
            k = i;
            break;
        }//找到右边降序排列中最右边的大于自己的元素，将其位置赋给k
    swap(num[j],num[k]);//交换num[j]和num[k],右边得到一个新的降序排列的序列
    reverse(num+j+1,num+n);//反转右边的序列,使其升序排列
    return 1;
}
int main()
{
    while (scanf("%d%d",&n,&m) != EOF && n && m)
    {
        for (i = 0;i < n;i++)
        {
            //scanf("%d", &num);
            num[i] = i+1;
        }
        sort(num,num+n);
        for (i = 1;i < m;i++)
            next(n);//模拟STL函数next_permutation(num,num+n);
        for (i = 0;i < n;i++)
        {
            printf("%d", num[i]);
            if (i == n-1)
                printf("\n");
        }
    }
    return 0;
}

附上能用next_permutation()函数解决的题：PKU1146、1256、1731、1833、3187
HDU1027

,

No Comments

《算法导论》入手

Posted by MatRush in Algorithm on 2009年08月25日

终于买了本机械工业出版社翻译的《算法导论》（原书第二版），花了63.8+5=78.8大洋，看着这本绝对重量级的算法书，不知道以后的日子会怎么样，反正估计CLRS+刘汝佳的黑书至少能陪伴我即将到来的大一生活，拿在手里真是很能感受到它的分量，既然书名《Introduction to Algorithms》，希望它真的能让我在算法之路上能走得更远一些。

附上几张裸照。

IMG_1506IMG_1505

IMG_1508IMG_1507

目录：

算法导论 第二版（Introduction to Algorithms, Second Edition）

目录（Table of Contents）
前言（Preface）
第一部分（Part I） 基础（Foundations）
第一章 计算中算法的角色（The Role of Algorithms in Computing）
第二章 开始（Getting Started）
第三章 函数的增长率（Growth of Functions）
第四章 递归（Recurrences）
第五章 概率分析与随机化算法（Probabilistic Analysis and Randomized Algorithms）
第二部分（Part II） 排序与顺序统计（Sorting and Order Statistics）
第六章 堆排序（Heapsort）
第七章 快速排序（Quicksort）
第八章 线性时间中的排序（Sorting in Linear Time）
第九章 中值与顺序统计（Medians and Order Statistics）
第三部分（Part III） 数据结构（Data Structures）
第十章 基本的数据结构（Elementary Data Structures）
第十一章 散列表（Hash Tables）
第十二章 二叉查找树（Binary Search Trees）
第十三章 红-黑树（Red-Black Trees）
第十四章 扩充的数据结构（Augmenting Data Structures）
第四部分（Part IV） 高级的设计与分析技术（Advanced Design and Analysis Techniques）
第十五章 动态规划（Dynamic Programming）
第十六章 贪婪算法（Greedy Algorithms）
第十七章 分摊分析（Amortized Analysis）
第五部分（Part V） 高级的数据结构（Advanced Data Structures）
第十八章 B-树（B-Trees）
第十九章 二项式堆（Binomial Heaps）
第二十章 斐波纳契堆（Fibonacci Heaps）
第二十一章 不相交集的数据结构（Data Structures for Disjoint Sets）
第六部分（Part VI） 图算法（Graph Algorithms）
第二十二章 基本的图算法（Elementary Graph Algorithms）
第二十三章 最小生成树（Minimum Spanning Trees）
第二十四章 单源最短路径（Single-Source Shortest Paths）
第二十五章 所有点对的最短路径（All-Pairs Shortest Paths）
第二十六章 最大流（Maximum Flow）
第七部分（Part VII） 精选的主题（Selected Topics）
第二十七章 排序网络（Sorting Networks）
第二十八章 矩阵运算（Matrix Operations）
第二十九章 线性规划（Linear Programming）
第三十章 多项式与快速傅里叶变换（Polynomials and the FFT）
第三十一章 数论算法（Number-Theoretic Algorithms）
第三十二章 字符串匹配（String Matching）
第三十三章 计算几何学（Computational Geometry）
第三十四章 NP-完备性（NP-Completeness）
第三十五章 近似算法（Approximation Algorithms）
第八部分（Part VIII） 附录：数学背景（Mathematical Background）
附录A 求和（Summations）
附录B 集合，等等。（Sets, Etc.）
附录C 计数与概率（Counting and Probability）
参考文献（Bibliography）
索引（Index）

PS:《麻省理工学院-算法导论》(MIT – Introduction to Algorithms)http://www.verycd.com/topics/87348/，里面有电子书和习题答案和教学视频。

配合这里面的MIT的OPEN COURSE使用更好，只不过我不能很流利地听懂，大学要加强英语口语和听力了，就这样了。

, ,

1 Comment