Programming puzzles: processing lists!

[pdo]

(08-16-2017 03:03 PM)DavidM Wrote:  

(08-16-2017 12:51 PM)pdo Wrote:  Hello,

I don't know if this has been mentioned already for #37, and excuse me if I'm barging in and stating the obvious here, but I think there is a simple proof that the total number of match-day pairings for any even N is equal to (N-1)(N-3)(N-5)...1 and an efficient/elegant way of enumerating them would probably be recursive in nature.

Paul

Well I think it's safe to say that you are neither "barging in" nor "stating the obvious", since neither of the two previously-active participants for this problem seemed to have deduced the equation for the number of "match-days".

I hope you have the time (and inclination) to put something together for this. It would be nice to see how you approach it!

Hi David,

Sorry for being cryptic, it was just a quick post after my lunchtime reading (this forum).

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.

As far as a program to compute the pairings goes, I was imagining a function recursing on the list in a similar way to my description above, but collecting all the possible choices and collating the results. I can imagine how to do this in a language like Lisp, for example, but on the way home from work I got to thinking how I would implement this in RPL, and to be honest I'm not sure how I would go about it. Stuff to ponder...

Paul