算法导论思考题14-2 Josephus permutation 约瑟夫排列

约瑟夫问题的定义：假设n个人排成环形，且有一个正整数 m <= n。从某个指定的开始，沿环报数，每遇到第m个人

就让其出列，且报数进行下去。这个过程一直进行到所有人都出列为止。每个人出列的次序定义了整数0,1,2，...n-1

的(n, m)-约瑟夫排列。例如(7, 3)约瑟夫排列为<2，5，1，6，4，0，3>。

原始办法是非常直观的O（mn）算法。

分析约瑟夫排列问题，

首先可以坑定约瑟夫环的运算时间绝对大于等于O（n），这点毫无疑问。

还有就是数据大小与约瑟夫序列毫无关系。

只有序列的下标位置与约瑟夫排列有关。

一个约瑟夫排列的产生取决于两个量，一个是总数n，另一个是m，也就是每次跳跃的数量。开始是第一个人m号出列，然后是2m号，但是约瑟夫排列还存在循环问题。

继续看O（n）这个时间，这真的是约瑟夫排列的下线吗？是否存在一个约瑟夫排列他的运行时间是O（n）？

回答是：存在，当m  = 1时，获得约瑟夫排列的时间是O(n)。

在看看约瑟夫环是否有最坏时间呢？

加入m = n，会发生什么事情呢？这样的情况下，没有具体的数据结构和算法是不能预估其计算时间的。

为了获得约瑟夫环，我目前只知道m和n能决定约瑟夫排列。对于每一个数据来说，它出现在最终排列的位置在[1,n]之间，这个最终排列的位置取决于什么呢？

可能的有：

1.这个数据的索引位置i

2.总数据量n

3.跳过间歇m

这三个量是影响这个数据在最终序列的位置的可能的关键变量。

仔细看也不全是这样。

如果当m = 1的时候，总数据量n并不会影响第i个数据出现在最终约瑟夫序列中的位置。

还有当i%m = 0 的时候，同样n也不会影响第i个数据出现在最终序列的位置。

这个例子可以看出，i，m，n之间的关系绝对是分情况的，这种情况可能是常量种情况或者随着n和m的变化而变化的情况数量。

变量种情况是不利于实现的。

实现这样一个约瑟夫序列生成的问题目前有以下几个：

1.如何快速实现从第i个输出的节点到第i+1个输出节点的查找？

换句话说就是如何在已经输出了i个节点的情况下，怎么快速判定，第i+1个输出节点。也就是和第i个输出的节点间隔m的那个节点。

问题可以稍微化简一点。

如果知道当前的节点总数n，和上一个输出节点x（其在n中的下标为x-index），那么我要知道下一个输出的数据是x后面第m个数。从全局来看就是从一开始第

（x-index + m）%n个数，输出之后n自减。换句话说我现在只需要每次求第（x-index + m)%n个数即可。从每次循环的过程来看。

假设一开始有n0个元素。

那么第一个输出的数据的下标为 x-index0 = m

第二个输出的数据在n0-1个元素中的位置为 x-index1 = （x-index0 + m - 1）%（n0-1）

第三个输出的数据在n0-2个元素中的位置为 x-index2 = （x-index1 + m - 1）%（n0-2）

。。。。。。

为了查找地x-index个位置的元素数据，

最快可以O（1）的时间，结合数组的数据结构，但是不便于维护。因为数组的元素下标固定，并且在上面每一次递归过程中都可能会发生改变，所以单纯的数组是不便利的。

由于这样的原因则只能抛弃使用下标来索引数据。但是为了快速获得第x-index个数据，除了下标直接索引之外就是使用二分法以O（logn）来查找这个数据。使用二分法的基本条件是需要有顺序关系，这一点上有很多数据结构都满足条件。

现在已经获得两个数据结构的有关特性了。

1.不能直接使用下标，这意味着数据可能是动态分配的。（因为静态分配大多都是连续空间）

2.需要保持数据之间的先后关系，以便于二分查找。

