Input: An array I of k positive integers. The integers will be no larger than 100 and k ≤ 100.
Output: Your code must output all possible arrays O of non-negative integers of length k with the restriction that 0 ≤ Oi ≤ Ii. To get from one array to the next you may add or subtract 1 to one value in the array. Your code must not output the same array twice. If the number of different arrays to be output is very large, your code should just carry on outputting forever until it is killed.
If I is an array of k ones then this is exactly the problem of iterating over all Gray codes of bit width k, except that the first and the last element do not need to be reachable in one step.
I = [2,1]then one possible ordering of the output arrays is
I = [2,1,3]then one possible ordering of the output arrays is
This is a code-golf challenge, the submission with the source code with the shortest length wins. Don't let the short answers in golfing languages discourage you from posting an answer in other languages. Try to come up with the shortest answer in any language.
This is also a restricted-complexity challenge. Every new array should be output with O(k) time elapsing since the previous outputted array (or the start of the program for the first array outputted). This means that the running time per new output array (they are each of length k) should be no greater than O(k). That is it should take time proportion to k and not, for example k2 or 2k. Note this is not the average time per output but the worst case time for each and every array outputted.
You can assume that all arithmetic on 64 bit integers can be performed in constant time as can reading and outputting them as well as assignment and looking up and changing values in arrays.
One consequence of the restricted-complexity is that solutions that only output at program exit are not acceptable.