`
hao3100590
  • 浏览: 131240 次
  • 性别: Icon_minigender_1
  • 来自: 成都
社区版块
存档分类
最新评论

整数的随机置换

阅读更多

算法描述:生成前N个整数的随机置换,如{4,3,1,5,2},{4,5,3,2,1}是合法的,而{5,4,1,1,2}不合法,因为3没出现。

1.基本算法

该算法效率比较低,O(n*n*logn),主要就是随机的生成一个数,然后再一直数组中去检测是否存在,如果不存在才插入。从而效率低下

 

//使用的是思想1(O(n*n*logn))
int* getRandom(int* a, int length){
		for(int i=0; i<length; i++){
			int j = randInt(0, length);
			//循环,直到找到一个在数组中不存在的值,这里的复杂度是n*logn
			while(true){
				if(findExist(a, i, j)){
					j = randInt(0, length);
				}else{
					break;
				}
			}
			a[i] = j;
		}
		return a;
}

 2.对算法1进行了改进,主要就是增加了一个标志数组,对于已经使用过的数进行了标记,从而不用再遍历原数组,复杂度O(n*logn)降低了不少,但以空间换时间

 

//使用思想2(O(n*logn))
int* getRandom2(int* a, const int length){
		int used[LEN] = {0};
		for(int i=0; i<length; i++){
			int j = randInt(0, length);
			//循环,直到找到一个在数组中不存在的值
			while(used[j]){
				j = randInt(0, length);
			}
			used[j] = 1;
			a[i] = j;
		}
		return a;
}
 

 

3.使用了逆向思维,为什么我们不一次性插入所有数据,然后再随机交换位置,从而达到此效果呢?该算法就是这样,复杂度O(n),线性的

 

//使用思想3(O(n))
int* getRandom3(int* a, const int length){
		int i;
		//初始化0-9
		for(i=0; i<length; i++){
			a[i] = i;
		}
		//任意交换位置,打乱次序
		for(i=0; i<length; i++){
			int temp = a[i];
			int j = randInt(0, i);
			a[i] = a[j];
			a[j] = temp;
		}
		return a;
}

 

 从1-3就是一个算法改进的过程体现,不断的减少时间复杂度,空间消耗,从而实现一个优秀的算法所必须的过程。

 

4.全部代码

 

#include <iostream>
#include <cstdlib>
#include <time.h>//用于做种子
const int LEN = 1000;
using namespace std;

int randInt(int start, int end){
	return start+(end-start)*rand()/(RAND_MAX + 1.0);
}

int findExist(const int* a, int length, int value){
	for(int i=0; i<length; i++){
		if(a[i] == value) return true;
	}
	return false;
}

//使用的是思想1(O(n*n*logn))
int* getRandom(int* a, int length){
		for(int i=0; i<length; i++){
			int j = randInt(0, length);
			//循环,直到找到一个在数组中不存在的值,这里的复杂度是n*logn
			while(true){
				if(findExist(a, i, j)){
					j = randInt(0, length);
				}else{
					break;
				}
			}
			a[i] = j;
		}
		return a;
}


//使用思想2(O(n*logn))
int* getRandom2(int* a, const int length){
		int used[LEN] = {0};
		for(int i=0; i<length; i++){
			int j = randInt(0, length);
			//循环,直到找到一个在数组中不存在的值
			while(used[j]){
				j = randInt(0, length);
			}
			used[j] = 1;
			a[i] = j;
		}
		return a;
}

//使用思想3(O(n))
int* getRandom3(int* a, const int length){
		int i;
		//初始化0-9
		for(i=0; i<length; i++){
			a[i] = i;
		}
		//任意交换位置,打乱次序
		for(i=0; i<length; i++){
			int temp = a[i];
			int j = randInt(0, i);
			a[i] = a[j];
			a[j] = temp;
		}
		return a;
}


int main(){
//	srand(unsigned(time(0)));//,随机数种子,使用这个就可以每次不同
	int a[LEN] = {0};
	srand(time(NULL));
//	int *b = getRandom(a, LEN);
//	int *b = getRandom2(a, LEN);
	int *b = getRandom3(a, LEN);
	for(int i=0; i<LEN; i++){
		cout<<b[i]<<" ";
	}
	return 0;	
}
 

 

0
0
分享到:
评论

相关推荐

    随机矩阵置换【VB】

    **随机置换**是指在一组元素中随机地改变元素的位置,通常用于增加算法的不可预测性和安全性。 **随机矩阵置换**则是在矩阵中随机交换元素的位置。例如,可以将一个矩阵的任意两行或两列进行交换,从而达到随机化的...

    页面置换算法实验报告.docx

    例如,最佳置换和随机置换使用整数数组,FIFO和LRU使用队列,而CLOCK算法及其改进版使用循环队列。所有算法都用整数数组来模拟页面访问序列。 数据结构设计部分,包括了存储页面访问序列的数组、模拟内存的数组,...

    页面置换算法实验报告 (2).pdf

    在实现各种算法时,采用了不同的数据结构以体现每种算法的特点:最佳置换和随机置换使用整数数组模拟内存;FIFO和LRU利用队列;而Clock算法及其改进版则采用循环队列。 数据结构设计部分,包括了页面访问序列数组、...

    页面置换算法实验报告.pdf

    最佳置换和随机置换算法用整数数组来模拟内存;FIFO和LRU利用队列结构;Clock置换及其改进版则利用循环队列。页面访问序列同样用整数数组表示。 数据结构设计包括了页面访问序列数组、内存数组,以及队列和链表的...

    基于Java实现的(GUI)页面置换算法模拟系统【100012888】

    产生随机序列功能:​ 随机生成 1-128 之间的整数,作为指令序列号,同时将随机生成的数字除以 10 取余作为该指令的页地址,随机数的生成以当前时钟做种子,保证每次生成的随机性。 算法运行功能:1、根据先进先出...

    页面置换算法实验.doc

    随机置换算法是最简单的策略,每次随机选择一个页面进行淘汰,无需预测未来访问。 3. **先进先出置换算法(First-In-First-Out, FIFO)**: FIFO算法按照页面进入内存的顺序进行淘汰,即最早进入内存的页面最先被...

    伪随机数发生器

    ### 伪随机数发生器详解 #### 一、概述 伪随机数发生器(Pseudo-Random Number Generator, PRNG)是一种能够生成一系列看似随机但实际上是由确定性算法产生的数字序列的程序或硬件设备。这些数字虽然不是真正的...

    页面置换算法模拟程序—操作系统课程设计

    `: 生成1到10之间的随机整数。 #### 完整代码 虽然题目提供了部分代码片段,但这里提供一个更为完整的概念框架: - **输入页面走向长度**: - 接受用户输入的实际页面走向长度(15≤L≤20)。 - 通过随机数生成器...

    古典加密算法之置换密码和代换密码-羽灵光Fealight

    在实际应用中,现代密码学结合了置换和代换的概念,并引入了公钥密码体制、哈希函数、伪随机数生成器等技术,极大地提高了加密的安全性和效率。 在提供的文件"古典加密算法.txt"中,可能会详细介绍这两种加密方法的...

    密码实验程序(具体的)

    - 输入一个大于15的整数`m`。 - 使用`srand(time(NULL))`初始化随机种子,确保每次运行程序时都能得到不同的结果。 - 随机生成一个介于0到15之间的数字,放入数组中,并检查该数字是否已存在于数组中。如果存在,...

    sam_test.rar_aes伪随机数_rsa_sam_sam模块_伪随机数测试

    AES的核心是基于替换和置换的迭代过程,具有较高的安全性与效率。 其次,RSA是一种非对称加密算法,由Ron Rivest、Adi Shamir和Leonard Adleman三位科学家在1977年提出。RSA的原理基于大整数因子分解的困难性,它...

    页面置换算法 fifo opt lru

    - `int Input(Pro p[])` 函数用于输入页面序列,支持自动随机生成或手动输入。 3. **核心函数**: - `void print(Pro pa[])` 函数用于打印当前内存中的页面状态。 - `int Search(int e, Pro pa[])` 函数用于搜索...

    randpermmat (N, M):随机排列矩阵-matlab开发

    randpermmat-随机置换矩阵A = randpermmat(N) 返回一个方阵,其中每一行和每一列保存整数 1:N 的排列。 这也称为随机拉丁广场,每个整数在每一行和每一行中恰好出现一次柱子。 A = randpermmat(N, M) 返回一个 N×M ...

    matlab开发-大序列的算法seudor和compermutation

    总的来说,MATLAB中的大序列算法涉及高效地处理大量数据,`createRandomPermutation`函数可能是一个自定义实现,用于生成随机置换,这在模拟和实验设计中有广泛的应用。而"Compermutation"可能是作者提出的一个特定...

    非线性整数规划的遗传算法Matlab程序.pdf

    其中,交叉操作是通过双亲双子单点交叉来实现的,变异操作是通过随机置换来实现的。最后,通过选择操作来保留最优个体。 在 Matlab 中,我们可以使用以下代码来实现遗传算法: ```matlab function [Xp,LC1,LC2,LC3...

    双序置换的最长递增子列 (2014年)

    研究者崔汉哲通过将双序置换与杨氏表建立对应关系,并运用杨氏表的计数方法,给出了随机双序置换中最长递增子列长度的分布,并计算了其期望与方差。这为理解和描述随机双序置换的统计特性提供了重要的工具。此外,...

    一种基于整数变换DC分量的自适应视频水印算法

    水印嵌入之前进行随机置换与LDPC编码增强了水印抗攻击能力。实验结果表明,该算法能够保证很好的视频质量,视频帧的PSNR值高于50dB,并实现了水印的盲提取。对于常见的视频攻击有较强的鲁棒性,特别是在多种格式压缩的...

    通过子域值多项式构造有限域上的置换和完全置换

    对于一个素数p和正整数n,可以通过添加p的n次根的方式构造出一个有限域F-pn,它包含p^n个元素。 - 置换多项式(Permutation Polynomial):如果一个多项式f(x)在有限域F-pn上的作用是一个一一对应的映射,即对于F-pn...

    permutation-iterator-rs:用于迭代随机排列的Rust库

    这是如何遍历[0, max)范围内的整数的随机排列,即从0包含到max不包含。 每次运行此命令,您都会得到不同的排列。 use permutation_iterator :: Permutor; fn main () { let max = 10 ; let permutor = Permutor ...

Global site tag (gtag.js) - Google Analytics