Partition

Une utilisation rigolote de try_for_each…

On prend en entrée une tranche de i32. On cherche à savoir s’il est possible de la décomposer en trois sous-tranches S1, S2, S3 telles que:

les sommes des elements de chaque tranche sont égales
toutes les tranches sont disjointes
l’union des tranches forme S

Attention il s’agit de tranches, le problème n’est donc pas NP-dur.

Voici un petit jeu de tests:

fn main() {
    let v = vec![1, 5, -1, 2, 3, 2, 3, -2, 2];
    assert!(partition3(&v));
    let w = vec![1, 3, 2, 4, 2, 3, 5, 3];
    assert!(!partition3(&w));
    let x = vec![5, 6, 5, -1];
    assert!(!partition3(&x));
}

Le but du jeu est d’écrire un code fonctionnel de coût linéaire.

Solution

Commençons par l’idée principale. On commence par calculer la somme de toute la tranche, de manière à calculer la quantité à mettre dans chaque sous tranche:

fn partition3(tranche: &[i32]) -> bool {
    let somme = tranche.iter().sum();

On va ensuite itérer sur toutes les sommes partielles de s à l’aide de scan. Les sommes partielles commencent à 0 et terminent à somme. Si il est possible de partitionner alors,

à la fin de S1, la somme partielle est somme/3
à la fin de S2, la somme partielle est 2*somme/3

Cette propriété est valable même si plusieurs solutions sont possibles.

    somme % 3 == 0
        && sous_sequence(
            vec![somme / 3, 2 * somme / 3, somme],
            tranche.iter().scan(0, |s, e| {
                *s += e;
                Some(*s)
            }),
        )
}

Il nous reste juste à vérifier que la séquence des tiers de somme est une sous-séquence de toutes les sommes partielles.

Est-ce que vous voyez comment faire (j’utilise try_for_each)?

Sous Séquence

Voici ma solution:

fn sous_sequence<T, I, J>(i: I, j: J) -> bool
where
    T: Eq,
    I: IntoIterator<Item = T>,
    J: IntoIterator<Item = T>,
{
    let mut iter_j = j.into_iter();
    i.into_iter().all(|ei| {
        iter_j
            .try_for_each(|ej| if ei == ej { Err(()) } else { Ok(()) })
            .is_err()
    })
}

Le all me permet de vérifier que tous les éléments i sont bien dans j. Notons que l’on peut s’arrêter avant la fin de j mais que c’est une ‘feature’, la somme des éléments restants valant alors 0.

Le truc délicat c’est qu’il faut à chaque fois repartir du dernier endroit où l’on s’était arrêté lors du parcours de j. Toutes les opérations en try_.... sur les itérateurs permettent exactement ça. Si on regarde le prototype:

fn try_for_each<F, R>(&mut self, f: F) -> R where
    F: FnMut(Self::Item) -> R,
        R: Try<Ok = ()>,

on se rend compte que l’itérateur n’est pas consommé mais emprunté en écriture.

Le try_fold en particulier est important en rust et il est conseillé de l’implémenter manuellement lorsque l’on développe un itérateur s’il est possible d’avoir une implémentation meilleure que celle par défaut.