Problem 14-2 Josephus permutation

This problem is taken from the book Introduction to Algorithms, Third Edition By Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein:

We define the Josephus problem as follows. Suppose that n people form a circle and that we are given a positive integer m <= n. Beginning with a designated first person, we proceed around the circle, removing every mth person. After each person is removed, counting continues around the circle that remains. This process continues until we have removed all n people. The order in which the people are removed from the circle defines the (n, m)-Josephus permutation of the integers 1,2,...,n. For example, the (7, 3)-Josephus permutation is (3,6,2,7,5,1,4)

a) Suppose that m is a constant. Describe an O(n)-time algorithm that, given integer n, outputs the (n, m)-Josephus permutation.

b) Suppose that m is not a constant. Describe an O(nlg(n))-time algorithm that, given integers n and m, outputs the (n, m)-Josephus permutation.

Answer

a) A simple solution would be using a linked list and delete the mth element until is empty. This runs in $\Theta (nm+n) = \Theta (n).$

b) We used an augmented tree for getting the rank of any element in $\Theta \left(lg\right(n\left)\right)$, but instead of implementing a balance tree we build the tree given a range from 1 to n in  $\Theta \left(n\right)$. So it runs in $\Theta (n lg(n)+n) = \Theta (n lg(n\left)\right)$.

Code of part b) in rust: 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113

extern crate itertools; use itertools::Unfold; use std::cmp::Ordering; pub fn permutation(size: u32, m: u32) -> Box<Iterator<Item = u32>> { let mut tree = Tree::new(1, size); let x = Unfold::new(1, move |a| { *a = (*a + m - 2) % tree.size + 1; Some(tree.pop_rank(*a)) }); Box::new(x.take(size as usize)) } #[derive(Debug)] struct Node { data: u32, left: Tree, right: Tree, } #[derive(Debug)] struct Tree { size: u32, root: Option<Box<Node>>, } impl Tree { fn new(from: u32, to: u32) -> Tree { if from > to { return Tree { root: None, size: 0, }; } let mid = from + (to - from) / 2; let node = Node { data: mid, left: Tree::new(from, mid - 1), right: Tree::new(mid + 1, to), }; Tree { size: 1 + node.left.size + node.right.size, root: Some(Box::new(node)), } } fn find_rank(&mut self, rank: u32) -> &mut Tree { let r = self.root .as_mut() .expect("rank out of range") .left .size + 1; self.size -= 1; match rank.cmp(&r) { Ordering::Equal => self, Ordering::Less => self.as_mut().left.find_rank(rank), Ordering::Greater => self.as_mut().right.find_rank(rank - r), } } fn as_mut(&mut self) -> &mut Box<Node> { self.root.as_mut().unwrap() } fn as_ref(&self) -> &Box<Node> { self.root.as_ref().unwrap() } fn empty(&self) -> bool { self.root.is_none() } fn delete_node(&mut self) { *self = self.root .take() .map(|mut x| { if x.left.empty() { x.right } else if x.right.empty() { x.left } else { x.data = x.right.pop_min(); Tree { root: Some(x), size: self.size, } } }) .expect("Can't delete None"); } fn pop_min(&mut self) -> u32 { if self.empty() { panic!("underflow"); } if self.as_ref().left.empty() { let data = self.as_ref().data; *self = self.root.take().unwrap().right; data } else { self.size -= 1; self.as_mut().left.pop_min() } } fn pop_rank(&mut self, rank: u32) -> u32 { let ranked = self.find_rank(rank); let data = ranked.as_ref().data; ranked.delete_node(); data } }