josephuspermutation.java

来自「<算法导论>第二版大部分算法实现. 1. 各类排序和顺序统计学相关」· Java 代码 · 共 77 行

/*
 * Copyright (C) 2003-2008 Wang Pengcheng <[e-mail]>
 * Permission is granted to copy, distribute and/or modify this
 * document under the terms of the GNU Free Documentation License,
 * Version 2.0 or any later version published by the Free Software Foundation;
 * with no Invariant Sections.
 * You may obtain a copy of the License at
 *   http://www.gnu.org/licenses/lgpl.txt
 */
//12 Mar 2008
package cn.edu.whu.iss.algorithm.unit14;

public class JosephusPermutation {
	private int m,n;
	private DynamicStatisticsTree<Integer> tree;
	
	public JosephusPermutation(int m, int n) {
		super();
		this.m = m;
		this.n = n;
		init();
	}

	public JosephusPermutation() {
		super();
	}

	public String getRes(int m,int n){
		this.m = m;
		this.n = n;
		init();
		return getRes();
	}
	
	private void init(){
		tree = new DynamicStatisticsTree<Integer>();
		for(int i=1;i<=n;i++){
			tree.add(i);
		}
	}
	
	public String getRes(){
		String s = "<";
		int m0 = this.m;
		int m = 1;
		int n = this.n;
		
		while(n>0){
			m+=m0-1;
			if(m%n==0){
				m=n;
			}else{
				m=m%n;
			}
			//System.out.print(m+ " ");
			Integer tar = tree.selectStatisticData(m);
//			if(tar==null){
//				continue;
//			}
			if(n>1){
				s+=tar+",";
			}else{
				s+=tar;
			}
			tree.remove(tar);
			n--;
		}
		return s+">";
	}
	
	@Override
	public String toString() {
		return getRes();
	}

}