而且每次递归的过程中数据规模都会减1，也就是会删除掉第一个数据，不在放入下一次递归中去。

所以条件3是：

3.能够快速删除的数据结构。

还有最重要的是能够快速索引到第i个数。

4.能够快速索引的数据结构。

有了这几个相关信息，明显在说红黑树，不过也是存在别的方案的。由于无法使用O（1）的索引方式获取数据，只能使用二分查找来获取。那么二分法时间就是O（logn），对于n个数据来说总时间至少是n*O(logn) = O(nlogn)的最低时间，因为还要考虑删除的时间，如果删除的时间无法在O（logn）内完成从n个数据中去除当前搜索到的节点的话就无法达到O（nlogn）的时间。

这里实际存在很多的方法来做，下面列举2个方案。

方案1：使用红黑树,以下标为红黑树比较值一个个节点添加进红黑树中去，并在红黑树每个节点中记录子树节点数量。时间O（nlogn），然后按照公式查找第x-index个节点并输出然后删除这个节点，总共耗时O（nlogn） + O（nlogn） = O（nlogn）。

方案2：使用一个数组记录n个元素，然后为这个数组添加一个搜索树，数组不断二分，每次二分生成一个树节点，结点中记录子树叶节点数量，最后保证每一个数据都是等深度的处在叶节点。然后再利用上面的递归公式依次查找并删除每个数据获得约瑟夫序列。这样一个过程分为建树和查找两部分，时间为O（n） + O（nlogn）。由于其节点的平均深度很可能大于方案1中的红黑树深度，而且随着删除过程的进行节点平均深度不变，而红黑树节点平均深度不断减小。所以在查找和删除部分，红黑树应占据优势。但在构建搜索树的过程中，红黑树速度弱于方案2.

方案3：使用普通搜索树来进行，具体做法为建树的过程类似方案2，每次取中间点作为子树根节点，直到所有节点都进入树中。这种方法保证了树的最大深度和平均深度，虽然删除过程会逐渐变得不平衡，但是由于其本身简单的实现过程加上最大深度的保证，一旦建树后就不会在添加节点，构建树速度也是O（n）而查找和删除的速度由于最大深度的保证同样也是O（nlogn）。相当于方案2的改进办法，相对于方案2，提升了一定的速度（具有更小的平均深度），同时也保证了编码的简单性。

方案4：可以为红黑树尝试添加一种O（n）直接建树的办法，这种方法是否能够实现还是个问题，最大的难点在于怎么保证红黑树的黑高一致这个问题，不过换个角度来考虑，红黑树保证黑高一致的根本目的在于保证叶节点的搜索深度保持在一定的最大值和最小值，但在本例中可以忽略这点，因为二分数组而产生的搜索树本身平衡度也十分好。并且有一个固定下限，下面给出证明：

二分法在最糟糕的情况下就是每次二分时候数组总数都是偶数。具体举出例子就是

最后一次二分是两个节点

以li表示二分后左边的结点数量，rj表示右边的结点数量，

最后一次二分l0 = 1，r0 = 1；

倒数第二次二分l1 = 1，r1 = 2；

倒数第三次二分l2 = 2，r2 = 3；

      l3 = 4，r3 = 5；

从这个规律看最糟糕的情况就是每次二分都使得两边的数据量差距为1的时候情况最糟。知道这个条件之后。

当总数为n个节点是，且 2^k - 1<=n <= 2^(k+1) - 1时候，证明二分查找n中的存在的节点最大搜索深度为k+1 .

使用数学归纳法，当k = 1 的时候， 1<= n<=3的时候，可以看见二分查找的最大搜索深度为1.

假设当2^k - 1<=n <= 2^(k+1) - 1时候最大搜索深度为k+1。那么对于

2^(k+1) - 1 <= n <= 2^(k+2) - 1的时候最大搜索深度D（n） =1　＋　max（D（lhs），D（rhs）)其中lhs + rhs = n - 1,且有0<=rhs-lhs<=1

