sort rows apart from each other

flexgrip

I know how to do basic sorting according to id number or alphabetical sorting based on, say, the last name of a person. I also figured out how to sort using criteria from multiple tables, but I am curious the method someone would use to sort rows away from each other. Let me explain.

Let's say I have a database for a grade school musical act. I have 20 students. So I put them in the database for each act they are in.

Let me just give you an example table and what I would want the output to be.

So here is my table of students and the acts they are in.
id - name - act_number
1 - bobby - 1
2 - sue - 1
3 - bobby - 2
4 - kim - 3
5 - larry - 4
6 - mark - 5
7 - tommy - 6
8 - edward - 7
9 - nathan - 8
10 - scotty - 9
11 - henry - 9
12 - scotty - 10
13 - rick - 10

I basically want to sort this list to produce the nights schedule. If one kid is in back to back acts then he wouldn't have time to change, so we cant have that. If I were to sort the act numbers ascending then they would go 1-10. But that would place bobby in back to back acts, and scotty in back to back acts. I would like it to order the acts so that they wouldn't be close to each other. So I would want the act order to be something like

1
9
3
4
5
2
10
6
7
8

This way the nights schedule would give them time to change. Now say by rearranging the acts like I did above it put someone else back to back, how would I get it to sort the list so that no students were back to back?

So if the table were in this order(putting sue in act 1 and 9:
id - name - act_number
1 - bobby - 1
2 - sue - 1
3 - bobby - 2
4 - kim - 3
5 - larry - 4
6 - mark - 5
7 - tommy - 6
8 - edward - 7
9 - nathan - 8
10 - scotty - 9
11 - sue - 9
12 - scotty - 10
13 - rick - 10

Arranging the table by hand like I originally did would place sue in back to back acts.

Is there a way, maybe using multiple tables or a clever php script, to do this? I have done a lot of php/mysql but I if I can't figure this out I will need to hire somebody to do this for me.

In the end, say there were two shows that night. I would also not want somebody to be in the first and last act, giving them time to change before the show starts over again.

I realize mysql doesnt really care/know what physical order the rows are in so I am pretty sure this will need to be done with php. But I dont know, mysql has a TON of functions. I am reading through a lot of manuals but it is a lot of content.

Thanks for any help, even if it is a kick in the right direction.

laserlight

I am not terribly good at such proofs, but I think that this problem is NP-complete. Luckily, you only have 20 students and 10 acts, so a solution should be feasible.

One way to start would be to construct an ordered list of tuples of (act, students), where act is the act number and students is a set of student names:
1: bobby, sue
2: bobby
3: kim
4: larry
5: mark
6: tommy
7: edward
8: nathan
9: henry, scotty
10: rick, scotty

A brute force solution would be to permutate the tuples and select the first permutation that satisfies your criteria (i.e., the intersection of students sets of adjacent tuples must be the null set, and optionally the same for the first and last tuples). Since there are 10 tuples, there are 10! = 3628800 permutations.

Bjom

There are no prefab functions for that in mySQL and neither in PHP.

You'll have to develop your own algorithm for that. Should be doable.

For the last problem, the one with the 2 shows: simply throw in the first act a second time after the last act. Your algorithm will then make sure there is no collission.

Bjom

Weedpacket

As a first cut, you could operate like this:

pick someone, anyone, preferably someone who appears a lot.
Pick an act that person appears in, preferably one in which a lot of people make an appearance.
That's your first act. For the second, pick any act in which none of the people who appear in the first act appear.
For the third, pick any act in which none of the people who appear in the second act appear (those who appeared in the first will have had time to change).
If you get stuck (all of the remaining acts contain people who appeared in the last act picked), then throw that last act back and pick another one. It might be necessary to backtrack more than one step

Like I say, that's just a first cut: it is possible to construct lists that can't be satisfied: this will be if someone appears in more than half of the acts, because there aren't enough acts in which they don't appear to fit between the ones where they do.

flexgrip

Ok what about if I did this. Selected all acts that had a person that was in multiple acts and put them into an array. then the rest into another array. then printed out the list according to that. So if I had 20 acts and 5 of them had people in multiple people in them, i would just be like.
1 from the first array,
4 from the rest
1 from the first array
4 from the rest
etc.

Do you see problems with that failing? or is there a smarter way to do it?

laserlight

flexgrip wrote:
Do you see problems with that failing?

If the two groups were about equal in size, that might work. So, if you cannot use a brute force solution (and indeed 20 acts would probably make brute force infeasible), you may need to adapt the algorithm or heuristic to the characteristics of your data set.