Let’s say I have a question pool to generate exams out of it. Each question contains a difficulty from 1 (hard) to 99 (easy). The questions are available in a hash / array (adapt to your favorite languages naming, I’m going with hash as it is a ruby implementation) in the following format:
questions = {
:55 => [<#Question 1>, <#Question 18>],
:8 => [<#Question 70>],
:43 => [<#Question 105>]
}
The hash keys denote the difficulty, whereas the value is a list of questions with said difficulty.
The aim is to be able to create an “exam” with N questions from the pool. Each exam generated should contain questions from “all” difficulty levels (not from each number, but having questions with lower, medium, and higher ratings). Also, each exam generated should have +/- the same difficulty X (e.g. 75).
How do you go about selecting questions from various difficulties so you have a) a result of N size and b) matching the average difficulty of X?
1
You’re imposing three constraints here:
- a specific total number of questions
- several pools of questions of similar difficulty, where the exam should contain elements of each pool
- a predefined average difficulty
As ratchet freak said, this is a knapsack problem and therefore hard to solve, although if the list of questions is reasonably small a complete search can still work.
However, if you’re willing to have the average difficulty vary a bit more, you could simply choose a predefined number of questions randomly from each pool, which requires only linear effort and will almost always yield a near-average total difficulty. Possibly, even a try-until-satisfactory approach is cheaper than the original problem.
1