import itertools


def gen_patterns(n, k):
    """Build patterns for digits(n) and substitutions (*)"""
    pattern = 'd' * (n - k) + '*' * k
    founded = set()
    patterns = []
    for composition in itertools.permutations(pattern, n):
        if composition not in founded:
            founded.add(composition)
            digits_at = [i for i, ch in enumerate(composition) if ch == '*']
            patterns.append(digits_at)
    return patterns