Programming puzzles: processing lists!

08162017, 07:33 PM
(This post was last modified: 08162017 07:34 PM by pier4r.)
Post: #190




RE: Programming puzzles: processing lists!
(08162017 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 N1 items with which to pair it. Choose one, then remove both items from the list. This will leave a list of N2 items to which you can apply the same procedure, this time giving a choice of N3 items, and so on. This gives a total number of possible "routes" through this process of (N1)(N3)(N5)...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 12 34 and 34 12 . So in one case the tree will follow the branch 12 and the other 34 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. Wikis are great, Contribute :) 

« Next Oldest  Next Newest »

User(s) browsing this thread: 2 Guest(s)