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?

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
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
Out of curiosity: what *advantages* does your team see in this design? — Joachim Sauer, May 28 '13 at 12:20
Java naming conventions are CamelCase for class names and camelCase for variable names. — Tulains Córdova, 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 03 '13 at 20:00

score 95 · Answer 1 · edited May 23 '17 at 11:33

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

it's not even object denial it's data structure denial – jk. May 28 '13 at 11:55 — jk., May 28 '13 at 11:55

score 22 · Answer 2 · answered May 28 '13 at 11:32

22

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

answered May 28 '13 at 11:32

Telastyn

108,850
29
239
365

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
@MichaelBorgwardt: yes, I've seen it, and it's quite interesting. Personally, if I'd been forced to do this kind of thing, I'd still prefer this solution here. – Joachim Sauer May 28 '13 at 12:28

score 16 · Answer 3 · answered May 28 '13 at 12:24

16

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

answered May 28 '13 at 12:24

Michael Borgwardt

51,037
13
124
176

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
ye gods, why would you re-arrange 3+ collections in place (and all of the copies involved) rather than my answer which is one shuffle and direct access (unless you're constrained to use non-direct access collections of course). For any non-trivial collection size I have to think that's decidedly less performant for little benefit. – Telastyn May 28 '13 at 13:58
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
The example is fairly rough or naïve in any case. As it is probably not an ideal general solution, an ideal shuffling process is probably not necessary. Simplicity looks to be the driving force. – JustinC May 28 '13 at 23:21

score 3 · Answer 4 · answered May 28 '13 at 11:36

3

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.

answered May 28 '13 at 11:36

Doc Brown

199,015
33
367
565

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

codingFriend1 · Answer 5 · 2013-05-29T08:00:50.697

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.

http://www.codinghorror.com/blog/2007/12/the-danger-of-naivete.html — the_lotus, May 28 '13 at 15:19

Efficient way to shuffle objects

5 Answers5

Linked