binary_string_permutations.py

"""
Given a string of 0s, 1s and ?s (wildcards), generate all 0-1 strings that match this pattern, e.g. 
1?00?101 -> [10000101, 10001101, 11000101, 11001101]. You can generate strings in any order that suit you.
"""


class Tree(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


def binary_string_permutations_recursive(inputstr, node):
    if len(inputstr) == 0:
        return node

    node = Tree(None)
    val = ""
    i = 0
    while i < len(inputstr):
        if inputstr[i] == "?":
            node.val = val
            node.left = binary_string_permutations_recursive("0" + inputstr[i+1:], node.left)
            node.right = binary_string_permutations_recursive("1" + inputstr[i+1:], node.right)
            i = len(inputstr)
        else:
            val += inputstr[i]
        i += 1
    node.val = val
    return node


def path_from_root_to_leaf(root, path, all_paths):
    if root is None:
        return path
    if root.left is None and root.right is None:
        path.append(root.val)
        all_paths.append(path)
        return path

    path.append(root.val)
    path = path_from_root_to_leaf(root.left, path, all_paths)
    path = path[:-1]
    path = path_from_root_to_leaf(root.right, path, all_paths)
    path = path[:-1]
    return path


def binary_string_permutations(inputstr):
    result = None
    result = binary_string_permutations_recursive(inputstr, result)
    all_paths = []
    path_from_root_to_leaf(result, [], all_paths)
    output = []
    for path in all_paths:
        tmp = "".join(path)
        output.append(tmp)
    return output

import unittest


class TestBinaryStringPermutations(unittest.TestCase):
    def test_get_string_permutation_simple(self):
        out = "10?0"
        expected = ["1000", "1010"]
        actual = binary_string_permutations(out)
        result_set = set(actual)
        actual = sorted(list(result_set))
        self.assertEqual(len(actual), len(expected))
        i = 0
        isvalid = True
        while i < len(actual):
            if actual[i] not in expected:
                isvalid = False
            i += 1
        self.assertEqual(True, isvalid)

    def test_get_string_permutation_complex(self):
        out = "1?00?101"
        expected = sorted(["10000101", "10001101", "11000101", "11001101"])
        actual = binary_string_permutations(out)
        result_set = set(actual)
        actual = sorted(list(result_set))
        self.assertEqual(len(actual), len(expected))
        i = 0
        isvalid = True
        while i < len(actual):
            if actual[i] not in expected:
                isvalid = False
            i += 1
        self.assertEqual(True, isvalid)

if __name__ == "__main__":
    unittest.main()