Programming puzzles: processing lists!

[pier4r]

(08-16-2017 06:58 PM)pdo Wrote:  My reasoning is as follows: given a list of N items (N even) take the first item, then you have a choice of N-1 items with which to pair it. Choose one, then remove both items from the list. This will leave a list of N-2 items to which you can apply the same procedure, this time giving a choice of N-3 items, and so on. This gives a total number of possible "routes" through this process of (N-1)(N-3)(N-5)...1. For a proper proof we'd need to show each route gives a unique result -- seems plausible to me, but I think it requires a bit more thought to put into words.

Then I saw through your hints properly. The idea is nice (and sort of what I do but without thinking about a formula) but as you said I am not entirely convinced that it gives only unique results.

Actually the #37 is a particular case of https://en.wikipedia.org/wiki/Matching_(graph_theory) so I believe what we are trying to solve is long solved. Just, as I wrote, before looking around I try to not spoil the fun (and learning experience) by myself.

For the recursive way: I thought too to make a tree (like a tree for keys) building it as soon as I pick elements, but the problem is that I may build elements that are just swapped. Like 1-2 3-4 and 3-4 1-2 . So in one case the tree will follow the branch 1-2 and the other 3-4 considering the two complete results different.

Instead if one find an order with built in "safety of no duplicates", like DavidM wants to do it, I guess it will be the most effective way.