Filter out unwanted substrings while generating all possible relevant substrings Write a Program that determines where to add periods to a decimal string so that
  the resulting string is a valid IP address. There may be more than one valid IP address
  corresponding to a string, in which case you should print all possibilities. For example, if the mangled string is "19216811" then some of the corresponding IP addresses are 192.168.1.1 and 19.216.81.1


Elements of Programming Interviews Section 6.9 See Bottom of Page 82, asks the following as a variant to the above problem:

Now suppose we need to solve the analogous problem when the number of periods is a parameter k and the
string length s is unbounded. 

See attempt below, I am generating all permutations, see permute(s), of the string and then filtering later hence I end up doing unnecessary work. Can I do better?

def period_partition(s, k):
    slen = len(s)

    def is_valid_octet(s):
        # section ranges 0 - 255 and `00` or `000`, `01` are not valid but 0 is
        return slen == 1 or (s[0] != "0" and 0 &lt;= int(s) &lt;= 255)

    def permute(s):
        if len(s) &gt; 0:
            for i in range(1, slen + 1):
                first, rest = s[:i], s[i:]
                for p in permute(rest):
                    yield [first] + p
        else:
            yield []

    results = set()

    for s in filter(
        lambda x: len(x) == k + 1 and all(is_valid_octet(i) for i in x), permute(s),
    ):
        results.add(".".join(s))

    return list(results)


if __name__ == "__main__":
    for args in [
        ("", 1),
        ("1234", 2),
        ("19216811", 3),
        ("192168111234", 3),
        ("192168111234", 4),
    ]:
        print(period_partition(*args))
        print()


Output:

[]

['1.23.4', '12.3.4', '1.2.34']

['1.92.168.11', '192.16.81.1', '19.216.81.1', '192.1.68.11', '192.16.8.11', '19.216.8.11', '19.2.168.11', '19.21.68.11', '192.168.1.1']

['192.168.111.234']

['192.16.81.11.234', '19.21.68.111.234', '19.2.168.111.234', '192.168.1.112.34', '192.168.11.12.34', '192.168.11.1.234', '192.168.111.23.4', '192.168.1.11.234', '192.1.68.111.234', '192.168.111.2.34', '19.216.81.112.34', '192.16.81.112.34', '19.216.81.11.234', '192.168.11.123.4', '192.16.8.111.234', '19.216.8.111.234', '1.92.168.111.234']


NB:
This is just a toy problem and its connection to valid IP addresses, IPv4 and IPv6, I think, is just to provide constraints on valid octets as periods are assigned. So 1.23.4 is an unbounded string s, "1234", after being partitioned with periods k=2
Use a generative approach

Iterating over all possible permutations and filtering out the invalid ones results in lots of wasted work.  Move the filtering operation earlier so many invalid permutations are not generated in the first place. 

For example, permute() contains for i in range(1, slen + 1), but we know that an octet can only be up to 3 digits long.  Change the loop to for i in range(1, min(4, len(s)+1)). Also, if first is not a valid octet skip the recursive call (none will result in a valid address).

Something like this:

def period_partition(s, k):

    def is_valid_octet(s):
        # section ranges 0 - 255 and `00` or `000`, `01` are not valid but 0 is
        return s == '0' or not s.startswith('0') and 0 &lt; int(s) &lt; 256

    if s and k:
        for i in range(1, min(4, len(s)+1)):
            first, rest = s[:i], s[i:]
            if is_valid_octet(first):
                yield from (f"{first}.{p}" for p in period_partition(rest, k-1))

    elif s and is_valid_octet(s):
        yield s


testcases = [
    ("", 1),
    ("1234", 2),
    ("19216811", 3),
    ("192168111234", 3),
    ("192168111234", 4),
    ("19216811123444", 4),
    ("192168111234444", 4),
]

for s, k in testcases:
    print(f"\nperiod_partition({s!r}, {k})")

    for partition in period_partition(s, k):
        print(f"  {partition}")


Note: I modified period_partition() to be a generator yields all valid partitions.  Use list() if you need an actual list.