Recursion Help

The way I'm thinking of it should take O(n!) time and O(n^2) space, where the recursive step looks something like

Code:

LinkedList recurse(array subset) {
  pointer a = array(length of subset)
  int v = array(length of subset)
  for (each element e in subset) {
    a[e] = recurse(subset without e)
    v[e] = value(a[e])
  }
  i <- index of max(v)
  create new LL element containing element i, pointing at a[i]
  return this new LL of e[i] -> a[i]
}

value(LinkedList in) {
  if (in.next is null)
    return 0;
  else
    return in.value + value(in.next);
}

At its worst, you'll have n linkedlists of length n-1 (at the head of the recursion) taking O(n^2) space... and of course, doing permutations this way means n! different ways.

At the end you end up with returning a linkedlist containing the best value arrangement.

Your linkedlistelements would have to be pointing at an object containing:
- woman
- pairing value
plus it might be useful to have
- man
- total value of the list below this element
Which would increase storage size, but make the class's operations faster & more intuitive.


If you did include total value then the value function would be just a[i].value.getTotal() or something instead, and when you created the new LLE you'd add next.value + next.total...