What is a scalable way to count the number of n-digit numbers (in mixed radix) that meet a list of different digit criteria? I asked the question from a mathematical point of view here but the focus there is on the methematics of the problem without as much concern for the practicality of actually computing the number. I know that this is a problem that scales exponentially, but I should still be able to generate some sort of solution and am interested in where the limit of computability is for this -- the method that one uses will determine that limit. Here is a small version of the problem that calls a black-box function to compute the answer. >>> n = 3 >>> bases = [3, 4, 2] # Bases for each digit >>> patterns = [ ... [(0, 0), (2, 1)], # Matches numbers like 0x1 where x is any digit ... [(1, 3)] # Matches numbers like x3y ... ] >>> >>> result = count_matching_numbers(n, bases, patterns) # should be 9 The goal is the count, but for reference, here are the solutions (and it is fine if the solutions can easily be computed as a byproduct of doing the count): [0, 0, 1], [0, 1, 1], [0, 2, 1], [0, 3, 0], [0, 3, 1], [1, 3, 0], [1, 3, 1], [2, 3, 0], [2, 3, 1]] To give a feel for the limits that I am aware of right now, in a larger system there are, say, 10440 unique patterns (without supersets, ranging in length from 3 to 10 for a 10 digit number having bases for each digit that are [7,6,6,6,7,7,4,7,5,5]). The count of numbers permitted by the patterns is 17306863. I have a non-brute force solution that takes 20 seconds by counting up the indices of the numbers permitted by each solution while removing duplicates. Using the matrix method (brute force using numpy) takes about 0.2 seconds; but the brute force method is going to run out of memory as the system sizes increases. When I tried using polynomial generating functions, the bottle neck is computing all the combinations of patterns to be used in an inclusion-exclusion count. That just can't be done with a problem this size. Prefix trees with the pattern was also very slow and they are especially not of interest if they mean generating all numbers and then testing in the tree to see if they work or not. Any other ideas? And is there any other tag that might be more receptive to a discussion of this problem? Downvotes are reaching critical mass here. Continue reading...
