Constructing expressions that produce integers by only using digits in string '2017' and high school level operators and functions

At school, we have a competition where the winner is determined by the length of their unbroken sequence of expressions that evaluate to integers 0 to n.
You must use the next year's number in the correct order, every digit exactly once.

example:

0 = 2*0*17   
1 = 2-01^7  
2 = 2-0*17  
...

The competition doesn't have a section for computer-aided results, but I thought I would try it for fun.

The problem is, I don't know how to do this efficiently.
In Python 3.5, I am using

itertools.product('2017()*/+-',repetitions=a)

where a is an integer 4 to n to gather different lengths of expressions,

and picking the results that evaluate to integers and fit the criteria.
This takes more than O(10^n) time.

Is there a way to do this more efficiently in Python?
If I should change language, what would be relatively easy to write but efficient?

Here is my whole code:

import itertools
import timeit

max_length = 8
min_val = 0
max_val = 100

start_time = timeit.default_timer()

year = '2017'
special_chars = '()*/+-'
these_chars = year + special_chars

def perm(seq, n):
    for p in itertools.product(seq, repeat=n):
        yield p

# Does every character in str_a occur in str_b 
# in the right order and exactly once, with arbitrary in-betweens
def right_order(str_a, str_b):
    list_a = list(str_a)
    list_result = []
    for c in str_b:
        if c in str_a:
            list_result.append(c)
    if list_result == list_a:   
        return True
    else:
        return False

def strs(length, dictionary):
    for a in perm(these_chars, length):
        cand = 0
        a = ''.join(a)
        try:
            cand = eval(a)
            if int(cand) != cand:
                continue
        except:
            pass

        if right_order(year, a) == True: 
            if not any(c in '()' for c in str(cand)) and min_val  4))

print()
stop_time = timeit.default_timer()
print('execution time: ' + str(stop_time - start_time))

input('EXIT')

Where your code is currently lacking is using all the knowledge you have. You already know that in the end the digits have to be in order and that in between the digits there can (or can not) be an operator.

This means, we only need to generate all strings of the form s = "{}2{}0{}1{}7{}", where the {} denote a place for an operator.

In addition, we know that certain operators will never make sense at the beginning (like /) and most will not make sense at the end either (basically, only ) makes sense there).

If we use this fact, we can end up with something like:

from collections import defaultdict
from itertools import product
from math import *

allowed_begin = set(["", "+", "-", "sin(", "cos(", "tan(", "exp(", "("])
allowed = allowed_begin | set(
    ["*", "/", "**", "*sin(", "*cos(", "*tan(", "*exp(", "*(", ")"])
allowed_end = set(["", ")"])

def find_expressions():
    expressions = defaultdict(list)
    template = "{}2{}0{}1{}7{}"
    for ops in product(allowed_begin, allowed, allowed, allowed, allowed_end):
        try:
            expression = template.format(*ops)
            n = eval(expression)
            if n >= 0 and n % 1 == 0:
                print n, x
                expressions[n].append(expression)
        except Exception:
            pass

    return expressions

if __name__ == "__main__":
    expressions = find_expressions()
    print sorted(expressions.keys())

This runs in about 0.5s on my machine and finds expressions for
0.0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13, 14, 15, 16, 17, 18, 19, 20.0, 21, 26, 27, 28, 30, 34, 37, 120, 140, 160, 194, 208, 340, 1407, 2017, 32768, 1.1719142372802612e+16, 13107200000000000000000L, 6.327431707155585e+60, 1.7911398206275708e+84, 2.1540324218248465e+90, 4.572185553551339e+147. They are stored in expressions and all possible expressions for an existing key can be accesses via e.g. expressions[22].

Note that I chose to allow *( as an operator, meaning implicit multiplication (see comment on the question). If you think this is not allowed, just take them out of the allowed operators.

The loop approach has one advantage over itertools.permutations. It allows a == b == c == d. Whereas permutations does not:

>>> list(itertools.permutations([1,2], 2))
[(1,2), (2,1)]

Note the absence of (1,1) and (2,2).

StackExchange Code Review Q#149678, answer score: 4