关于排列集p（n,r）的几种有效算法

本文在按字典排序的前提下，给出了生成排列集ｐ（ｎ，ｒ）的枚举算法，为建立ｐ（ｎ，ｒ）与它的反相集合的映射及逆映射，提供了一对编解码算法；在此编解码算法的基础上，为建立ｐ（ｎ，ｒ）与ｚ＝｛１，２，…，│ｐ（ｎ，ｒ）│｝之间的一一映射关系，还给出了相应的排序和逆排序算法。实际上，我们给出的这些算法，与已知的算法相比，更具有普遍性和优越性。     

全排列的算法及程序设计

全排列是从N个元素中取出全部相异元素的排列,而且每一种排列不重复,不遗漏。全排列广泛地应用在各种复杂的软件中,尽管数学概念简单,但程序实现并不容易。全排列包含着多种形式的数据结构,隐藏着特别引人的趣味。全排列的算法通常分成三种类型：串行类、并行类和递归类。在n个元素组成的所有排列中,必有一个最小的排列;所有的排列根据字典顺序,按由小到大构成一个队列,任意一个排列都有唯一的后继（只有最大的排列除外）。作者经过反复调试,编制了全排列的6种算法。算法短小精悍,代码紧凑,给读者提供一个全排列算法设计的借鉴…     

常见全排列生成算法简介

全排列在程序设计中有着广泛的应用，本文简单地介绍了常见的几种全排列生成算法。     

余数法无表查询排列方式算法的研究与实现

文章的研究目的是用一种无表查询排列方式的算法解决编程计算中经常遇到的随机排序问题.算法的实现用到了余数法原理和递归算法,文中给出了C语言的函数实现.文中用到了全排列的思想,但研究的目的不是全排列.文章认为全排列是一个有序的集合,每一种排列方式都有其对应的序号,算法在没有建立实际序列集的情况下,实现根据序号查询排列方式,...     

一种基于排列融合的归纳式半监督排序方法

排序学习,即用有标记的训练集通过机器学习的方法学习一个排序函数,并对测试集的数据进行排序的技术.当前的文档排序学习算法主要是基于全监督排序学习的框架,它需要大量已标记的文档,而通过人工给文档赋予标记(完美、优秀、好、一般、差)是非常费力费时的.因此这里提出一种基于排列融合的归纳(inductive)式半监督排序算法.首...     

一个附带排列奇偶性的排列生成算法

自然数1，2，……，n的n级排列在数学中有广泛的应用。随着计算机的广泛应用，许多组合问题的计算机算法中要求产生所有的n级排列。但是，附带排列奇偶性的排列生成算法并不多见。本文采用给每一个n级排列编码的方法，利用集合映射，获得一个同时给出排列奇偶性的排列生成算法，并通过编码，对每一个排列得到一个序号。本文中的算法可望在优化问题的计算机算法中得到应用。     

排列约束条件下的快速生成算法

所述的约束排列是指：棚个非负整数所构成的排列a1a2…am，满足约束条件a1≤N1，a2≤N2…．8m≤NM及a1＋a2＋…am=M，其中M和M1M2…Nm是给定的正整数。在此解决对于给定的一个约束排列a1a2……am，按照字典排序给出下一个约束排列的生成算法，并对查找位置的确定给出新思路。     

变换存储结构的一种高效排序算法

给出变换存储结构的一种高效排序算法 ,该算法的时间复杂度为 O(n) ,且与待排序数据的分布无关 .给出了该排序算法的描述 ,并在时间复杂度和空间复杂度两方面与其他排序算法作了比较     

一种基于结构化学习的排序算法

传统排序算法将排序问题转换成分类或回归问题来求解,这样得到的模型不够精确。对此提出一种新的排序算法,该算法把排序问题看成一个结构化学习过程,即通过训练集来学习一个排序结构。算法首先定义了一个查询级的目标函数,针对算法约束条件太多,难以直接优化,提出使用割平面算法进行求解。对于算法中的“寻找最违约排列”子问题,将其变换成为一个简单的降序排列问题。基于基准数据集的实验表明,相比起传统的排序算法,所提算法更为有效。     

适应文档检索的半监督多样本排序学习算法

针对标记训练集不足的问题,提出了一种协同训练的多样本排序学习算法,从无标签数据挖掘隐含的排序信息。算法使用了两类多样本排序学习机,从当前已有的标记数据集分别构造两个不同的排序函数。相应地,每一个无标签查询都有两个不同的文档排列,由似然损失来计算这两个排列的相似性,为那些文档排列相似度低的查询贴上标签,使两个多样本排序学习机新增了训练数据。在排序学习公开数据集LETOR上的实验结果证实,协同训练的排序算法很有效。另外,还讨论了标注比例对算法的影响。     

