从一组属性重建位序列

Question

我想根据给定的 ones 集合、数字 x 和其他属性重建一个位序列。在位序列中，第一位的值为 1，第二位的值为 2，第三位的值为 3，等等

例如我有以下属性：

x=15（设置位所有值的总和）

位序列长度：8

所有子序列中 1 的计数：2

1 个子序列的计数：1

序列长度：2

所以解是11000000。

解可以不止一种，我对所有解都感兴趣

如何有效地找到具有给定属性的解决方案？

Answer 1

这是一个小背包问题

这是 Python 中使用迭代器的解决方案。使用迭代器的原因是答案的数量可能非常大。例如，有 15029 个位序列加起来为 100，长度为 20。并且呈指数增长。

# Finds all answers and puts it in an compact but complex data structure.
def find_subsum_path_tree(target, array):
    # For each value, we will have an array of trees of how to get there.
    # The simplest tree is the empty sum, None
    paths_to = {0: [None]}
    for val in array:
        new_paths_to = {}
        for key, prev_paths in paths_to.iteritems():
            # Take care of initialization.
            if key not in new_paths_to:
                new_paths_to[key] = []
            if key + val not in new_paths_to:
                new_paths_to[key + val] = []

            # We have ways to get to key without using val
            new_paths_to[key] = new_paths_to[key] + prev_paths
            # We have ways to get to key+val with using val.
            #
            # NOTE: our data structure here will look like:
            #     [
            #         prev_tree_1,
            #         prev_tree_2,
            #         ...
            #         prev_tree_n,
            #         [val, [
            #             prev_path_1,
            #             prev_path_2,
            #             ...
            #             prev_path_m
            #         ]]
            #    ]
            #
            # This encodes a lot of options.  In data structures that get
            # reused.  So there can be a lot of paths, but this is not a
            # lot of data.
            new_paths_to[key + val] = new_paths_to[key + val] + [[val, prev_paths]]
        paths_to = new_paths_to
    if target in paths_to:
        return paths_to[target]
    else:
        return []

# Turn the complex tree into arrays recursively.
# With iterators so it doesn't live in memory all at once.    
def subsum_paths(target, array):
    tree = find_subsum_path_tree(target, array)

    def path_decode(subtree):
        if subtree[0] is None:
            yield []
        else:
            for option in subtree:
                value, rest = option
                for subpath in path_decode(rest):
                    yield [value] + subpath

    for path in path_decode(tree):
        yield path

# Use the previous knapsack solution to find bitsequences as desired.
def bitsequences(target, length):
    for path in subsum_paths(target, range(1, length + 1)):
        bits = ['0' for _ in range(length)]
        for n in path:
            bits[length - n] = '1'
        yield "".join(bits)

# And a demonstration of how to use this code.    
for sequence in bitsequences(15, 8):
    print(sequence)

从一组属性重建位序列

Reconstruct bitsequence from a Set of properties

arrays

algorithm

bit-manipulation

permutation

integer-partition