DEV Community

Cover image for Solving Coding Problems using the Inclusion-Exclusion Principle and its variations
Wewake
Wewake

Posted on

Solving Coding Problems using the Inclusion-Exclusion Principle and its variations

Problem Statement

Let's start with the problem statement:

Count the number of permutations of digits from 0 to 9 such that the first digit is greater than 1, and the last digit is less than 8.

Solving the inverse problem

We will try to solve for the inverse problem instead. i.e. finding all permutations where the first digit is greater than 1, OR the last digit is less than 8

If we define X and Y as follows:

X: The set of permutations where the first digit is less than or equal to 1.
Y: The set of permutations where the last digit is greater than or equal to 8.
Enter fullscreen mode Exit fullscreen mode

From venn diagram:

|X ∪ Y|
|X ∪ Y|

|X ∩ Y|:

|X ∩ Y|

it follows:

i.e.

|X ∪ Y| : Count of permutations with "first digit is less than or equal to 1" OR "last digit is greater than or equal to 8".

|X ∩ Y|: Count of permutations with "first digit is less than or equal to 1" AND "last digit is greater than or equal to 8".
Enter fullscreen mode Exit fullscreen mode
|X ∪ Y| : Represents all the bad permutations.
This is the solution to the "inverse" problem.

So,
Our answer = All Permutations of [O, 9]  - All Bad permutations
=> answer = All Permutations of [O, 9] - |X ∪ Y|

Since, `|X ∪ Y| = |X| + |Y| - |X ∩ Y|`

Answer = `Total Permutations of [O, 9] - (|X| + |Y| - |X ∩ Y|)`
Enter fullscreen mode Exit fullscreen mode

Here is the code:

from math import factorial

def count_permutations_ie():
    total_permutations = factorial(10)
    bad_first_digit = 2 * factorial(9)  # 2 options (0 or 1) for the first digit
    bad_last_digit = 2 * factorial(9)   # 2 options (8 or 9) for the last digit
    bad_first_and_last = 2 * 2 * factorial(8)  # 2 options for first, 2 for last

    bad_permutations = bad_first_digit + bad_last_digit - bad_first_and_last
    good_permutations = total_permutations - bad_permutations

    return good_permutations

print(f"Number of permutations (IE): {count_permutations_ie()}")
Enter fullscreen mode Exit fullscreen mode

This can also be solved via dynamic programming. See section Appendix.

Inclusion Exclusion Principle

What we observed above was basically the Inclusion Exclusion Principle.

To find |X ∪ Y|, we used |X| + |Y| - |X ∩ Y|.

Here is a more complete definition:

The Inclusion-Exclusion Principle is a counting technique that allows us to find the cardinality (size) of the union of multiple sets by considering their individual cardinalities, their intersections, and their complements. The principle states that:

|A_1 ∪ A_2 ∪ ... ∪ A_n| = Σ(|A_i|) - Σ(|A_i ∩ A_j|) + Σ(|A_i ∩ A_j ∩ A_k|) - ... + (-1)^(n-1) * |A_1 ∩ A_2 ∩ ... ∩ A_n|
Enter fullscreen mode Exit fullscreen mode

In simpler terms, the principle says that to find the cardinality of the union of sets, we need to:

  • Add the cardinalities of all the individual sets.
  • Subtract the cardinalities of all pairwise intersections of the sets.
  • Add the cardinalities of all triple intersections of the sets.
  • Subtract the cardinalities of all quadruple intersections of the sets, and so on, alternating the signs.

This formula might seem intimidating at first, but it becomes more intuitive with examples and practice.

Variations

Variation 1: Counting Sequences with Required Elements

Consider a problem where we need to count the number of sequences of length n consisting of only 0, 1, and 2, such that each number occurs at least once.

