How to make a controled "shuffle" order?

Question

I have a set of quiz game questions in a sql database (javascript and sqlite actually). The questions all have a difficulty level from 1 to 5, 5 being hardest. Here is a simplified visualization of the data...

+---------+--------------+  
|   id    | difficulty   |   
+---------+--------------+  
| 1       |      1       |    
| 2       |      5       |    
| 3       |      2       |    
| 4       |      3       |    
| 5       |      2       | 
| 6       |      2       |    
| 7       |      4       |    
| 8       |      1       |    
| 9       |      5       |    
| 10      |      3       |      
+---------+--------------+   

Now I can shuffle these fine in sql or code so they are in a random order with no repeats but I also want to have control over the way the difficulty field is ordered.

So for instance I could have a shuffled set of question where the difficulty level order looks like this...

1,1,5,2,3,3,2,2,2,4

This has several 'clumps' of difficulty, that's not what I want. The user playing the game would get several groups of the similarly difficult questions. An order like this would be better...

1,2,3,2,5,4,1,2,3,2

I want to ensure the questions are shuffled but without difficulty clumping. An even spread of difficulty where there are few, if any 'clumps'. Any help on the MySQL/javascript (or PHP) would be great.

Answer 1

Well in a truly random sample 'clumps' do naturally appear. So if you want to remove these you have to enforce something manually, e.g. specify a pattern of difficulty and choosing a random question matching each difficulty level

Answer 2

Instead of grouping all the ids together why don't you group them by difficulty randomize each section and then pull them out one by one. Or once they are randomly sorted you could pull them from a random difficulty, then remove that difficulty level until you have a question from each.

This is what I was thinking about in answer to sje397, so I'll add it to my answer.

As long as all the other choices add up to the largest group minus one you will have no clumping (assuming your algorithm is correct). However, the algorithm would basically take the form of pick from A (group with greatest number of choices), pick from another group, pick from A etc. until A is equal to the size of the other groups. So the best algorithm would check to find the largest group and pick from it. It would then pick from another group, then check to see what group is the largest, then choose from it unless it is the previously chosen one etc.

Answer 3

Iterate through a randomly-shuffled input array and whenever you hit an element with the same difficulty level as the one before it, swap with the next element that doesn't have the same difficulty level. Just in my head, I think that this would turn your initial input into: 1,5,1,2,3,2,3,2,4,2

Depending on the input, this approach might cause clumping at the end but might be good enough...

If your input is bigger than what you need, you could also just remove any element that has the same difficulty as the one before it.

Answer 4

How about the following strategy, in code: (the following was a bulleted list, but I couldn't get code appearing after a bulleted list to display correctly - I thoroughly detest this "markdown" garbage this site uses)

order the questions by difficulty

split the questions halfway into two lists, an "easy" list and a "hard" list

take questions one by one from the easy and hard lists, alternating between the two. (This would mean that you would have a slight trend from easy to difficult over the sequence of questions, which you might or might not be OK with.)

Primitive implementation:

$resultset = your_preferred_query_function('SELECT id FROM question ORDER BY difficulty');
$questions_temp = array();
while ( $row = mysqli_fetch_assoc() ) {
    $questions_temp[] = $row['id'];
}
if ( count($questions) % 2 ) {
    $loop_limit = (count($questions) - 1) / 2;
    $halfway = (count($questions) + 1) / 2;
    $questions[0] = $questions_temp[$loop_limit];
} else {
    $loop_limit = count($questions) / 2;
    $halfway = count($questions) / 2;
    $questions = array();
}
for ($i=0; $i<$loop_limit; $i++) {
    $questions[] = $questions_temp[$i];
    $questions[] = $questions_temp[$halfway+$i];
}

Now $questions is an array containing questions ordered as I suggested.

Answer 5

A very simple solution (it's not very efficient though) would be to do:

<?php

        define('MAX_QUESTIONS',10);

        $dbh = new PDO("mysql:dbname=so;host=127.0.0.1","","");
        $sql = "SELECT * FROM q group by difficulty order by rand()";
        $data = $dbh->query($sql);
        $rows = $data->fetchAll();
        $ids = getIds($rows);
        while (count($rows) < MAX_QUESTIONS ) {
                $sql = "SELECT * FROM q where id not in ".
                       "(".join(",",$ids).") group by difficulty order by rand()";
                $data = $dbh->query($sql);
                $more_rows = $data->fetchAll();
                $rows = array_merge($rows,$more_rows);
                $ids = getIds($rows);
        }
        print_r($rows);

        function getIds($data) {
                $ids = array();
                foreach ($data as $v) {
                        $ids[] = $v['id'];
                }
                return $ids;
        }

?>

This is needed because MySQL's group by always return the same ids, regardless of if you've ordered previously (even in a subquery.)

The good thing about this is that it guarantees no 'clumps' (at the potential cost of returning empty for the final question that would create a 'clump', you could special case that, though)

The bad thing is that you need more than a single query, and that ordering by rand() is awfully inefficient, but if your table is small it probably won't actually matter.