求解多目标最小生成树的一种新的遗传算法

在改进的非支配排序遗传算法（NSGA-II）的基础上,提出了一种新的基于生成树边集合编码的繁殖算子求解多目标最小生成树问题的遗传算法。通过快速非支配排序法,降低了算法的计算复杂度,引入保存精英策略,扩大采样空间。实验结果表明：对于多目标最小生成树问题,边集合编码具有较好的遗传性和局部性,而且基于此繁殖算子的遗传算法在求解效率和解的质量方面都优于基于PrimRST的遗传算法。     

一种快速的双目标非支配排序算法

提出一种快速的双目标非支配排序算法(BNSA)。设计了前向比较操作,以便快速识别非支配个体。提出了按需排序策略,避免生成多余的非支配前沿。论证BNSA算法的正确性,分析其时间复杂度为O(NlogN)。在9个标准的双目标优化测试问题上进行了比较实验。实验结果表明与其它3种非支配排序算法相比,BNSA算法在大多数测试问题上具有更快速的性能。当进化代数超过400代时,BNSA在所有的测试问题上都具有最好的加速效果。此外,BNSA算法简明、易于编程实现,可集成到任何基于非支配排序的多目标进化算法中,能较大程度地提高双目标优化的运行速度。     

浅析递归问题和它的三个应用

递归是一种重要的算法设计方法。经过对递归进行研究,给出递归的定义和它在二叉树、搜索和排序中的应用,并利用C#语言编程实现相应的算法。     

新的等价类生成算法—生成支法*

目前,基于排序的等价类生成算法存在以下不足:排序后仍需高达 O（|B| |U|）的时间复杂度重复进行 运算才求得等价类,为此,设计了一种新算法。新算法采用孩子兄弟表示法,将生成等价类的过程定义为一棵二 叉树,主要采取了边生成节点边访问,一旦求得某个等价类便释放相应分支节点空间的方法。其时间复杂度为 O（|C| |U|）,空间复杂度为O（|U|）,为求等价类提供了一个新的解决办法。     

An efficient non-dominated sorting method for evolutionary algorithms

We present a new non-dominated sorting algorithm to generate the non-dominated fronts in multi-objective optimization with evolutionary algorithms, particularly the NSGA-II. The non-dominated sorting algorithm used by NSGA-II has a time complexity of O(MN(2)) in generating non-dominated fronts in one generation (iteration) for a population size N and M objective functions. Since generating non-dominated fronts takes the majority of total computational time (excluding the cost of fitness evaluations) of NSGA-II, making this algorithm faster will significantly improve the overall efficiency of NSGA-II and other genetic algorithms using non-dominated sorting. The new non-dominated sorting algorithm proposed in this study reduces the number of redundant comparisons existing in the algorithm of NSGA-II by recording the dominance information among solutions from their first comparisons. By utilizing a new data structure called the dominance tree and the divide-and-conquer mechanism, the new algorithm is faster than NSGA-II for different numbers of objective functions. Although the number of solution comparisons by the proposed algorithm is close to that of NSGA-II when the number of objectives becomes large, the total computational time shows that the proposed algorithm still has better efficiency because of the adoption of the dominance tree structure and the divide-and-conquer mechanism.     

利用堆实现优先队列

利用堆实现的优先队列实质是一棵顺序存储的二叉树。所以具有很好的时间、空间性能。比传统的优先队列具有更广泛的应用前景。可在计算机的各种排队算法中推广应用。     

如何提高编程效率

本文主要通过slit算法的功能模块划分，在实现该运算中特别注意内存空间的分配与排序算法的选择，通过分析排序算法的优劣来选择适当的排序算法。文章最后总结该过程，得到如何提高编程效率的心得。     

A more efficient algorithm for perfect sorting by reversals

We describe a new algorithm for the problem of perfect sorting a signed permutation by reversals. The worst-case time complexity of this algorithm is parameterized by the maximum prime degree d of the strong interval tree, i.e., f(d).nO(1). This improves the best known algorithm which complexity was based on a parameter always larger than or equal to d.     

Parallel sorting on cayley graphs

This paper presents a parallel algorithm for sorting on any graph with a Hamiltonian path and 1-factorization. For ann-cube the algorithm is equivalent to the sequential balanced sorting network of Dowd, Perl, Rudolph, and Saks. The application of this algorithm to other networks is discussed.     

不改变数据位置的排序算法及动态演示

实际应用中经常遇到要求不改变原始数据的顺序而按关键字的大小对数据进行排序的情况,原有的一些经典排序算法不能直接用于解决该类问题。经过对选择排序算法进行研究,给出基于选择思想的不改变数据位置而对数据进行排序的算法,并利用C#语言编程对该算法的实现过程进行动态演示。