1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Algorithm for creating unique groups of elements

  1. Jul 22, 2015 #1
    1. The problem statement, all variables and given/known data
    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.

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

    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

    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!
  2. jcsd
  3. Jul 24, 2015 #2


    Staff: Mentor

    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted