Enumerating all strings meeting given restrictions
-
06-07-2019 - |
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?
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:
- 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)
- For each 24-bit number with n bits set, iterate over all n-bit numbers
- 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
OTHER TIPS
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
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;
}
}