// codesnip-guard: combinations
#[cfg_attr(any(),rustfmt::skip)]pub use self::combinations::SliceCombinationsExt;#[cfg_attr(any(),rustfmt::skip)]mod combinations{use std::{collections::BTreeSet,mem::swap};pub trait SliceCombinationsExt<T>{fn for_each_product<F>(&self,r:usize,f:F)where F:FnMut(&[T]);fn for_each_permutations<F>(&self,r:usize,f:F)where F:FnMut(&[T]);fn for_each_combinations<F>(&self,r:usize,f:F)where F:FnMut(&[T]);fn for_each_combinations_with_replacement<F>(&self,r:usize,f:F)where F:FnMut(&[T]);fn next_permutation(&mut self)->bool where T:Ord;fn prev_permutation(&mut self)->bool where T:Ord;fn next_combination(&mut self,r:usize)->bool where T:Ord;fn prev_combination(&mut self,r:usize)->bool where T:Ord;fn apply_permutation(&mut self,permutation:&[usize]);}impl<T>SliceCombinationsExt<T>for[T]where T:Clone{#[doc=" choose `r` elements from `n` independently"]#[doc=""]#[doc=" # Example"]#[doc=""]#[doc=" ```"]#[doc=" # use competitive::algorithm::SliceCombinationsExt;"]#[doc=" let n = vec![1, 2, 3, 4];"]#[doc=" let mut p = Vec::new();"]#[doc=" let mut q = Vec::new();"]#[doc=" n.for_each_product(2, |v| p.push(v.to_vec()));"]#[doc=" for x in n.iter().cloned() {"]#[doc="     for y in n.iter().cloned() {"]#[doc="         q.push(vec![x, y]);"]#[doc="     }"]#[doc=" }"]#[doc=" assert_eq!(p, q);"]#[doc=" ```"]fn for_each_product<F>(&self,r:usize,mut f:F)where F:FnMut(&[T]){fn product_inner<T,F>(n:&[T],mut r:usize,buf:&mut Vec<T>,f:&mut F)where T:Clone,F:FnMut(&[T]){if r==0{f(buf.as_slice());}else{r-=1;for a in n.iter().cloned(){buf.push(a);product_inner(n,r,buf,f);buf.pop();}}}let mut v=Vec::with_capacity(r);product_inner(self,r,&mut v,&mut f);}#[doc=" choose `r` elements from `n` independently"]#[doc=""]#[doc=" # Example"]#[doc=""]#[doc=" ```"]#[doc=" # use competitive::algorithm::SliceCombinationsExt;"]#[doc=" let n = vec![1, 2, 3, 4];"]#[doc=" let mut p = Vec::new();"]#[doc=" let mut q = Vec::new();"]#[doc=" n.for_each_product(2, |v| p.push(v.to_vec()));"]#[doc=" for x in n.iter().cloned() {"]#[doc="     for y in n.iter().cloned() {"]#[doc="         q.push(vec![x, y]);"]#[doc="     }"]#[doc=" }"]#[doc=" assert_eq!(p, q);"]#[doc=" ```"]fn for_each_permutations<F>(&self,r:usize,mut f:F)where F:FnMut(&[T]){fn permutations_inner<T,F>(n:&[T],mut r:usize,rem:&mut BTreeSet<usize>,buf:&mut Vec<T>,f:&mut F)where T:Clone,F:FnMut(&[T]){if r==0{f(buf.as_slice());}else{r-=1;for i in rem.iter().cloned().collect::<Vec<_>>(){buf.push(n[i].clone());rem.remove(&i);permutations_inner(n,r,rem,buf,f);rem.insert(i);buf.pop();}}}if r<=self.len(){let mut v=Vec::with_capacity(r);let mut rem:BTreeSet<usize>=(0..self.len()).collect();permutations_inner(self,r,&mut rem,&mut v,&mut f);}}#[doc=" choose distinct `r` elements from `n` in any order"]#[doc=""]#[doc=" # Example"]#[doc=""]#[doc=" ```"]#[doc=" # use competitive::algorithm::SliceCombinationsExt;"]#[doc=" let n = vec![1, 2, 3, 4];"]#[doc=" let mut p = Vec::new();"]#[doc=" let mut q = Vec::new();"]#[doc=" n.for_each_permutations(2, |v| p.push(v.to_vec()));"]#[doc=" for (i, x) in n.iter().cloned().enumerate() {"]#[doc="     for (j, y) in n.iter().cloned().enumerate() {"]#[doc="         if i != j {"]#[doc="             q.push(vec![x, y]);"]#[doc="         }"]#[doc="     }"]#[doc=" }"]#[doc=" assert_eq!(p, q);"]#[doc=" ```"]fn for_each_combinations<F>(&self,r:usize,mut f:F)where F:FnMut(&[T]){fn combinations_inner<T,F>(n:&[T],mut r:usize,start:usize,buf:&mut Vec<T>,f:&mut F)where T:Clone,F:FnMut(&[T]){if r==0{f(buf.as_slice());}else{r-=1;for i in start..n.len()-r{buf.push(n[i].clone());combinations_inner(n,r,i+1,buf,f);buf.pop();}}}if r<=self.len(){let mut v=Vec::with_capacity(r);combinations_inner(self,r,0,&mut v,&mut f);}}#[doc=" choose `r` elements from `n` in sorted order"]#[doc=""]#[doc=" # Example"]#[doc=""]#[doc=" ```"]#[doc=" # use competitive::algorithm::SliceCombinationsExt;"]#[doc=" let n = vec![1, 2, 3, 4];"]#[doc=" let mut p = Vec::new();"]#[doc=" let mut q = Vec::new();"]#[doc=" n.for_each_combinations_with_replacement(2, |v| p.push(v.to_vec()));"]#[doc=" for (i, x) in n.iter().cloned().enumerate() {"]#[doc="     for y in n[i..].iter().cloned() {"]#[doc="         q.push(vec![x, y]);"]#[doc="     }"]#[doc=" }"]#[doc=" assert_eq!(p, q);"]#[doc=" ```"]fn for_each_combinations_with_replacement<F>(&self,r:usize,mut f:F)where F:FnMut(&[T]){fn combinations_with_replacement_inner<T,F>(n:&[T],mut r:usize,start:usize,buf:&mut Vec<T>,f:&mut F)where T:Clone,F:FnMut(&[T]){if r==0{f(buf.as_slice());}else{r-=1;for i in start..n.len(){buf.push(n[i].clone());combinations_with_replacement_inner(n,r,i,buf,f);buf.pop();}}}let mut v=Vec::with_capacity(r);combinations_with_replacement_inner(self,r,0,&mut v,&mut f);}#[doc=" Permute the elements into next permutation in lexicographical order."]#[doc=" Return whether such a next permutation exists."]fn next_permutation(&mut self)->bool where T:Ord{if self.len()<2{return false;}let mut target=self.len()-2;while target>0&&self[target]>=self[target+1]{target-=1;}if target==0&&self[target]>=self[target+1]{return false;}let mut next=self.len()-1;while next>target&&self[next]<=self[target]{next-=1;}self.swap(next,target);self[target+1..].reverse();true}#[doc=" Permute the elements into previous permutation in lexicographical order."]#[doc=" Return whether such a previous permutation exists."]fn prev_permutation(&mut self)->bool where T:Ord{if self.len()<2{return false;}let mut target=self.len()-2;while target>0&&self[target]<=self[target+1]{target-=1;}if target==0&&self[target]<=self[target+1]{return false;}self[target+1..].reverse();let mut next=self.len()-1;while next>target&&self[next-1]<self[target]{next-=1;}self.swap(target,next);true}#[doc=" Permute the elements into next combination choosing r elements in lexicographical order."]#[doc=" Return whether such a next combination exists."]fn next_combination(&mut self,r:usize)->bool where T:Ord{assert!(r<=self.len());let(a,b)=self.split_at_mut(r);next_combination_inner(a,b)}#[doc=" Permute the elements into previous combination choosing r elements in lexicographical order."]#[doc=" Return whether such a previous combination exists."]fn prev_combination(&mut self,r:usize)->bool where T:Ord{assert!(r<=self.len());let(a,b)=self.split_at_mut(r);next_combination_inner(b,a)}#[doc=" Apply a permutation to the elements."]#[doc=" `self[i] <- self[p[i]]` for each `i`."]fn apply_permutation(&mut self,p:&[usize]){assert_eq!(self.len(),p.len());let mut visited=vec![false;self.len()];for mut current in 0..self.len(){if visited[current]{continue;}loop{visited[current]=true;let next=p[current];if visited[next]{break;}self.swap(current,next);current=next;}}}}fn rotate_distinct<'a,T>(mut a:&'a mut[T],mut b:&'a mut[T]){while!a.is_empty()&&!b.is_empty(){if a.len()>=b.len(){let(l,r)=a.split_at_mut(b.len());l.swap_with_slice(b);a=r;}else{let(l,r)=b.split_at_mut(a.len());l.swap_with_slice(a);a=l;b=r;}}}fn next_combination_inner<T>(a:&mut[T],b:&mut[T])->bool where T:Ord{if a.is_empty()||b.is_empty(){return false;}let mut target=a.len()-1;let last_elem=b.last().unwrap();while target>0&&&a[target]>=last_elem{target-=1;}if target==0&&&a[target]>=last_elem{rotate_distinct(a,b);return false;}let mut next=0;while a[target]>=b[next]{next+=1;}swap(&mut a[target],&mut b[next]);rotate_distinct(&mut a[target+1..],&mut b[next+1..]);true}}