Sign in to follow this  

Sorting: Need a push in the right direction.

This topic is 4341 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I have a college assignment to do and I don't want someone to just tell me what to do, I just want a push in the right direction. I think this has to do with sorting, I may be competly wrong though. There are two houses in the School, Red and Yellow. Each student belongs to one. The students are then split into classes, with students from both red and yellow house mixed into them. There are also four board games to play. The rules are: - Each student should play one match (best out of three rounds) for each game. - Students can't play students from the same house or from the same class. - Students can only play another student once. The task is to prepare the list of matches. So each student will play a maximum of 12 rounds (3 max per match), now how would I sort the list? What technique? Would something recursive work for this? Thanks for looking :)

Share this post


Link to post
Share on other sites
My friend Joe works at a Puzzle Assembly Plant. He's part of an expert Puzzle Assembly Team. These puzzles are really tricky because pieces can fit in more than one location. It's often very difficult to see what the appropriate place is for a piece to be in. Luckily, the puzzles only have ten pieces in them, to be placed in ten different locations.

Joe's job, specifically, is Fifth Piece Placer. His one and only job is to place the fifth piece into a partially constructed puzzle. He works for Fourth Piece Placer, and the Sixth Piece Placer works for him.

His job goes like this. Fourth Piece Sorter will give him a puzzle with four pieces placed in it. Maybe they're placed correctly, maybe they aren't. Joe's job is to place the fifth piece. He has no way of knowing whether he's putting it in the right place or not. So what he does is, he just places it in the first empty spot. Then he hands the puzzle off to Sixth Piece Sorter, who takes it from there. Sometimes (usually), Sixth Piece Sorter will come back to him with a fifth-piece-placed puzzle and say "Boss, this placement didn't work out. Try a different one." Joe will then try putting the fifth piece in the next empty spot, and give it to Sixth Piece Sorter again. And if Sixth Piece Sorter isn't happy with that one either, Joe will put it in the next spot.

There are two problems Joe can encounter. The first problem is if Fourth Piece Sorter gives him a puzzle which is wrong. In that case, he will hand the puzzle right back to Fourth Piece Sorter, saying "Boss, this placement didn't work out. Try a different one." Also, sometimes he'll try the fifth piece in all the empty spots, and each time, Sixth Piece Sorter will say "Boss, this placement didn't work out. Try a different one." Again, if this happens, Joe knows that the placement of the first four pieces must be wrong, so he hands the puzzle back to Fourth Piece Sorter, saying "Boss, this placement didn't work out. Try a different one."

Joe and his team aren't very fast, but they get the puzzles assembled eventually. In fact, in certain cases, they don't do any worse than more intelligent puzzle assemblers.

The other members of his team are also named Joe.

Share this post


Link to post
Share on other sites
Ok now I've kinda figured out what to do:

I have a class/struct (if I use c++) or type (if I use VB6) for each student. It contains the name, class and house of the student.

For each student I loop through the other students checking if they are in the same class/house etc. and if that is all fine I add them as an opponent until I get to 12 oppenents and then start on the next student.

Does this sound liek the way to go?

Share this post


Link to post
Share on other sites
Quote:
Original post by Sneftel
...
Nice story. Can we see one for IntroSort, with threshold at 8 items? [grin]

@mengha: Really, if time is no factor, brute force it how Sneftel "pushed". If you want to do something fancy, I'll say that Wikipedia has pretty decent articles of sorting algorithms, and I'll also say that if you learn something from someone else's teachings, and you understand it, that's probably not a Bad Thing. Not that you were suggesting otherwise.

Share this post


Link to post
Share on other sites
Quote:
Original post by Sneftel
My friend Joe works at a Puzzle Assembly Plant.

...

The other members of his team are also named Joe.
Oh man, the plot twists, the suspense![grin]
Very nice, well written actually. A good push.

It sounds like you're catching on mengha.

Share this post


Link to post
Share on other sites

This topic is 4341 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this