Introduction

Let's consider binary numbers for simplification and let's consider 4 bits numbers. Sets which answer my problem are:

a) 1001
   0110
b) 0000
   1111
c) 0001
   0010
   1100

So for each bit, in a number or another of the set, we find each possible value, does not matter in which number. From the above wee see that:

• the solution may not be unique
• minimum set has 2 numbers
• solution c) may by a minimum set for the given conditions, see below.

Additional aspects:

1. It possible that the given set does not contain all the 4 bit 16 numbers and because of that:

• the minimum set may be bigger than 2 numbers;
• there could be no solution, in which case is still useful a solution which covers as more bit values.

For example, for a given set:

0000
0001
0010
0100

a best partial solution is

0001
0010
0100

2. I am interested in the fastest algorithm - O(N) I'm sure is not possible, O(logN) would be nice.
3. I took binary numbers as example but the problem can be extended to decimal numbers and even to situations more general where, let's say, digit 0 can have 4 values, digit 1 can have 100 values, digit 2 can have 11 values, etc.
4. I highlight that I am not interested in covering all the combinations of the bits but to make sure that each bit will have each possible value, in a number of another.
5. I don't know which branch of mathematics this problem belongs to so I would be happy to find out.
6. Is it there already a known such problem, study, a theorem maybe?
7. As a background information, I am software developer and this is for testing purposes. I have some already written tests for some application and these tests cover some testing conditions. I wonder how to pick minimum set of tests to prove the behavior for different parameters or conditions. Again, I mention that I am not interested now in all the combinations of parameters. Just to make sure that the application was tested when that parameter has different values, that parameter has different values etc. But the Idea is to test for multiple parameters with as few tests as possible. For the example of binary 4 bit numbers, a complete set, a set which covers all the bits, can't be bigger than 4 so I don't need 8 tests, one for each vale of each bit but it would be nice to reduce it even more. This is because the problem grows with the number of parameters and the number of parameter values.