Function comlib_math::subsets::subsets

pub fn subsets(n: usize) -> Subsets

Constructs an iterator over subsets of given size.

For example the subsets of [1, 2, 3] are [], [1], [2], [1, 2], [3], [1, 3], [2, 3], and [1, 2, 3].

Note that the subsets are based on indices and hence this method doesn’t do any kind of deduplication of the data. For example subsets of array [1, 1] are [], [1], [1], and [1, 1].

See Subset for methods implemented on subsets.

Examples

// Let's count the number of positive integers less than 10 that are divided by 2, 3, or 5, using
// inclusion-exclusion principle.
let primes = [2, 3, 5];
let result: i32 = subsets(primes.len())
    .map(|subset| {
        // We don't want to consider the empty subset
        if subset.is_empty() {
            return 0;
        }

        // Compute the value represented by the subset of primes
        let num: i32 = subset.select(&primes).product();
        // Compute the number of integers at most 100 that are divisible by num
        let count = 100 / num;

        if subset.len() % 2 == 1 {
            // We add odd subsets
            count
        } else {
            // and subtract even ones
            -count
        }
    })
    .sum();
assert_eq!(result, 74);