Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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?

share|improve this question
30  
I hate to talk in absolutes, but if your team insists on this design, then they are wrong. Tell them! Tell them that I said so (and I wrote it on the Internet, so I have to be right). –  Joachim Sauer May 28 '13 at 11:31
10  
Yes, tell them that there are a lot of people here telling you that this kind of design is a typical beginners mistake. –  Doc Brown May 28 '13 at 11:40
6  
Out of curiosity: what advantages does your team see in this design? –  Joachim Sauer May 28 '13 at 12:20
9  
Java naming conventions are CamelCase for class names and camelCase for variable names. –  user61852 May 28 '13 at 12:21
    
I think you need to confront your team about this terrible design decision. If they continue to insist, find out why. If it's just stubbornness, perhaps start thinking about finding a new team in the not too distant future. If they do have reasons for this structure, then consider those reasons on their merits. –  Ben Lee Jun 3 '13 at 20:00
add comment

5 Answers

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);
share|improve this answer
37  
it's not even object denial it's data structure denial –  jk. May 28 '13 at 11:55
add comment

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).

share|improve this answer
10  
I'm reluctant to vote this up: it's the next-best solution iff this design is indeed fixed, but insisting on this design is so wrong, that I wouldn't want to give any suggestions about it. (meh, upvoted anyway ;-)) –  Joachim Sauer May 28 '13 at 11:35
3  
@joachimSauer - while I agree, there are plenty of other (less offensive) scenarios where the original collection must remain static while the path through them needs to vary. –  Telastyn May 28 '13 at 11:38
4  
yes, I know. And shuffling a collection of indices is the correct approach for those situations. My only fear is that the OPs team will just take this and say "good enough", without re-viewing their design. –  Joachim Sauer May 28 '13 at 11:46
1  
This Answer is valuable especially for the case where one does not have the freedom to revise/recode the underlying collection class or structure, e.g. one has to make do with an API to an OS maintained collection. Shuffling the indices is a great insight and stands by itself even if it's not as keen an insight as redoing the underlying design. –  hardmath May 28 '13 at 12:13
    
@Joachim Sauer: actually shuffling the indices is not necessarily the best solution to the problem as stated. See my answer for an alternative. –  Michael Borgwardt May 28 '13 at 12:27
show 1 more comment

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.

share|improve this answer
1  
This is a good idea, but only after a-priori attempts to change the design have failed. –  Sebastian Redl May 28 '13 at 11:45
    
@SebastianRedl: sometimes it is easier to convince people of a better design when just showing them the solution in code. –  Doc Brown May 28 '13 at 11:59
add comment

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);
...
share|improve this answer
    
That's ... a neat way to do it! Now, for the "sorting" case we just need to find a seed that produces a sorted list when applied this way and then we shuffle all lists with this seed! –  Joachim Sauer May 28 '13 at 12:26
1  
@JoachimSauer: well, sorting was not part of the problem. Though it's an interesting question whether there is a systematic way to find such a seed for a given RNG. –  Michael Borgwardt May 28 '13 at 12:30
2  
@MichaelBorgwardt once you get over 17 questions you simply can't express the amount of possible shuffles in the 48 bits the java Random uses (log_2(17!)=48.33) –  ratchet freak May 28 '13 at 12:54
    
@ratchetfreak: doesn't sound like a real problem to me. And it's trivial to use SecureRandom instead if you must. –  Michael Borgwardt May 28 '13 at 13:14
4  
@Telastyn: the list of indexes is IMO a layer of indirection that makes your solution conceptually more complex, and whether it's more or less performant depends on how often the lists are accessed after the shuffle. But performance differences would be insignificant given realistic sizes for a quiz to be answered by humans. –  Michael Borgwardt May 28 '13 at 14:30
show 2 more comments

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.