# How to determine the optimal permutation to get to a result with the minimum steps

I am not a mathematician. I need to be able to frame my problem so I would like guidance on what type of problem this is and perhaps guidance on how to solve it.

I have patients with food allergies. I need to find what they are allergic to. I normally ask the patient to exclude all food types, perform a test to confirm their allergic response has gone and then reintroduce one food type at a time, testing at each reintroduction.

They are usually allergic to one of 6 possible food types. The probability of being allergic to each food type is as follows (we assume the probability of having one allergy is independent of the others)

fish 0.3
egg 0.2
soya 0.3
milk 0.6
wheat 0.4
rye 0.1


The idea of excluding all the foods and then reintroducing one at a time is probably a bit inefficient so I could follow an alternative structure such as remove one at a time and then retest, or remove two at a time, or remove all and then reintroduce two a time etc.

The problem I have is how do I determine the best reintroduction or exclusion path using which food types to determine which food type the patient is allergic to with the smallest number of steps.

Hopefully this is clear. I have a feeling someone may mention a Travelling Salesman type solution but is this correct and how would I incorporate probabilities into this? I am comfortable with R if a solution is provided in this format.

With $6$ foods, we have $2^6 = 64$ possible states the patient can be in, corresponding to all subsets of that set of foods: a patient's state is the set of foods that patient is allergic to. Each state $i$ has a certain probability $p_i$, the sum of which is $1$. Now our knowledge of the patient's state at any time corresponds to a set of states: these are the states that are possible for this patient, given the tests that have been done. At the beginning, all $64$ states are possible, and at the end you want to narrow it down to only one. You say you want to do this as quickly as possible, by which I interpret you want to minimize the expected number of tests performed.
A test will consist of administering a certain set $T$ of foods and seeing if there is an allergic response. If there is, we know the patient is allergic to at least one of the foods in $T$, so we can eliminate all states disjoint from $T$. On the other hand, if there is no allergic response, we know the patient is not allergic to any food in $T$, so we can eliminate all states that intersect $T$. We can always do it in $6$ tests (just testing one food at a time), but it may be possible to do better. I suspect it may be possible to find an optimal solution with a dynamic programming approach. Alternatively, a useful heuristic may be to choose a test where the probabilities of the two alternatives are as close to equal as possible.