pub fn group_by_ignoring_digits(
    start: usize,
    end: usize,
    base: usize,
    nb_digits: usize,
) -> Vec<Vec<usize>> {
    let mut ds = decompose_value(start as usize, base as usize, nb_digits as usize);
    let mut de = decompose_value(end as usize, base as usize, nb_digits as usize);

    // We take the common prefix of start and end and save it, so we are guaranteed that ds[0] != de[0].
    let prefix = take_prefix(&mut ds, &mut de);

    // If start is all 0 and end is all base - 1, the prefix is enough to cover the interval.
    if (ds.is_empty() && de.is_empty())
        || (ds.iter().all(|x| *x == 0) && de.iter().all(|x| *x == base - 1))
    {
        return vec![prefix];
    }

    // We can remove the trailing 0s from the start and trailing base - 1 from the end
    // as they will be covered the interval represented by the digits in front of them.
    remove_tail(&mut ds, 0);
    remove_tail(&mut de, base - 1);

    // We initialize the stack with the start digits.
    let mut stack = ds.clone();
    let mut list = Vec::new();

    // This will generate all the prefixes for the interval [start, start[0]..base - 1]. E.g.
    // if start is 1234 in base 10, this will generate for [1234, 1999].
    while stack.len() != 1 {
        let i = stack.len() - 1;
        // Once the last digit of the stack is base - 1, we can save the prefix and pop a digit.
        // E.g. if we have our stack as [1, 2, 3, 9], next is [1, 2, 4, 0], but we don't need the last 0
        // as we can cover with [1, 2, 4].
        if stack[i] == base - 1 {
            list.push(stack.clone());
            stack.pop();
            // We can remove any base - 1 digits at this point. E.g. if we had [1, 2, 9, 9] above,
            // now we have [1, 2, 9], next is [1, 3, 0], but similarly as above we can get rid of
            // the trailing zero.
            remove_tail(&mut stack, base - 1);
            // We increment the last digit (e.g. move from [1, 2] to [1, 3] in the example above).
            let j = stack.len() - 1;
            stack[j] += 1;
        } else if stack[i] == 0 {
            // We can always get rid of trailing zeros (up to the first digit). E.g. if we have
            // out stack as [1, 3, 0, 0], [1, 3] is enough to cover the interval
            remove_tail(&mut stack, 0);
        } else {
            // We save the stack an increment the last digit. E.g. if we had [1, 2, 3, 4], we save it
            // and move to [1, 2, 3, 5].
            list.push(stack.clone());
            stack[i] += 1;
        }
        assert!(stack.iter().all(|x| x < &base));
    }

    // All the single digits in ]start[0]; end[0][ are sufficient to cover their respective intervals.
    // E.g. with start = 1234 and end = 4567, 2___ and 3___ are enough to cover between 2000 and 3999.
    while stack[0] != de[0] {
        list.push(stack.clone());
        stack[0] += 1;
    }

    // We take care of the interval [end[0]..0; end]. E.g. if end is 4567 that's [4000; 4567].
    while stack != de {
        let i = stack.len() - 1;
        // If stack has common prefix with end, we need to push a zero. E.g. if stack is [4], we
        // want then have stack as [4, 0], so we will cover [4000; 4499] with (40, 41, 42, 43).
        if stack[i] == de[i] {
            stack.push(0);
        } else {
            // We save the stack and increment the last digit. E.g. if we have [4, 0], we move to [4, 1].
            list.push(stack.clone());
            stack[i] += 1;
        }
    }

    // We need to include end (previous condition exit when stack is equal to end).
    list.push(de);

    // We add the common prefix of start and end if there was one and return our list of prefixes.
    if !prefix.is_empty() {
        list.into_iter()
            .map(|mut x| {
                let mut p = prefix.clone();
                p.append(&mut x);
                p
            })
            .collect()
    } else {
        list
    }
}
/// Returns the set of decomposed prefixes that cover the range [start, end].
Returns the set of decomposed prefixes that cover the range [start, end].
Returns the set of decomposed prefixes that cover the range [ start end ] .
pub fn group_by_ignoring_digits(
    start: usize,
    end: usize,
    base: usize,
    nb_digits: usize,
) -> Vec<Vec<usize>> {
    let mut ds = decompose_value(start as usize, base as usize, nb_digits as usize);
    let mut de = decompose_value(end as usize, base as usize, nb_digits as usize);
    // We take the common prefix of start and end and save it, so we are guaranteed that ds[0] != de[0].
    let prefix = take_prefix(&mut ds, &mut de);
    // If start is all 0 and end is all base - 1, the prefix is enough to cover the interval.
    if (ds.is_empty() && de.is_empty())
        || (ds.iter().all(|x| *x == 0) && de.iter().all(|x| *x == base - 1))
    {
        return vec![prefix];
    }
    // We can remove the trailing 0s from the start and trailing base - 1 from the end
    // as they will be covered the interval represented by the digits in front of them.
    remove_tail(&mut ds, 0);
    remove_tail(&mut de, base - 1);
    // We initialize the stack with the start digits.
    let mut stack = ds.clone();
    let mut list = Vec::new();
    // This will generate all the prefixes for the interval [start, start[0]..base - 1]. E.g.
    // if start is 1234 in base 10, this will generate for [1234, 1999].
    while stack.len() != 1 {
        let i = stack.len() - 1;
        // Once the last digit of the stack is base - 1, we can save the prefix and pop a digit.
        // E.g. if we have our stack as [1, 2, 3, 9], next is [1, 2, 4, 0], but we don't need the last 0
        // as we can cover with [1, 2, 4].
        if stack[i] == base - 1 {
            list.push(stack.clone());
            stack.pop();
            // We can remove any base - 1 digits at this point. E.g. if we had [1, 2, 9, 9] above,
            // now we have [1, 2, 9], next is [1, 3, 0], but similarly as above we can get rid of
            // the trailing zero.
            remove_tail(&mut stack, base - 1);
            // We increment the last digit (e.g. move from [1, 2] to [1, 3] in the example above).
            let j = stack.len() - 1;
            stack[j] += 1;
        } else if stack[i] == 0 {
            // We can always get rid of trailing zeros (up to the first digit). E.g. if we have
            // out stack as [1, 3, 0, 0], [1, 3] is enough to cover the interval
            remove_tail(&mut stack, 0);
        } else {
            // We save the stack an increment the last digit. E.g. if we had [1, 2, 3, 4], we save it
            // and move to [1, 2, 3, 5].
            list.push(stack.clone());
            stack[i] += 1;
        }
        assert!(stack.iter().all(|x| x < &base));
    }
    // All the single digits in ]start[0]; end[0][ are sufficient to cover their respective intervals.
    // E.g. with start = 1234 and end = 4567, 2___ and 3___ are enough to cover between 2000 and 3999.
    while stack[0] != de[0] {
        list.push(stack.clone());
        stack[0] += 1;
    }
    // We take care of the interval [end[0]..0; end]. E.g. if end is 4567 that's [4000; 4567].
    while stack != de {
        let i = stack.len() - 1;
        // If stack has common prefix with end, we need to push a zero. E.g. if stack is [4], we
        // want then have stack as [4, 0], so we will cover [4000; 4499] with (40, 41, 42, 43).
        if stack[i] == de[i] {
            stack.push(0);
        } else {
            // We save the stack and increment the last digit. E.g. if we have [4, 0], we move to [4, 1].
            list.push(stack.clone());
            stack[i] += 1;
        }
    }
    // We need to include end (previous condition exit when stack is equal to end).
    list.push(de);
    // We add the common prefix of start and end if there was one and return our list of prefixes.
    if !prefix.is_empty() {
        list.into_iter()
            .map(|mut x| {
                let mut p = prefix.clone();
                p.append(&mut x);
                p
            })
            .collect()
    } else {
        list
    }
}
pub fn group_by_ignoring_digits ( start : usize , end : usize , base : usize , nb_digits : usize , ) -> Vec < Vec < usize > > { let mut ds = decompose_value ( start as usize , base as usize , nb_digits as usize ) ; let mut de = decompose_value ( end as usize , base as usize , nb_digits as usize ) ; // We take the common prefix of start and end and save it, so we are guaranteed that ds[0] != de[0]. let prefix = take_prefix ( & mut ds , & mut de ) ; // If start is all 0 and end is all base - 1, the prefix is enough to cover the interval. if ( ds . is_empty ( ) && de . is_empty ( ) ) || ( ds . iter ( ) . all ( | x | * x == 0 ) && de . iter ( ) . all ( | x | * x == base - 1 ) ) { return vec ! [ prefix ] ; } // We can remove the trailing 0s from the start and trailing base - 1 from the end // as they will be covered the interval represented by the digits in front of them. remove_tail ( & mut ds , 0 ) ; remove_tail ( & mut de , base - 1 ) ; // We initialize the stack with the start digits. let mut stack = ds . clone ( ) ; let mut list = Vec :: new ( ) ; // This will generate all the prefixes for the interval [start, start[0]..base - 1]. E.g. // if start is 1234 in base 10, this will generate for [1234, 1999]. while stack . len ( ) != 1 { let i = stack . len ( ) - 1 ; // Once the last digit of the stack is base - 1, we can save the prefix and pop a digit. // E.g. if we have our stack as [1, 2, 3, 9], next is [1, 2, 4, 0], but we don't need the last 0 // as we can cover with [1, 2, 4]. if stack [ i ] == base - 1 { list . push ( stack . clone ( ) ) ; stack . pop ( ) ; // We can remove any base - 1 digits at this point. E.g. if we had [1, 2, 9, 9] above, // now we have [1, 2, 9], next is [1, 3, 0], but similarly as above we can get rid of // the trailing zero. remove_tail ( & mut stack , base - 1 ) ; // We increment the last digit (e.g. move from [1, 2] to [1, 3] in the example above). let j = stack . len ( ) - 1 ; stack [ j ] += 1 ; } else if stack [ i ] == 0 { // We can always get rid of trailing zeros (up to the first digit). E.g. if we have // out stack as [1, 3, 0, 0], [1, 3] is enough to cover the interval remove_tail ( & mut stack , 0 ) ; } else { // We save the stack an increment the last digit. E.g. if we had [1, 2, 3, 4], we save it // and move to [1, 2, 3, 5]. list . push ( stack . clone ( ) ) ; stack [ i ] += 1 ; } assert ! ( stack iter ( ) all ( x x base ) ) ; } // All the single digits in ]start[0]; end[0][ are sufficient to cover their respective intervals. // E.g. with start = 1234 and end = 4567, 2___ and 3___ are enough to cover between 2000 and 3999. while stack [ 0 ] != de [ 0 ] { list . push ( stack . clone ( ) ) ; stack [ 0 ] += 1 ; } // We take care of the interval [end[0]..0; end]. E.g. if end is 4567 that's [4000; 4567]. while stack != de { let i = stack . len ( ) - 1 ; // If stack has common prefix with end, we need to push a zero. E.g. if stack is [4], we // want then have stack as [4, 0], so we will cover [4000; 4499] with (40, 41, 42, 43). if stack [ i ] == de [ i ] { stack . push ( 0 ) ; } else { // We save the stack and increment the last digit. E.g. if we have [4, 0], we move to [4, 1]. list . push ( stack . clone ( ) ) ; stack [ i ] += 1 ; } } // We need to include end (previous condition exit when stack is equal to end). list . push ( de ) ; // We add the common prefix of start and end if there was one and return our list of prefixes. if ! prefix . is_empty ( ) { list . into_iter ( ) . map ( | mut x | { let mut p = prefix . clone ( ) ; p . append ( & mut x ) ; p } ) . collect ( ) } else { list } }
Returns the set of decomposed prefixes that cover the range [start, end].
Returns the set of decomposed prefixes that cover the range [ start end ] .
start
usize
end
usize
base
usize
nb_digits
usize