这时候 lhs和rhs 有性质  2^(k) - 1 <=max（lhs，rhs）<=2^(k+1) - 1.那么max（D（max（lhs，rhs）） <=k+1，孤儿D（n）<=k+2.命题的证。

由于二分法的搜索特性，这样建树的过程同意也有最大高度k+1，其中2^k - 1<=n <= 2^(k+1) - 1。

这比红黑树的最差情况要好，而在上色的时候选择所有节点涂成黑色就行，这里不去保证红黑树的黑高一致，因为这样构建的红黑树本身平衡性要好于一个个节点插入的过程。原因在于最大搜索深度为k+1，也就是log（n+1） - 1 向上取整，对于最小深度类似的有mD（n） = 1 + min（D（lhs），D（rhs））从而再次得到最小深度k，这比起红黑树的最大2*logn的树深要平衡的多。红黑树的删除过程在于保持每一个分支直接黑高一致，由于一开始根叶路径上的黑高一致，而每次删除都维护这一点，所以使用红黑树的删除办法要好于原始删除办法。

也可以这样理解，最快的二分搜素办法永远是每次比较都能缩小整个规模的一半，而这点红黑树做不到。但这种建树方法在一开始建树之后能做到，因为它就是用这样的方法建树的。所以红黑树一开始的搜索性能绝对不如这里的做法。

方案4是对方案1，2，3的改进和结合，把它们的优点集中。

最终采用方案4编码，下面是代码：

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <malloc.h>
#include <math.h>
#include <time.h>
#define BLACK 1
#define RED   0
#define RBT_NODE RBT
//#define ROOT(T) (T->left)

typedef struct node{
	struct node *left;
	struct node *right;
	struct node *parent;
	int color;
	int data;
	//int information;
	int size;
} *RBT;
#define RBTREE_INIT(name) {name,0, 0,BLACK,0,0}

int node_hight(RBT T,RBT_NODE x)
{
	int re = 0;
	while(x!=T){
		x = x->parent;
		re++;
	}
	return re;
}
int all_hight(RBT T,RBT_NODE x)
{
	if(x==T){
		return 0;
	}
	int a,b,c;
	a = all_hight(T,x->left);
	b = node_hight(T,x);
	c = all_hight(T,x->right);

	return a+b+c;
}
void left_rotate(RBT T,RBT_NODE x)
{

	struct node * y = x->right;
	if(y == T) return ;
	x->right = y->left;

	int temp = y->size;
	y->size = x->size;
	x->size-=temp;

	if(y->left != T){
		y->left->parent = x;
		x->size += y->left->size;
	}
	y->left = x;
	y->parent = x->parent;
	 if(x == y->parent->left){
		y->parent->left = y;
	}else{
		y->parent->right = y;
	}
	x->parent = y;
}
void right_rotate(RBT T,RBT_NODE x)
{
	struct node *y = x->left;
	if(y == T) return ;

	int temp = y->size;
	y->size = x->size;
	x->size -= temp;

	x->left = y->right;
	if(x->left != T){
		x->size += x->left->size;
		x->left->parent = x;
	}
	y->right = x;
	y->parent = x->parent;
	if(x->parent->left == x){
		x->parent->left = y;
	}else{
		x->parent->right = y;
	}
	x->parent = y;
}


void rb_transplant(RBT T,RBT_NODE u,RBT_NODE v)
{
	if(u==u->parent->left){
		u->parent->left = v;
	}else u->parent->right = v;
	v->parent = u->parent;
	if(v != T)
		v->size = u->size;
}
RBT_NODE tree_minimum(RBT T,RBT_NODE x)
{
	RBT_NODE p = x;
	while(p->left != T){
		p = p->left;
	}
	return p;
}



