algorithmstringenumerationcombinatorics

Enumerating all strings meeting given restrictions


I'm looking for the name of the following class of problem, so that I can google for effective algorithms and more information.

I have an alphabet with three characters {-1, 0, 1}.

I need to effectively generate all strings of length 24 which are mostly {0} but have zero to eight {1,-1} characters distributed in certain patterns. (The patterns involve restrictions on the number and pairings of {-1}). The total number strings that meet my criteria are quite modest: about 128,000.

So what is the name for this class of problem/algorithm?


Solution

  • I'm not sure there's a well-defined "algorithm class" for this this; it's just an exercise in combinatorics. You can do the generation in three steps:

    1. Generate all 24-bit numbers with 8 or fewer bits set (you may be able to speed this up a bit if you precompute some lookup tables)
    2. For each 24-bit number with n bits set, iterate over all n-bit numbers
    3. If the kth bit of the n-bit number is 0, then the kth set bit of the 24-bit number prints as -1, otherwise it prints as 1

    To explain steps 2-3 a bit better say your 24-bit number has 4 bits set and looks like

    0 0 0 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0
    

    Then, we iterate over all 16 4-bit numbers from 0 0 0 0 to 1 1 1 1, and, for example:

    0 0 0 0 gives the string  0 0 0 -1 0 0 0 0 0 0 0 0 -1 -1 0 0 0 0 0 -1 0 0 0 0
    0 1 1 0 gives the string  0 0 0 -1 0 0 0 0 0 0 0 0  1  1 0 0 0 0 0 -1 0 0 0 0
    0 1 0 0 gives the string  0 0 0 -1 0 0 0 0 0 0 0 0  1 -1 0 0 0 0 0 -1 0 0 0 0
    1 1 1 1 gives the string  0 0 0  1 0 0 0 0 0 0 0 0  1  1 0 0 0 0 0  1 0 0 0 0