Use given digits and operators to generate an expression that yields a requested value The exercise is as follows:


  Given K digits, show all the arithmetic expressions that yield a requested value (N), using four basic arithmetic operations. Each number should be used exactly one time, and the order of the digits may be changed. Don't use parenthesis.
  
  Example: 
  
  
    K = 1, 6, 7, 9
    
    N = 10
    
    One possible solution: 1 * 7 + 9 - 6
    
    Another one: 9 + 7 - 6 / 1
  


My code:

import itertools
from typing import (Sequence, Iterable, Iterator,
                    Union, Optional,
                    List, NamedTuple)

ALLOWED_OPERATORS = ('*', '/', '+', '-')  # , '**)
REPEAT_NUMBERS = False
DigitsSequence = Union[str, Sequence[Union[str, int]]]


class Answer(NamedTuple):
    solution: Optional[int]
    expression: str


def normalize_input(digits: DigitsSequence) -&gt; List[str]:
    try:
        new_digits = list(map(str, digits))  # type: ignore
        if not all(map(str.isdecimal, new_digits)):
            raise TypeError
    except TypeError:
        print("Digits must be an iterable containing strings.")
        return []
    return new_digits


def any_order(items: Sequence, length: int=None, allow_repeats: bool=True) \
              -&gt; Iterable:
    if length is None:
        length = len(items)

    if allow_repeats:
        yield from itertools.product(items, repeat=length)
    else:
        yield from itertools.permutations(items, r=length)


def zip_to_str(expression: Iterable) -&gt; str:
    return ''.join(''.join(i) for i in expression)


def get_answer(digits: List[str], operators: Sequence) -&gt; Answer:
    expression = zip_to_str(zip(digits, operators)) + digits[-1]
    try:
        return Answer(solution=eval(expression), expression=expression)
    except ZeroDivisionError:
        return Answer(solution=None, expression=expression)


def solver(digits: DigitsSequence, solution: int) -&gt; Iterator[str]:
    assert isinstance(solution, int), "Solution must be a number."
    all_digits = normalize_input(digits)

    for operators in any_order(ALLOWED_OPERATORS, length=len(all_digits)-1):
        for digits_option in any_order(all_digits, allow_repeats=REPEAT_NUMBERS):
                answer = get_answer(digits_option, operators)
                if answer.solution == solution:
                    yield answer.expression


if __name__ == '__main__':
    for solution in solver('1679', solution=27):
        print(solution)
The logic in normalize_input() is a bit bizarre. First, to your credit, you are doing DbC (design by contract) and enforcing a pre-condition. I would rather see the not all test performed immediately upon entry, rather than after computing new_digits. But then your error check raises and immediately catches. Please don't do that. Just use an if instead. Returning an exception to the caller might be better than returning an empty list. If we're going down the type safety route, I guess I'm wondering why a DigitsSequence would let a bad input to sneak in in the first place. I'm a little sad that we need to admit potentially non-numeric str, and can't make that type the output of some validation function.

You wrote "Digits must be an iterable containing strings." where "Digits must be a numeric string." seems more accurate. A different test would have been to assert str(int(digits)) == digits. You're using defensive programming, but it's not clear just who you're defending against.

I'm looking at any_order. I am relatively new to PEP484 annotations. I feel allow_repeats: bool=True completely makes sense, but OTOH length: int=None seems a bit odd, as None clearly doesn't appear on the number line. Would a sentinel of -1 instead of None maybe be a better idiom here? Or should I be viewing this in terms of the java int vs Integer distinction, where potentially we can always have a null object? If None is the appropriate pythonic way to phrase it (definitely true before PEP484), then should we maybe dispense with annotations for that particular parameter?

The specification is fairly clear:


  Each number should be used exactly one time,


therefore I recommend deleting the REPEAT_NUMBERS global, and inverting the allow_repeats default value. 

expression = zip_to_str(zip(digits, operators)) + digits[-1]


This is insane. I think you're making the observation that len(digits) = 1 + len(operators), but the code never enforces that. I would much much rather see zip(digits[:-1], operators) and then tack on the last element. Say what you mean and mean what you say.

solver() has a 2nd parameter of solution. For consistency, I would prefer to see Answer have a 2nd parameter of solution.

I have my doubts about DigitsSequence:
(1) maybe it's the sort of thing that offers false assurances, which gives type systems a bad name, or
(2) maybe what we really wanted was to pass in the results of list(map(int, digits)).

I am reading this line:

for operators in any_order(ALLOWED_OPERATORS, length=len(all_digits)-1):


I have no idea why the signature of any_order mentions length: int=None. That makes no sense to me. I recommend no default for that parameter.

I am reading this line:

    for digits_option in any_order(all_digits, allow_repeats=REPEAT_NUMBERS):


It essentially asks for permutations of all_digits. I'm not understanding how digits_option reflects that; it appears to me to be an ill-chosen name. I recommend digit_permutation instead.

It appears to me that Answer is not quite an accurate name - PotentialAnswer or CandidateAnswer seem closer. To retain the current name, we'd have to push the if answer.solution == solution test down into that class.