Joe Ganley: Chinese menu enumeration

A number of times I've been faced with what I call the "Chinese menu enumeration" problem - you know, one from column A, one from column B, etc. Given an array num of N entries where each entry contains the number of items in that column, enumerate [the indices of] all of the possible meals. Equivalently, list every N-digit number in which the i'th digit is less than num[i]. This is not a hard problem, but it's all too easy to write ugly code for it. My latest attempt ended up like this:

int val[N]; for (int i = N - 1; i >= 0; --i) val[i] = 0; for (int inc = 0; inc >= 0;) { // do whatever you need to do with val[] inc = N - 1; while (inc >= 0 && ++val[inc] == num[inc]) { val[inc--] = 0; } }

Pretty succinct, but I can't shake the feeling that it could be ~~obfuscated~~ simplified further. Any takers?

Labels: programming

Joe Ganley	I make software and sometimes other things.

Due to Blogger's termination of support for FTP, this blog is no longer active. It is possible that some links from here, particularly those within the site, are now broken. If you encounter one of those, your best bet is to go to the new front page and hunt for it from there. Most, but not all, of the blog's posts are on this page; the archives are here.
Chinese menu enumeration
A number of times I've been faced with what I call the "Chinese menu enumeration" problem - you know, one from column A, one from column B, etc. Given an array num of N entries where each entry contains the number of items in that column, enumerate [the indices of] all of the possible meals. Equivalently, list every N-digit number in which the i'th digit is less than num[i]. This is not a hard problem, but it's all too easy to write ugly code for it. My latest attempt ended up like this: `int val[N]; for (int i = N - 1; i >= 0; --i) val[i] = 0; for (int inc = 0; inc >= 0;) { // do whatever you need to do with val[] inc = N - 1; while (inc >= 0 && ++val[inc] == num[inc]) { val[inc--] = 0; } }` Pretty succinct, but I can't shake the feeling that it could be ~~obfuscated~~ simplified further. Any takers? Labels: programming 0 Comments: Post a Comment << Home