[darcs-users] Delta Debugging

[Kenneth Knowles]

On Mon, May 24, 2004 at 07:12:32PM -0400, Andrew Pimlott wrote:
> Oh dear, I meant that b is (4, 5, 6, 7, 8).  Sorry.  I mixed this up
> with another example.

Ah, yes.  In that case we have the problem of not being able to split the input
into patch sets that will build.  But if we leave one half applied when
increasing granularity, as in dd+, we get this:

1 2 3 4 5 6 7 8
---------------
1 2 3 4         ?
        5 6 7 8 ?
1 2     5 6 7 8 ?
    3 4 5 6 7 8 ?
1       5 6 7 8 ?
  2     5 6 7 8 ?
    3   5 6 7 8 ?
      4 5 6 7 8 P

... and then we want to know to check the complement

1 2 3           F

But then I've hardly given a complete algorithm...

I don't have much time right now, but I'm thinking that this could be leveraged
in a useful manner.  Of course, always finding a truly minimum set can't be done
without 2^n complexity; but this example of yours is not at all inconceivable,
and we'd want to find it.

Kenn