void rb_delete_fixup(RBT T,RBT_NODE x)
{
	RBT_NODE w;
	while( x != T->left && x->color == BLACK)
	{
		if( x == x->parent->left)
		{
			w = x->parent->right;
			if(w->size < x->size){
				break ;
			}
			if(w->color == RED){
				w->color = BLACK;
			//	if(x->parent->color!=BLACK){
			//		puts("x == x->parent->left x->parent->color!=BLACK");
			//	}
				x->parent->color = RED;
				left_rotate(T,x->parent);
				w = x->parent->right;
			}
			if(w == T){
				right_rotate(T,x->parent);
				break ;
			}
			if(w->left->color == BLACK && w->right->color ==BLACK)
			{
				w->color = RED;
				x = x->parent;
			}else {
				if(w->right->color == BLACK){
					//if(w->right == T){
					//	puts("this should not happend w->right == T 1");
					//}
			//		if(w->left->color != RED){
			//			puts("condition 3 error,w->left->color != RED 1");
			//		}
					w->left->color = BLACK;
					w->color = RED;
					right_rotate(T,w);
					w = x->parent->right;
				}
			//	if(w->right->color!=RED){
			//		puts("error in condition 4 w->right->color!=RED 1");
			//	}
				w->color = x->parent->color;
				x->parent->color = BLACK;
				w->right->color = BLACK;
				left_rotate(T,x->parent);
				x = T->left;
			}	
		}else{
			w = x->parent->left;
		//	if(w == T)
		//		puts("disaster 2");
			if(w->size < x->size){
				break ;
			}
			if(w->color == RED)
			{
				w->color = BLACK;
		//		if(x->parent->color!=BLACK){
		//			puts("x == x->parent->right x->parent->color!=BLACK");
		//		}
				x->parent->color =RED;
				right_rotate(T,x->parent);
				w = x->parent->left;
			}
			if(w == T){
				left_rotate(T,x->parent);
				break ;
			}
			if(w->left->color == BLACK&&w->right->color == BLACK){
				//x->parent->color = BLACK;
				w->color = RED;
				x = x->parent;
			}else{
				if(w->left->color == BLACK){
					//if(w->left == T){
					//	puts("this should not happend w->right == T 3");
					//}
		//			if(w->right->color != RED){
		//				puts("condition 3 error,w->left->color != RED 1");
		//			}
					w->right->color = BLACK;
					w->color = RED;
					left_rotate(T,w);
					w = x->parent->left;
				}
		//		if(w->left->color!=RED){
		//			puts("error in condition 4 w->right->color!=RED 2");
		//		}
				w->color = x->parent->color;
				x->parent->color = BLACK;
				w->left->color = BLACK;
				right_rotate(T,x->parent);
				x = T->left;
			}
		}
	}
	T->left->color = BLACK;
	x->color = BLACK;
}
void rb_delete(RBT T,RBT_NODE z)
{
	if(z == T){
		puts("cann't delete the tree");
	}

	RBT_NODE y =z;
	y = z;
	RBT_NODE x;
	int y_original_color = y->color;

	if(z->left == T)
	{
		x = z->right;
		rb_transplant(T,z,x);
	}else if(z->right == T)
	{
		x = z->left;
		rb_transplant(T,z,x);
	}else{
		y = tree_minimum(T,z->right);
		y_original_color = y->color;
		x = y->right;

		if(y->parent == z){
			x->parent =y;
			if(x!=T)
				x->size = y->size;
		}
		else{
			rb_transplant(T,y,y->right);
			y->right = z->right;
			y->right->parent = y;
		}
		rb_transplant(T,z,y);
		y->left = z->left;
		y->left->parent = y;
		y->color = z->color;
	}
	y = x;
	if(y!=T) y->size--;
	while(y->parent != T){
		y->parent->size --;
		y = y->parent;
	}
	if(y_original_color == BLACK){
		rb_delete_fixup(T,x);
	}
}

