0
$\begingroup$

There are $p$ projects and $s$ students where $p \le s$. Multiple students can work on the same project but the same student cannot work on multiple projects. All projects must be allocated and all students must have a project. I need to compute and display all possible ways of allocating projects to students under these constraints. Here's an example:

Input:

3 students, 2 projects

Output:

   P1      P2
   {1}     {2, 3}
   {2}     {1, 3}
   {3}     {1, 2}
   {1, 2}  {3}
   {1, 3}  {2}
   {2, 3}  {1}

In my attempts, I've thought about this as being related to the problem of partitioning the set of students into non empty subsets and then ignoring those partitions which have unacceptable length. i.e. for my example generate:

{{1}, {2}, {3}}
{{1}, {2, 3}}
{{2}, {1, 3}}
{{3}, {1, 2}}
{{1, 2, 3}}

and ignore the first and last as well as double count the three in the middle as they can be arranged in a two ways (order matters for this problem). I'm not sure however how I would go about generating and filtering these subsets and even whether this is a decent solution for any p or s values.

$\endgroup$
0
$\begingroup$

I didn't get what you're exatly asking for? Backtracking is the solution. Are you looking for an actual implementation or an explanation of backtracking? Or a better performing approach in terms of runtime.

Here my pseudo code how I would generate all matching solutions.

state = [];  //array representing the current state, assigns students to projects

S = [..];    //array containing the students
P = [..];    //array with students
func assign(level) {
  if(level == S.length) {
    if is_valid_state() //ensure each project has at least one student
      output(state);
  }
  for(i = 0; i < P.length; i++) {
    state[level] = i;
    assign(level+1);
  }
}

level(0)

Can of course be optimized by moving the final condition atop, but this would be my first thought of how to solving this the least efficient way (in terms of performance).

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I guess I'm looking for an implementation. I've updated my question a bit with a simple example and one of my attempts at reasoning about the problem. $\endgroup$ – Alex Dec 15 '14 at 12:17
  • $\begingroup$ Your pseudo code is a bit too abstract and I'm not sure how it goes about turning the given input into the proper solution. Maybe if you can add a bit more detail to it I'll be able to better grasp it and then get back to you with some proper questions, if any. $\endgroup$ – Alex Dec 15 '14 at 12:21
  • $\begingroup$ @Alex Pseudocode is, by its very nature, somewhat abstract. An actual implementation in an actual programming language would be off-topic here, as understanding it would depend almost as much on understanding the details of the particular language chosen as it would on understanding the underlying problem. Is there something more specific you don't understand about the algorithm? "I'm not sure how it goes about turning the given input into the proper solution" is essentially the same as "I'm not sure how any of it works." $\endgroup$ – David Richerby Dec 15 '14 at 12:26
  • $\begingroup$ Indeed, abstract is fine, but this one is a "bit too abstract" for my capabilities, hence the request for more details, if possible. My asking for an implementation was a bit of a mistake. I'm not looking for c code or something. Just a more detailed exposition of the solution. $\endgroup$ – Alex Dec 15 '14 at 12:31
  • $\begingroup$ And yes, I don't really understand how any of it works. That's why I was looking for more details. I'm not sure what level is, what P holds, nor how state as an array is supposed to work. $\endgroup$ – Alex Dec 15 '14 at 12:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.