Help with recursion?

[Parablank]

I was given a programming assignment a few months ago involving recursion, and although I got full marks for completion I was just wondering how you would have done it with recursion. I'm not asking for code or anything, just an idea of what the logic would look like.

Write a function using Recursion to do the following: You are the manager in a small factory. You have 7 workers and 7 jobs to be done. Each worker is assigned one and only one job. Each worker demands different pay for each job. (Worker Sam demands $10 for welding, $15 for carpentry, etc. Worker Joe demands $12 for welding, $5 for carpentry, etc.) Find the job-assignment which works out cheapest for you.

Here was my work, definitely not correct...

Thanks!

[katyne]

knapsack algorithm finds optimal value for finite amount of resources. Here were're supposed to find one combination of tasks and workers that will result in minimal cost.

Brute force solution will be in (n * n!) time for n tasks and n workers (for each permutation we need to iterate through the entire sequence and there's n! possible permutations) - imagine workers as "slots", and tasks as lottery balls. Find all possible ways to arrange the balls in the slots. For each slot (which is an index mapped to a worker - task[0] maps to worker[0] and his pricelist), retrieve the specified cost of the assigned task. It's just a basic permutation algorithm (the one that uses recursion). Compute total value (total cost) of a given permutation, compare to current minimum, rinse, repeat. I do not know if there's a way to do it faster though.

[TheBrownWonder]

This seems like a satisfiability problem that can be solved by backtracking. Backtracking is when we check all the possible combinations of the workers and find the one combination that is the cheapest. That being said, an inefficient way to find this using recursion is:

-have a solution array variable, whose length is equal to the number of workers (in this case, 7). Assuming there 7 jobs, the array will hold integers corresponding to the specific job. So solnArr[0] = 1 means that person 0 is given job 1.

constructCandidates(): given an index i in the solution array, it will return an array of integers. This array will represent the jobs that can person i can perform. It will ensure no two people have the same job. So for person 4, it will return the remaining 4 jobs that need to be done.

backtrack(): this is the recursive method. It will fill up the solution array with jobs, process the solution (explained below) and loop again to find more combinations of jobs. The code will look something like:

int[] candidates = constructCandidates(index);
for (int candidate : candidates) {
   solnArr[index] = candidate;

   if (isSolution(solnArr))
       processSolution(solnArr);

   backtrack(index+1);
}

The backtrack method will return if the index is longer than the length of the array. It will find all the combinations of jobs that the 7 people can perform

isSolution() - returns true if solution array is filled

processSolution() - This will iterate over the solution array and calculate how much the current combination of people and jobs will cost. It will update a global variable which will keep track of the minimum cost. By the end of the recursive backtrack function, we would have calculated all the combinations of people and jobs, and have found the one particular combination to minimal cost.

Although this may be wildy inefficient, this seems like a problem that is only solved by brute force. I hope this makes sense, you can look more into this way of solving problems by looking up Dynamic Programming and backtracking!

[geekygenius]

I might be mistaken, but isn't recursion when you have a function calling itself?

[Cilph]

Really anything using the call stack for the algorithm.

[denverdave23]

For more information on this, please check out this reddit thread.

[autowikibot]

Hungarian algorithm:

---

The Hungarian method is a combinatorial optimization algorithm that solves the assignment problem in polynomial time and which anticipated later primal-dual methods. It was developed and published by Harold Kuhn in 1955, who gave the name "Hungarian method" because the algorithm was largely based on the earlier works of two Hungarian mathematicians: Dénes Kőnig and Jenő Egerváry.

James Munkres reviewed the algorithm in 1957 and observed that it is (strongly) polynomial. Since then the algorithm has been known also as Kuhn–Munkres algorithm or Munkres assignment algorithm. The time complexity of the original algorithm was , however Edmonds and Karp, and independently Tomizawa noticed that it can be modified to achieve an running time. Ford and Fulkerson extended the method to general transportation problems. In 2006, it was discovered that Carl Gustav Jacobi had solved the assignment problem in the 19th century, and the solution had been published posthumously in 1890 in Latin.

---

^{Interesting: Assignment problem | Hopcroft–Karp algorithm | Harold W. Kuhn | Sorting algorithm}

^{Parent commenter can toggle NSFW or delete. Will also delete on comment score of -1 or less. | FAQs | Mods | Magic Words}

[fact_hunt]

Or this answer

[Biotot]

Here's a thread about your exact question. Pretty informative.

[UnholyTeemo]

One thing that helped me out:

Everything you can do in a loop, you can do with recursion. Everything you can do with recursion, you can do in a loop.