int mmax(int a,int b)
{
	return a > b? a:b;
}
void rb_build_tree(RBT_NODE T,RBT_NODE p,int direct,RBT_NODE *in,int size)
{
	if(size>0){
		int mid = (size-1)>>1;
		if(direct == -1)
			p->left = in[mid];
		else 
			p->right = in[mid];
		in[mid]->parent = p;
		in[mid]->color = BLACK;
		in[mid]->size = size;
		int lhs = mid;
		int rhs = size - mid - 1;
		rb_build_tree(T,in[mid],-1,in,lhs);
		rb_build_tree(T,in[mid],1,&in[mid+1],rhs);
	}else{
		if(direct == -1){
			p->left = T;
		}else{
			p->right = T;
		}
	}
}
int extract_elem(RBT_NODE T,int index)
{
	if(T->left == T)
		printf("error in extract_elem %d\n",index);
	RBT_NODE y = T->left;
	/*

	*/
	while(y->left->size != index )
	{
		if(y == T||index < 0)
		{
			printf("error in extract_elem1 %d\n",index);
			return 0;
		}
		if(index < y->left->size)
		{
			y = y->left;
		}
		else{
			index = index - 1 - y->left->size;
			y = y->right;
		}
	}
	rb_delete(T,y);
	return y->data;
}
struct LL{
	int data;
	struct LL *next;
};
void Josephus_Permunation_check(int size,int m,int *out)
{
	struct LL vec[size] ;//= (int*)malloc(sizeof(int)*size);
	for(int i = 0;i<size;i++){
		vec[i].next = &vec[(i+1)%size];
		vec[i].data = i;
	}
	struct LL *linklist = &vec[size - 1];
	for(int i = 0;i<size;i++)
	{
		for(int j = 0;j<m-1;j++)
			linklist = linklist->next;
		out[i] = linklist->next->data;
		linklist->next = linklist->next->next;
	}
}
void print(RBT T,RBT_NODE N)
{ 
	if(N != T){
		printf("data = %d size = %d ",N->data,N->size);
		if(N->left!=T)
			printf("N->left->data = %d ", N->left->data);
		if(N->right!=T)
			printf("N->right->data = %d ", N->right->data);
		puts("");
		print(T,N->left);
		print(T,N->right);
	}
}
void Josephus_Permunation(RBT_NODE T,int m,int *re,int n)
{
	int index = (m-1)%n ;
	int i = 0;
	while(T->left!=T)
	{

		//print(T,T->left);
		int avl_height = all_hight(T,T->left);
		printf("allnum = %d avl_height = %d  logn + 1 = %f \n",n,avl_height/n,(int)1 + (double)log(n)/log(2));
		re[i++] = extract_elem(T,index);	
		//printf("m = %d index = %d re[i = %d] = %d\n",m,index,i,re[i-1]);
		if(n > 1)
			index = (index + m - 1) % --n;
		else
			index = 0;
	}
}
#define MAX  100000
int main()
{
	struct node tree = RBTREE_INIT(&tree);
	RBT_NODE T = &tree;
	RBT_NODE in[MAX];
	srand((unsigned)time(0));
	for(int i = 0;i<MAX;i++){
		in[i] = (RBT_NODE)malloc(sizeof(struct node));
		in[i]->data = i;
	}
	rb_build_tree(T,T,-1,in,MAX);
	//print(T,T->left);
	int re[MAX];
	int re1[MAX];
	int m =rand()%MAX;
	while(m==0){
		 m = rand() % MAX;
	}
	printf("m = %d\n",m);
	Josephus_Permunation(T,10000,re,MAX);
	//Josephus_Permunation_check(MAX,10000,re1);
	for(int i = 0;i<MAX;i++){
		if(re[i]!=re1[i]){
			puts("error");
			break;
		}
	}
	puts("success");
}
           

经过多个节点的实验，发现平均搜索深度一直都保持在log（n）+ 1之下，也就是保障了平均深度要低于正常情况下的完全二叉树的最大深度。这相对于方案一而言是有优势的，因为插入生成的红黑树最大深度可能为2*log（n），最大深度可能约是平均深度的一倍。