Random Seating

[mmertk]

Hey everyone! This is my first post on this site, and I have a question/problem.

 

Well, I have 2 databases (one contains tables and the other contains users). I want users to pick 3 tables in orders -like first_choice, second_choice and third_choice - and I want to have an action that seats users for their choices for each table. Like for first table, the function would search every user in database and find the one that has the first table's ID (1) for the first_choice. And if table is full, then the function should go for the second table. If not, when all the tables are cycled for once, function should run again with second_choices. And same thing for the third_choices.

 

Well, on paper it seemed pretty easy. But not working with PHP and MySQL for a while, hasn't been a good thing for me. If you could help me with codes, resources or ideas, I'd really be thankful. I don't have too much time, so yeah... THANKS!

[Christian F.]

What you're looking for is called a "weighted selection", if my translation and understanding is correct.

A quick search on the term gave me, amongst others, this result: http://forums.devshed.com/game-development-141/correctly-making-a-weighted-selection-755978.html

[mmertk]

I'm checking it now, thanks!

[Psycho]

I can think of a fairly strait-forward simple solution. But, first off you need to determine what gives one user precedence over another. If too many people selected table B as their first choice, who gets table B and who will be kicked out to another table. I don't know what data you do and do not have, but I would base it upon the timestamp of when each user made their choice.

 

But, here is what I would do

 

1. Do a select query for all tables using only the ID. Process these results into an an array with the ID as the key and an empty sub-array as the value. This will be the assigned array.

2. Do a select query on the users including their choices for 1 2 and 3

3. As you process the records above you will check if a user's first selection is available in the assigned array created on step 1. If so, add them and skip to the next record. If not you check thier second and third selections. If none of the user's choices are available put the user into an unassigned array until you've finished processing all the users.

4. After all the users have been processed to put them into one of their three choices, go back through the unassigned array (users' who's first, second and third choices were at capacity) and randomly put them into the tables that have capacity.

 

Here is a quick script that appears to work. However, I hard coded the data I would generate from a DB query for testing since I didn't feel like creating DB tables. So you will need to modify accordingly

 

<?php

//Mock DB results for tables
$tablesDB = array('Table A', 'Table B', 'Table C', 'Table D');

//Mock DB results for users and their selections
$userSelectionsDB = array(
array('userID' => 0, 'sel_1'=>0, 'sel_2'=>1, 'sel_3'=>2),
array('userID' => 1, 'sel_1'=>1, 'sel_2'=>3, 'sel_3'=>2),
array('userID' => 2, 'sel_1'=>0, 'sel_2'=>1, 'sel_3'=>2),
array('userID' => 3, 'sel_1'=>0, 'sel_2'=>1, 'sel_3'=>2),
array('userID' => 4, 'sel_1'=>0, 'sel_2'=>1, 'sel_3'=>3),
array('userID' => 5, 'sel_1'=>0, 'sel_2'=>1, 'sel_3'=>2),
array('userID' => 6, 'sel_1'=>2, 'sel_2'=>1, 'sel_3'=>0),
array('userID' => 7, 'sel_1'=>0, 'sel_2'=>1, 'sel_3'=>2),
array('userID' => 8, 'sel_1'=>0, 'sel_2'=>1, 'sel_3'=>2),
array('userID' => 9, 'sel_1'=>1, 'sel_2'=>0, 'sel_3'=>2),
array('userID' => 10, 'sel_1'=>2, 'sel_2'=>1, 'sel_3'=>0),
array('userID' => 11, 'sel_1'=>2, 'sel_2'=>1, 'sel_3'=>0),
array('userID' => 12, 'sel_1'=>0, 'sel_2'=>1, 'sel_3'=>2),
array('userID' => 13, 'sel_1'=>0, 'sel_2'=>1, 'sel_3'=>2),
array('userID' => 14, 'sel_1'=>2, 'sel_2'=>0, 'sel_3'=>1),
array('userID' => 15, 'sel_1'=>2, 'sel_2'=>0, 'sel_3'=>1),
array('userID' => 16, 'sel_1'=>0, 'sel_2'=>1, 'sel_3'=>2),
array('userID' => 17, 'sel_1'=>2, 'sel_2'=>0, 'sel_3'=>1),
array('userID' => 18, 'sel_1'=>0, 'sel_2'=>1, 'sel_3'=>2),
array('userID' => 19, 'sel_1'=>3, 'sel_2'=>1, 'sel_3'=>0)

);

//Number of people that can fit at a table
$tableCapacity = 5;

//Create array of table assignments
$assignments = array();
//This foreach loop would be replaced with a DB query and while loop
foreach($tablesDB as $tableID => $tableName)
{
$assignments[$tableID] = array();
}

//Array to temporarily assign usrs whose choices are already full
$unassignedUsers = array();
//Assign users to tables based upon their preferences
//This foreach loop would be replaced with a DB query and while loop
foreach($userSelectionsDB as $row)
{
if(count($assignments[$row['sel_1']]) < $tableCapacity)
{
 $assignments[$row['sel_1']][] = $row['userID'];
}
elseif(count($assignments[$row['sel_2']]) < $tableCapacity)
{
 $assignments[$row['sel_2']][] = $row['userID'];
}
elseif(count($assignments[$row['sel_3']]) < $tableCapacity)
{
 $assignments[$row['sel_3']][] = $row['userID'];
}
else
{
 $unassignedUsers[] = $row['userID'];
}
}

//After all users are placed into one of their three preferences if capacity allows
//If any were not able to be placed, assign them to tables where there is capacity
foreach($assignments as $tableID => $assignedUsers)
{
$remainingCapacity = $tableCapacity - count($assignedUsers);
if($remainingCapacity > 0)
{
 $assignments[$tableID] = array_merge($assignedUsers, array_slice($unassignedUsers, 0, $remainingCapacity));
 $unassignedUsers = array_slice($unassignedUsers, $remainingCapacity);
}
if(!count($unassignedUsers)) { break; }
}

echo "<pre>" . print_r($assignments, 1) . "</pre>";
?>

Edited October 11, 2012 by Psycho