Recherche du point milieu des combinaisons d'un tableau

Question

J'ai une structure qui implémente Iterator dans Rust (bien que la question puisse s'appliquer à n'importe quel langage) pour calculer des combinaisons d'un tableau. L'itérateur est créé avec un tableau initial qui définit la valeur maximale de chaque entrée dans le tableau. Le code actuel de l'itérateur est encore en cours de développement, il y a donc probablement beaucoup d'endroits qui pourraient être améliorés.

Par exemple, si je crée une Combo en utilisant la fonction Combo::new(), et je donne le tableau set_max, [4,3,2,1], le iterator produira toutes les combinaisons d'un tableau de longueur 4, de telle sorte qu'aucune entrée dépasse l'entrée donnée dans set_max.

Ainsi, le premier tableau qui obtient produit est [0,0,0,1], suivie par [0,0,1,0], [0,0,1,1], [0,0,2,0], [0,0,2,1], [0,1,0,0], etc. Essentiellement, il incrémente une seule entrée à la fois, jusqu'à ce que l'entrée est maximisé-out. Ensuite, il le réinitialise et commence à incrémenter deux entrées à la fois.

Je voudrais que cet itérateur implémente rayon::ParallelIterator à un certain point, mais d'abord, je crois que j'ai besoin d'un moyen de diviser le calcul des combinaisons de moitié.

Comment puis-je trouver le point à mi-chemin de l'itérateur, afin que je puisse le diviser en deux parties? Après avoir trouvé ce point central, j'ai quelques idées sur l'implémentation de la fonction split: ajouter un tableau set_min qui spécifie un point de départ à partir duquel incrémenter les entrées. Mais le point principal de la question est de savoir comment trouver le point médian en général.

#[derive(Clone)] 
pub struct Combos { 
    pub set_max: Vec<usize>, 
    set_current: Vec<usize>, 
    size: usize, 
} 

impl Combos { 
    pub fn new(set_max: Vec<usize>) -> Combos { 
     Combos { 
      set_current: vec![0; set_max.len()], 
      size: set_max.iter().fold(1, |acc, x| (x + 1) * acc) - 1, 
      set_max: set_max, 
     } 
    } 

    fn increment_combo(&self, length: usize, combo: &[usize]) -> Vec<usize> { 
     if let Some(last) = combo.last() { 
      if *last == self.set_max[length - 1] { 
       let mut v = self.increment_combo(length - 1, &combo[..length - 1]); 
       v.push(0); 
       return v 
      } else { 
       let mut v = combo.to_vec(); 
       v[length - 1] = last + 1; 
       return v 
      } 
     } else { 
      return Vec::new() 
     } 
    } 
} 

impl Iterator for Combos { 
    type Item=Vec<usize>; 

    fn next(&mut self) -> Option<Vec<usize>> { 
     if self.set_current == self.set_max { 
      return None 
     } 

     self.set_current = self.increment_combo(self.set_max.len(), &self.set_current); 
     return Some(self.set_current.clone()) 
    } 
} 

Answer 1

juste la moitié de la première valeur du tableau pour couper l'opération en deux, depuis la première valeur est la dernière à augmenter dans votre algorithme (le plus important):

[4, 3, 2, 1] 

peut être couper cette façon:

first part: [0, 3, 2, 1] -> [1, 3, 2, 1] 
second part: [2, 3, 2, 1] -> [3, 3, 2, 1] 

par conséquent, ce qui est très facile à couper dans la moitié de votre algorithme: appeler la première partie avec [2, 3, 2, 1] et le second avec [4, 3, 2, 1] ce début: [2, 0, 0, 0].