Enumerating all strings meeting given restrictions

Question

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?

Answer 1

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

Answer 2

If you only need to solve this once, perhaps you could just brute force it and put the results in a lookup table in your application. There's less than a trillion 24 bit sequences of 0,1,-1 to check.

If perhaps I'm doing my math wrong or you need to dynamically solve the problem at run time, I would consider the problem as a system of 24 variables each limited to -1, 0 ,1 and approach it as a Constraint Satisfaction Problem, assuming you can enumerate your constraints in some way. My concern, however, is that since you require seeing all solutions and not just a subset, you may still be stuck exhaustively searching the problem space.

This paper seems right up your alley: Enumerating All Solutions for Constraint Satisfaction Problems. Though I don't have access to the full text of the paper to see if it helps.

I may be barking up the wrong tree all together, but perhaps this is a starting place

Answer 3

A completely seperate answer from my last, as working code tends to trump links to research papers, I found this code at Physics Forum and can not take credit for it myself, I just fixed it up so it compiled under g++ and changed to constants to look for 8 bits in 24. It very quickly enumerates all 24 bit strings with 8 bits on, and there are only about 735,000 of these. These 'templates' show the only valid patterns for your non-zero characters. You'd then have to take each of these 735,000 answers and throw around the -/+ signs and decide if each meets you criteria, but this way you are starting from 735k possible solutions instead of 200 Billion.

#include <stdio.h>

 int main()
 {
 int size = 24;
 int pop = 8;

 int n = ((1 << pop) - 1) << (size - pop);

 while(true) {
    printf( "%x\n",n);

    int lowest = n & -n;

     if(lowest > 1) {
        n = n ^ lowest ^ (lowest >> 1);
        continue;
     }

     int high = n & (n + lowest);
     if(high == 0) break;

     int low = n ^ high;

     low = (low << 2) + 3;

     while((low & high) == 0) low <<= 1;
     n = high ^ low;
  }
 }