Algorithm for creating unique groups of elements

[Pi Face]

Homework Statement

so for a side task I'm supposed to assign people to groups for an icebreaker in python, can anyone give me links to theories that I could read up on or give me suggestion

X number of people at my company signed up for a dinner roulette as a way to meet new people. Everyone is grouped in groups of Y people each (Y=3 in this case). If there is a remainder it is more preferable to have groups of Y+1 (4) rather than Y-1 (2) Furthermore, each of the X people are in a different department, let's say Z number of departments (D1, D2, D3 etc) and no group should have more than 1 person from each department where avoidable (groups of 4) I should have some sort of history function so that when the roulette is run again, the same people are not paired with each other. I'm only a novice comp sci student so I don't have much background in optimization methods, can someone critique my approach? I'm going to be writing this script in python so I've been looking into itertools but not sure what to use.

The Attempt at a Solution

assume say X=11 people, Y= groups of 3, Z = 5 departments A1= first person from dept A, B4= 4th person from dept B, etc

so let's say this is my group of people (3 from A, 5 from B, 2 from C, 1 from D, 3 from E)

A1 B1 C1 D1 E1
A2 B2 C2 E2
A3 B3 E3
-- B4
-- B5

My first thought is to put them in order from high to low population

B1 A1 E1 C1 D1
B2 A2 E2 C2
B3 A3 E3
B4
B5

next, I attempt to tetris-ify them, by squeezing them into a 3 person wide array. I leave B, A, E columns as is since they are the first 3. I take the next column, column C, and stack it on top of the second column, column A.

B1 A1 E1 D1
B2 A2 E2
B3 A3 E3
B4 C1
B5 C2

At this point, if there was 6 or more people in the B column, i would continue adding people to the second column until there were at least as many in column 2 as column 1. since they are equal (both 5), I move onto the next column, column D. I place the people of D onto the third column so we are left with

B1 A1 E1
B2 A2 E2
B3 A3 E3
B4 C1 D1
B5 C2

we now have 4 groups of 3 and 1 group of 2. Because we'd rather have groups of 4 than 2, we move the remainders to the 4th column

1) B1 A1 E1 B5
2) B2 A2 E2 C2
3) B3 A3 E3
4) B4 C1 D1

There is some conflict due to 2 people from group B in the first group/row but I think it's unavoidable(?)

Now for the second rnu of the roulette, we have stored the above 4 combinations as a history to prevent someone from being grouped with a person they've already been grouped with. Starting with the existing combinations, we leave the first column alone, shift the 2nd column by 1, the 3rd column by 2, and the 4th column by 3 to get:

1) B1 C1 E3 C2
2) B2 A1 D1
3) B3 A2 E1
4) B4 A3 E2 B5

This would be the second run of the roulette. I guess this also means that number of people per group needs to be less than number of groups for this to work?

There is also the issue of what happens when someone drops out from the first roulette to the second, and someone joins in on the second roulette. Let's say A1 drops out and E4, E5 joins, so we have

Ax B1 C1 D1 E1
A2 B2 C2 E2
A3 B3 E3
-- B4 E4new
-- B5 E5new

to make it easier to deal with the history, we keep the index of the old spot and then populate according to group:

Ax B1 C1 D1 E1
A2 B2 C2 E2
A3 B3 E3
-- B4 E4
-- B5 E5

put them in order once more (same order as first run):

B1 Ax E1 C1 D1
B2 A2 E2 C2
B3 A3 E3
B4 E4
B5 E5

next tetris-ify them

B1 Ax E1 C1
B2 A2 E2 C2
B3 A3 E3
B4 C1 E4
B5 C2 E5
D1

move remainder to 4th col

B1 Ax E1 C1
B2 A2 E2 C2
B3 A3 E3 D1
B4 C1 E4
B5 C2 E5

Then since it's the 2nd run, multiply each shift by 2: 2nd column shifted twice, 3rd col 4 times, 4th 6

B1 C1 E2
B2 C2 E3 C1
B3 Ax E4 C2
B4 A2 E5 D1
B5 A3 E1

so the groups are

1) B1 C1 E2
2) B2 C2 E3 C1
3) B3 E4 C2 (Ax is the A1 that left so he's gone)
4) B4 A2 E5 D1
5) B5 A3 E1

I realize upon rereading my post how confusing I might sound as I expressed myself poorly and have no real background in optimization, but I wanted to show my thought process and that I really took the time to think about the problem. Is there a more elegant solution to what I have? Is there a more optimal way? Feel free to link or post anything you think would help, I'm really curious as to how this can be optimized, thanks!

 

[jedishrfu]

For tools, you could consider the Processing.org IDE which has an installable Python mode. It has to be one of the easier ways of playing with Python.

Other people may simply use python from the command line with a simple text editor like vim.

Lastly, there's iPython for numerical computing using python.