Filter out unwanted substrings while generating all possible relevant substrings

Question

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 <= int(s) <= 255)
 def permute(s):
 if len(s) > 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

• Peilonrayz: An IPv4 address is a 32 bit number, "1.23.4" is a 24bit number and "192.16.81.11.234" is a 40 bit number. It's not IPv6 because your output is neither a 128 bit number or using colons. 1 Please can you provide the source for this problem. 2 Does the code work the way the problem specifies?
• Brayoni: This is just a toy problem and its connection to valid IP addresses, IPv4 and IPv6, is just to provide constraints on valid octets as periods are assigned. Please see update to the question. So 1.23.4 is an unbounded string s, 1234, after being partitioned with periods k=2
• Peilonrayz: Ok, that makes sense. Please could you edit your question to add that.
• Peilonrayz: As an aside I'm not sold on the validity of the book you're reading. I would take care to not trust the book too much. The following sentence is misleading at best and wrong at worst. "The total number of IP addresses is a constant (\2ドル^{32}\$), implying an \$O(1)\$ time complexity for the above algorithm."
• Alex Hall: I copy pasted your code and got a RecursionError. I'm pretty sure your slen = len(s) at the beginning is a bug, since you use slen where you probably want the length of a string other than the outer s.

Answer 1

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 < int(s) < 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.