-
Notifications
You must be signed in to change notification settings - Fork 309
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Feature Request: partitions
#611
Comments
Hi @bruderjakob17. I think this might be a neat addition. I think I understand the idea of your algorithm (though I did not in-depth-review it), and I think we can go with it (we do similar index mapping in Some remarks on the code on stackoverflow before you dive in (copied in so you have it at hand):
Regarding all of the above: I might be wrong with my assessment, so please apply your judgement where necessary. |
Hi @phimuemue :) First of all, thanks for all your comments and sorry for the late reply. Also, in the meantime I implemented a version where one can iterate also over all partitions over a specific size (the approach is similar, only that viable sequences have the additional requirement that there need to be k different p_i (where k is the number of classes into which the vec is partitioned)). I will just post the modified code below: pub struct Partition<'a, T> where T: Copy {
elements: &'a Vec<T>,
index_map: Vec<usize>,
number_of_classes: Option<usize>,
initialized: bool,
}
impl<'a, T> Partition<'a, T> where T: Copy {
fn smallest_viable(v: &'a Vec<T>, k: Option<usize>) -> Partition<'a, T> {
let initial_index_map = match k {
None => vec![0; v.len()],
Some(k) => {
let mut initial_index_map = vec![0; v.len() - k];
initial_index_map.append(&mut (0..k).collect());
initial_index_map
}
};
Partition::<T> { elements: v, index_map: initial_index_map, number_of_classes: k, initialized: true }
}
fn is_incrementable(&self, index: usize) -> bool {
index < self.index_map.len()
&& index > 0
&& (0..index).any(|x| self.index_map[x] == self.index_map[index])
// additional constraint: when only partitions into number_of_classes subsets are required
&& (self.number_of_classes == None || self.index_map[index] + 1 < self.number_of_classes.unwrap())
}
fn increment(&mut self, index: usize) { //TODO BUGFIXES
self.index_map[index] += 1;
match self.number_of_classes {
None => {
for x in index + 1..self.index_map.len() {
self.index_map[x] = 0;
}
},
Some(k) => {
let m = self.index_map[0..=index].iter().map(|x| *x).max().unwrap();
// now, append 0...0(m+1)(m+2)...(k - 1).
// note that k - 1 = m + (k - 1 - m).
// hence, (k - 1 - m) is the length of the tail
let first_nonzero_index = self.index_map.len() - (k - 1 - m);
for x in index + 1..first_nonzero_index {
self.index_map[x] = 0;
}
for x in first_nonzero_index..self.index_map.len() {
self.index_map[x] = m + x - first_nonzero_index + 1;
}
}
}
}
fn create_partition(&self) -> Vec<Vec<T>> {
if let Some(&max_index) = self.index_map.iter().max(){
return (0..=max_index).map(|x| zip(self.elements, &self.index_map)
.filter(|(_e,i)| **i == x).map(|(e,_i)| *e).collect())
.collect();
} else {
return Vec::new();
}
}
}
impl<'a, T> Iterator for Partition<'a, T> where T: Copy {
type Item = Vec<Vec<T>>;
fn next(&mut self) -> Option<Self::Item> {
if self.initialized {
self.initialized = false;
return Some(self.create_partition());
}
for index in (0..self.index_map.len()).rev() {
if self.is_incrementable(index) {
self.increment(index);
return Some(self.create_partition());
}
}
return None;
}
}
pub fn partitions<'a, T>(v: &'a Vec<T>, k: Option<usize>) -> Partition<'a, T> where T: Copy {
Partition::smallest_viable(v, k)
}
impl<'a, T> Iterator for Partition<'a, T> where T: Copy {
type Item = Vec<Vec<T>>;
fn next(&mut self) -> Option<Self::Item> {
if self.initialized {
self.initialized = false;
return Some(self.create_partition());
}
for index in (1..self.index_map.len()).rev() {
if
(0..index).any(|x| self.index_map[x] == self.index_map[index])
// additional constraint: when only partitions into number_of_classes subsets are required
&& (self.number_of_classes == None || self.index_map[index] + 1 < self.number_of_classes.unwrap())
{
self.index_map[index] += 1;
match self.number_of_classes {
None => {
for x in index + 1..self.index_map.len() {
self.index_map[x] = 0;
}
},
Some(k) => {
let m = self.index_map[0..=index].iter().map(|x| *x).max().unwrap();
// now, append 0...0(m+1)(m+2)...(k - 1).
// note that k - 1 = m + (k - 1 - m).
// hence, (k - 1 - m) is the length of the tail
let first_nonzero_index = self.index_map.len() - (k - 1 - m);
for x in index + 1..first_nonzero_index {
self.index_map[x] = 0;
}
for x in first_nonzero_index..self.index_map.len() {
self.index_map[x] = m + x - first_nonzero_index + 1;
}
}
}
return Some(self.create_partition());
}
}
return None;
}
}
fn create_partition(&self) -> Vec<Vec<T>> {
if let Some(&max_index) = self.index_map.iter().max() {
let mut partition_classes = vec![Vec::new(); max_index + 1];
for i in 0..self.index_map.len(){
partition_classes[self.index_map[i]].push(self.elements[i]);
}
return partition_classes;
} else {
return Vec::new();
}
}
As a final comment: here is the code above with your first two suggestions: pub struct Partition<'a, T> where T: Copy {
elements: &'a Vec<T>,
index_map: Vec<usize>,
number_of_classes: Option<usize>,
initialized: bool,
}
impl<'a, T> Partition<'a, T> where T: Copy {
fn smallest_viable(v: &'a Vec<T>, k: Option<usize>) -> Partition<'a, T> {
let initial_index_map = match k {
None => vec![0; v.len()],
Some(k) => {
let mut initial_index_map = vec![0; v.len() - k];
initial_index_map.append(&mut (0..k).collect());
initial_index_map
}
};
Partition::<T> { elements: v, index_map: initial_index_map, number_of_classes: k, initialized: true }
}
fn create_partition(&self) -> Vec<Vec<T>> {
if let Some(&max_index) = self.index_map.iter().max() {
let mut partition_classes = vec![Vec::new(); max_index + 1];
for i in 0..self.index_map.len(){
partition_classes[self.index_map[i]].push(self.elements[i]);
}
return partition_classes;
} else {
return Vec::new();
}
}
}
impl<'a, T> Iterator for Partition<'a, T> where T: Copy {
type Item = Vec<Vec<T>>;
fn next(&mut self) -> Option<Self::Item> {
if self.initialized {
self.initialized = false;
return Some(self.create_partition());
}
for index in (1..self.index_map.len()).rev() {
if
(0..index).any(|x| self.index_map[x] == self.index_map[index])
// additional constraint: when only partitions into number_of_classes subsets are required
&& (self.number_of_classes == None || self.index_map[index] + 1 < self.number_of_classes.unwrap())
{
self.index_map[index] += 1;
match self.number_of_classes {
None => {
for x in index + 1..self.index_map.len() {
self.index_map[x] = 0;
}
},
Some(k) => {
let m = self.index_map[0..=index].iter().map(|x| *x).max().unwrap();
// now, append 0...0(m+1)(m+2)...(k - 1).
// note that k - 1 = m + (k - 1 - m).
// hence, (k - 1 - m) is the length of the tail
let first_nonzero_index = self.index_map.len() - (k - 1 - m);
for x in index + 1..first_nonzero_index {
self.index_map[x] = 0;
}
for x in first_nonzero_index..self.index_map.len() {
self.index_map[x] = m + x - first_nonzero_index + 1;
}
}
}
return Some(self.create_partition());
}
}
return None;
}
}
pub fn partitions<'a, T>(v: &'a Vec<T>, k: Option<usize>) -> Partition<'a, T> where T: Copy {
Partition::smallest_viable(v, k)
} |
Hi @bruderjakob17, just want to let you know that I did not forget this. The new implementation imho already looks much cleaner. If you want to pursue this further, please do the following:
If you want, I think you can then also open a PR (which usually gets a bit more feedback). I do not have much free time right now, but you can be assured that I'd really like to have this feature. |
Hi @phimuemue , Thanks again for your comments. I simplified (and commented) the code again. Into which branch should I merge my PR? |
Hi @bruderjakob17, cool. Please rebase against the branch If you do this, please ansure that no unrelated (formatting) changes are included in the PR, and - if needed - split your changes into several commits. |
It would be neat to have a way of iterating over all possible partitions of some vector. Example usages:
all_partitions(&vec![7,8,9])
should iterate overwhile
partitions(&vec![6,7,8,9], 2)
should iterate overRemark: I asked this question on StackOverflow, and implemented a version of
all_partitions()
. I am happy to create a PR if this is something that could belong to theitertools
package.The text was updated successfully, but these errors were encountered: