iterating through submasks Algorithm

The iterating through submasks algorithm is an advanced programming technique that allows efficient manipulation of bitmasks. This algorithm is particularly useful when dealing with combinatorial problems or tasks that involve iterating over all subsets of a given set. It is a powerful tool for solving problems with constraints and can significantly reduce the time complexity of certain algorithms. The main idea behind the algorithm is to iterate through all submasks of a given bitmask in a specific order, allowing the programmer to perform various operations on these submasks. One of the primary benefits of the iterating through submasks algorithm is that it can greatly optimize the performance of dynamic programming solutions. The algorithm can be used to traverse all possible subsets of a set of elements and allows for faster enumeration of these subsets. This is particularly useful in problems where the order of elements in the subset does not matter, allowing the programmer to process the subsets in a specific way without having to generate all possible combinations manually. The iterating through submasks algorithm can be implemented using bitwise operations, which are fast and efficient, making it an excellent choice for solving complex combinatorial problems in a time-efficient manner.
"""
Author : Syed Faizan (3rd Year Student IIIT Pune)
github : faizan2700
You are given a bitmask m and you want to efficiently iterate through all of
its submasks. The mask s is submask of m if only bits that were included in
bitmask are set
"""
from typing import List


def list_of_submasks(mask: int) -> List[int]:

    """
    Args:
        mask : number which shows mask ( always integer > 0, zero does not have any submasks )

    Returns:
        all_submasks : the list of submasks of mask (mask s is called submask of mask
        m if only bits that were included in original mask are set

    Raises:
        AssertionError: mask not positive integer

    >>> list_of_submasks(15)
    [15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
    >>> list_of_submasks(13)
    [13, 12, 9, 8, 5, 4, 1]
    >>> list_of_submasks(-7)  # doctest: +ELLIPSIS
    Traceback (most recent call last):
        ...
    AssertionError: mask needs to be positive integer, your input -7
    >>> list_of_submasks(0)  # doctest: +ELLIPSIS
    Traceback (most recent call last):
        ...
    AssertionError: mask needs to be positive integer, your input 0

    """

    fmt = "mask needs to be positive integer, your input {}"
    assert isinstance(mask, int) and mask > 0, fmt.format(mask)

    """
    first submask iterated will be mask itself then operation will be performed
    to get other submasks till we reach empty submask that is zero ( zero is not
    included in final submasks list )
    """
    all_submasks = []
    submask = mask

    while submask:
        all_submasks.append(submask)
        submask = (submask - 1) & mask

    return all_submasks


if __name__ == "__main__":
    import doctest

    doctest.testmod()

LANGUAGE:

DARK MODE: