Need: Algorithm to determine the smallest subset of all possible test
cases to achieve n-wise coverage of a set of data.
Example:
Variables X, Y, and Z can contain the following values:
X: 1, 4, or 7
Y: 2, 5, 8, 9, or 10
Z: 3, or 6
Calculating all combinations of values produces 30 test cases. The
algorithm should calculate the smallest number of cases to achieve
n-wise coverage.
If n=3 then the smallest number of cases needed for coverage is 30,
and it should specify the cases. They are:
X Y Z
-----------------------------
1 1 2 3
2 1 2 6
3 1 5 3
4 1 5 6
5 1 8 3
6 1 8 6
7 1 9 3
8 1 9 6
9 1 10 3
10 1 10 6
11 4 2 3
12 4 2 6
13 4 5 3
14 4 5 6
15 4 8 3
16 4 8 6
17 4 9 3
18 4 9 6
19 4 10 3
20 4 10 6
21 7 2 3
22 7 2 6
23 7 5 3
24 7 5 6
25 7 8 3
26 7 8 6
27 7 9 3
28 7 9 6
29 7 10 3
30 7 10 6
If n=2 (2-wise or pair-wise), then from the 31 possible combinations
(see below), the algorithm should determine that coverage of all pairs
can be achieved by testing 15 of the cases and should specify which
cases. Note: there can be more than one correct answer. The algorithm
need only specify one, but it should be one that has the lowest number
of cases.
All possible 2-wise combinations
----------------------------------------
1 2 1 3 1 5 1 6 1 8
1 9 1 10 2 3 2 6 4 2
4 3 4 5 4 6 4 8 4 9
4 10 5 3 5 6 7 2 7 3
7 5 7 6 7 8 7 9 7 10
8 3 8 6 9 3 9 6 10 3
10 6
15 cases to achieve 2-wise coverage of all data
--------------------------------------------------------
X Y Z
-----------------------------
1 1 2 3
4 1 5 6
6 1 8 6
8 1 9 6
9 1 10 3
11 4 2 3
13 4 5 3
16 4 8 6
18 4 9 6
20 4 10 6
22 7 2 6
23 7 5 3
25 7 8 3
27 7 9 3
30 7 10 6
So, in summary, I need an algorithm to determine the smallest subset
of all possible cases that will achieve coverage of all n-wise
combinations (where n is equal to a number between 1 and the number of
variables). |
Request for Question Clarification by
mathtalk-ga
on
05 Aug 2003 08:34 PDT
Hi, skah-ga:
As you are probably aware, the problem in the generality you have
stated it is a very difficult one. Even for pairwise and 3-wise
coverage (and flexible numbers/cardinalities of parameters) one is
already in the domain of patented algorithms. See here for an
innovative "Web service" based on practical solutions to such
"simplified" (from your point of view) problems:
[Telecordia AETG Web Service]
http://aetgweb.argreenhouse.com/
One can certainly describe a brute force algorithm for this sort of
thing, with a certain amount of "trimming" of combinatorial paths. I
think a thorough search of the literature to determine what the
state-of-the-art algorithms, even for modest n = 2,3,4, would require
more effort than is commensurate with the list price you are offering.
Nonetheless it's a very interesting question, and I'd be happy to
work with you on this to the extent of describing a brute force
approach with a few "efficiencies" noted.
regards, mathtalk-ga
|
Clarification of Question by
skah-ga
on
06 Aug 2003 09:02 PDT
Quote from mathtalk-ga: "one is already in the domain of patented
algorithms"
The algorithms are patented? Does that mean no one is allowed to use
them or that they just can't be used in 'for profit' applications?
Quote from mathtalk-ga: "with a certain amount of 'trimming' of
combinatorial paths"
What do you mean here, if a brute force method is chosen, we'd have to
limit variables, values, and/or n?
|
Request for Question Clarification by
mathtalk-ga
on
06 Aug 2003 09:38 PDT
Actually what I mean is that, while some special cases are known to
have efficient or even explicit solutions for n = 1,2,3, only "brute
force" algorithms are known for general n, which is what you asked
about.
By "trimming" I mean to propose something a bit more clever than
"Check all subsets of the Cartesian product, and pick one of least
cardinality." For example, if lower and upper bounds on the
cardinality of a minimal subset can be given, then "search" can be
constrained to consider only subsets within that range.
As to what the implications of "patenting" an algorithm are, I would
have to disclaim any special legal knowledge. This seems to me a
recently evolving area of patent law, so standards are probably not
well settled.
However the patenting of an algorithm should probably be considered as
a claim on the rights to license it, at least in the context of a
particular process (here, the selection of test cases). Whether the
use is private or commercial is theoretically not the main criterion,
though of course an unlicensed commercial use of patented procedures
would be most likely to draw complaints in practical terms.
The good news is that one can read the patent claim for oneself (it's
a public document) and benefit from its account of the novel and prior
art involved. I would be happy to post a link with some comments as
part of an answer.
regards, mathtalk-ga
|