We can represent the set of "bad" sequences (those that don't satisfy the constraint) as the union of three sets:

A_0: The set of sequences that don't contain 0.
A_1: The set of sequences that don't contain 1.
A_2: The set of sequences that don't contain 2.
Using the Inclusion-Exclusion Principle, we can find the cardinality of the "bad" sequences as:

|A_0 ∪ A_1 ∪ A_2| = |A_0| + |A_1| + |A_2| - |A_0 ∩ A_1| - |A_0 ∩ A_2| - |A_1 ∩ A_2| + |A_0 ∩ A_1 ∩ A_2|
Enter fullscreen mode Exit fullscreen mode

We can calculate the cardinalities as follows:

def count_sequences(n):
    total_sequences = 3 ** n
    bad_sequences = 3 * (2 ** n) - 3 * (1) + 0
    good_sequences = total_sequences - bad_sequences
    return good_sequences

n = 5
print(f"Number of good sequences of length {n}: {count_sequences(n)}")
Enter fullscreen mode Exit fullscreen mode

This code will output the number of sequences of length n that contain all three elements (0, 1, and 2) at least once.

Variation 2: Number of upper-bound integer sums

For x1 + x2 + x3 + x4 + x5 + x6 = 20, where 0 <= xi <= 8, find the number of solutions.

  • Let's define the set of "good" solutions as the set of all tuples (x1, x2, x3, x4, x5, x6) that satisfy the equation x1 + x2 + x3 + x4 + x5 + x6 = 20 and the constraint 0 ≤ xi ≤ 8 for all i.
  • Also, let's define the set of "bad" solutions as the set of tuples that violate the constraint 0 ≤ xi ≤ 8 for at least one value of i.

Now, we can use the Inclusion-Exclusion Principle to count the number of "bad" solutions and then subtract it from the total number of solutions to get the count of "good" solutions.

Here is the code:

from functools import lru_cache

@lru_cache(maxsize=None)
def count_solutions(target, num_vars, lower_bound=0, upper_bound=8):
    """
    Count the number of solutions to the equation x1 + x2 + ... + xn = target,
    where lower_bound <= xi <= upper_bound for all i.
    """
    if num_vars == 1:
        return 1 if lower_bound <= target <= upper_bound else 0

    solutions = 0
    for x in range(lower_bound, upper_bound + 1):
        remaining_target = target - x
        solutions += count_solutions(remaining_target, num_vars - 1, lower_bound, upper_bound)

    return solutions

def count_solutions_with_inclusion_exclusion(target, num_vars, lower_bound=0, upper_bound=8):
    total_solutions = count_solutions(target, num_vars, 0, upper_bound)
    bad_solutions = 0

    for k in range(1, num_vars + 1):
        invalid_values = [0] * k + [-1] * (num_vars - k)
        bad_solutions += (-1) ** k * count_solutions(target, num_vars, lower_bound, upper_bound - 1, invalid_values)

    return total_solutions - bad_solutions

# Example usage
target = 20
num_vars = 6
print(f"Number of solutions: {count_solutions_with_inclusion_exclusion(target, num_vars)}")
Enter fullscreen mode Exit fullscreen mode

Variation 3: Leetcode Problem Ugly Number III

This is a bit advanced. Here, the Inclusion Exclusion Principle helps us break down the problem so that we can apply binary search, and find the solution.

An ugly number is a positive integer that is divisible by a, b, OR c.

Given four integers n, a, b, and c, return the nth ugly number.

Basically, we can find count of such ugly numbers from 1...N by doing this:

+ count of numbers from 1..n which are divisible by a
+ count of numbers from 1..n which are divisible by b
+ count of numbers from 1..n which are divisible by c
- count of numbers from 1..n which are divisible by a AND b
- count of numbers from 1..n which are divisible by b AND c
- count of numbers from 1..n which are divisible by a AND c
+ count of numbers from 1..n which are divisible by a,b AND c
Enter fullscreen mode Exit fullscreen mode

Let's call this f(K). Now the task is to find out the least K such that f(K) >= N.
We can do a binary search.

class Solution:
    def gcd(self, a, b):
        if b == 0:
            return a
        return self.gcd(b, a%b)

    def lcm(self, a, b):
        return (a * b) // self.gcd(a,b)

    def uglyCountFrom1toN(self, a, b, c, n):
        return n // a + n // b + n // c - n // self.lcm(a,b) - n // self.lcm(b,c) - n // self.lcm(a,c) + n // self.lcm(a,self.lcm(b,c))

    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:
        lo = min(a,b,c)
        hi = max(a*b*c, 2*pow(10,9))
        while lo < hi:
            mid = lo + (hi-lo)//2
            count = self.uglyCountFrom1toN(a,b,c,mid)
            # print(lo, hi, mid, count, n)
            if count < n:
                lo = mid+1
            else:
                hi = mid
            # print(lo, hi)
        return lo

Enter fullscreen mode Exit fullscreen mode

Other Variations

You can find several other variations in this wonderful detailed article.

Conclusion

The Inclusion-Exclusion Principle is a powerful combinatorics technique that can be applied to a wide range of counting problems. While the principle's formula might seem daunting at first, its systematic approach can simplify complex counting scenarios by breaking them down into manageable parts.

By understanding the Inclusion-Exclusion Principle and practicing its application, developers can enhance their problem-solving skills and tackle intricate counting problems more effectively. Whether you're working on algorithms, probability theory, or combinatorics-related challenges, mastering this technique can be a valuable asset in your programming toolbox.

References and Further Reading

Appendix

Can this be solved using Dynamic Programming ?
Yes.
Let's define dp[i][j] that stores the count of permutations of length i where the first digit is j.

from math import factorial
def count_permutations_dp(n):
    dp = [[0] * 10 for _ in range(n + 1)]

    # Base case: For permutations of length 1, there's 1 permutation for each digit
    for j in range(10):
        dp[1][j] = 1

    # Fill the dp table
    for i in range(2, n + 1):
        for j in range(10):
            if j > 1:  # Include permutations where the first digit is greater than 1
                dp[i][j] = 9 * dp[i - 1][j] + factorial(9)
            else:
                dp[i][j] = 8 * dp[i - 1][j]

    # Calculate the desired result
    result = sum(dp[n][j] for j in range(2, 8))
    return result

print(f"Number of permutations (DP): {count_permutations_dp(10)}")
Enter fullscreen mode Exit fullscreen mode

Time complexity: O(n * 10)
Space complexity:O(n * 10), where n is the number of digits (10 in this case).


This article was originally published on my blog at https://wewake.dev/posts/inclusion-exclusion-principle/

Find more of my content of my blog, where I share my software development experiences and learnings: https://wewake.dev

Top comments (0)