[Python] Fastest way to find all permutations of 0, 1 of width n without itertools in pure...

If there is a duplicate, I couldn't find it. I scrolled through 272 irrelevant Google search results to check if there is an exact duplicate. And the last edit to my previous question was rolled back and this comment tells me to post a new question, so I posted a new question.

I want to create an efficient (efficient as in optimized for less execution time) power set function without using itertools and using only built-in Python functions and operators etc. (everything usable without any import) as a self-imposed programming challenge.

The problem boils down to generate all permutations of 0 and 1 with width N, which is equivalent to counting the first N natural numbers in binary. The output should be in tuple format.

For example, given N=3, the output should contain: (0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1) in exactly the same order. And under the aforementioned restrictions, itertools.product((0, 1), repeat=3) doesn't qualify as a solution.

I tried to solve the problem myself, I wrote an efficient function to do this, then two slow functions to compare with the original function.

from typing import Generator, Tuple

def powerset_indices(l: int) -> Generator[Tuple[int, ...], None, None]:
if not isinstance(l, int) or l < 1:
raise ValueError("The argument l must be a positive integer")

numeral = [0] * l
maxi = l - 1
for _ in range(1 << l):
yield tuple(numeral)
i = maxi
while True:
if not (d := numeral):
numeral = 1
break
else:
numeral = 0
i -= 1


def powerset_indices1(l: int) -> Generator[Tuple[int, ...], None, None]:
if not isinstance(l, int) or l < 1:
raise ValueError("The argument l must be a positive integer")

for i in range(1 << l):
yield tuple(map(int, f"{i:0{l}b}"))


def powerset_indices2(l: int) -> Generator[Tuple[bool, ...], None, None]:
if not isinstance(l, int) or l < 1:
raise ValueError("The argument l must be a positive integer")

places = [1 << (l - i) for i in range(l - 1, -1, -1)]
for i in range(1<<l):
yield tuple((i & p) > 0 for p in places)


In [133]: from itertools import product

In [134]: %timeit list(powerset_indices(16))
19.8 ms ± 92.2 μs per loop (mean ± std. dev. of 7 runs, 100 loops each)

In [135]: %timeit list(product((0, 1), repeat=16))
6.86 ms ± 32.5 μs per loop (mean ± std. dev. of 7 runs, 100 loops each)

In [136]: %timeit list(powerset_indices1(16))
184 ms ± 485 μs per loop (mean ± std. dev. of 7 runs, 10 loops each)

In [137]: %timeit list(powerset_indices2(16))
136 ms ± 277 μs per loop (mean ± std. dev. of 7 runs, 10 loops each)


My original function is only slower than product and it is faster than the two later functions by a wide margin. Can anyone offer a solution faster than powerset_indices while only using built-in Python?

Continue reading...