Efficient way to shuffle objects

Question

I'm writing a program for some quiz software. I have a question class containing the ArrayLists for the question, answer, options, marks and negative marks. Something like this:

class question
{
    private ArrayList<Integer> index_list;
    private ArrayList<String> question_list;        
    private ArrayList<String> answer_list;      
    private ArrayList<String> opt1_list;        
    private ArrayList<String> opt2_list;    
}

I want to shuffle all questions, but for questions to be shuffled, all the objects need to be shuffled. I would have approached this problem in this way:

First of all, I would not have used this design and used String not ArrayList<String> type as instance variables, and would then have used the Collections.shuffle method to shuffle objects. But my team insists on this design.

Now, the question class is containing increasing ArrayLists as the entry to the questions are made. How to shuffle the questions now?

Answer 1

Your team suffers from a common problem: object denial.

Instead of a class that holds a single question with all the information associated with it, you try to create a class called question that holds all the questions in a single instance.

That's the wrong way to go about it, and it complicates what you try to do a lot! Sorting (and shuffling) parallel arrays (or Lists) is nasty business and there's no common API for it, simply because you usually want to avoid it at all.

I suggest you restructure your code like this:

class Question
{
    private Integer index;
    private String question;        
    private String answer;      
    private String opt1;        
    private String opt2;    
}

// somewhere else
List<Question> questionList = new ArrayList<Question>();

This way, shuffling your question becomes trivial (using Collections.shuffle()):

Collections.shuffle(questionList);

Answer 2

You don't. You make another list/queue of indexes and shuffle that. Then you iterate down the indexes which drive the "shuffled" order of your other collections.

Even outside of your scenario with things split apart, the separate ordering collection provides a number of benefits (parallelism, speed when reseating the original collection is costly, etc).

Answer 3

I agree with the other answers that the correct solution is to use a proper object model.

However, it is actually quite easy to shuffle multiple lists in identical manner:

Random rnd = new Random();
long seed = rnd.nextLong();

rnd.setSeed(seed);
Collections.shuffle(index_list, rnd);
rnd.setSeed(seed);
Collections.shuffle(question_list, rnd);
rnd.setSeed(seed);
Collections.shuffle(answer_list, rnd);
...

Answer 4

Create a class Question2:

class Question2
{
    public Integer index_list;
    public String question_list;        
    public String answer_list;      
    public String opt1_list;        
    public String opt2_list;    
}

Then create a function mapping a question to ArrayList<Question2>, use Collection.Shuffle for that result, and create a second function for mapping ArrayList<Question2> back to question.

Afterwards, go to your team and try to convince them that using an ArrayList<Question2> instead of question would improve their code a lot, since it would save them a lot of that unnecessary conversions.

Answer 5

My original naive and wrong answer:

Just create (at least) n random numbers and interchange item n with item i in a for loop for each list you have.

In pseudo code:

for (in i = 0; i < question_list.length(); i++) {
  int random = randomNumber(0, questions_list.length()-1);
  question_list.switchItems(i, random);
  answer_list.switchItems(i, random);
  opt1_list.switchItems(i, random);
  opt2_list.switchItems(i, random);

}

---

Update:

Thanks for the_lotus for pointing out the coding horror article. I feel much smarter now :-) Anyway Jeff Atwood also shows how to do it right, using the Fisher-Yates algorithm:

for (int i = question_list.Length - 1; i > 0; i--){
  int n = rand.Next(i + 1); //assuming rand.Next(x) returns values between 0 and x-1
  question_list.switchItems(i, n);
  answer_list.switchItems(i, n);
  opt1_list.switchItems(i, n);
  opt2_list.switchItems(i, n);
}

The main difference here is that each element is swapped only once.

And while the other answers correctly explain that your object model is flawed, you might not be in the positioin to change it. So the Fisher-Yates algorithm would solve your problem without changing your data model.