Generalized Gray codes

Question

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 ≤ O_i ≤ I_i. 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.

Examples

• 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.

• If I = [2,1] then one possible ordering of the output arrays is (0,0),(0,1),(1,1),(1,0),(2,0),(2,1)

• If I = [2,1,3] then one possible ordering of the output arrays is (0,0,0),(0,0,1),(0,0,2),(0,0,3),(0,1,3),(0,1,2),(0,1,1),(0,1,0),(1,1,0),(1,1,1),(1,1,2),(1,1,3),(2,1,3),(2,1,2),(2,1,1),(2,1,0),....

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 k² or 2^k. 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.

Answer 1

Python 3, 116 bytes

def f(a):
 l=len(a);t=[0]*l;d=[1]*l
 while 1:
  i=0;yield t
  while not-1<t[i]+d[i]<=a[i]:d[i]*=-1;i+=1
  t[i]+=d[i]

Try it online!

Thanks Mnemonic for -1 byte.

Generator function. (thanks Dennis for reminding me, I forgot the feature exists) If the output should be printed to stdout then use print(t,flush=1) for 9 additional bytes, or if Python is called with -u, print(t) suffices for +1 bytes.

Stops with an error (IndexError). If you want to call this function and then continue the program, you have to catch it.

Answer 2

Stax, 22 bytes

▒)∙ñ╚▀NK♀F☺S(A#P`░]╪Db

Run and debug it

Here's a big one to show the asymptotic behavior Press run.

Unpacked, ungolfed, and commented, it looks like this.

,           pop from input to main stack
W           run the rest of the program repeatedly until explicitly cancelled
  cJP       copy top of stack and print, delimited by spaces
            get the index to mutate
  i^            iteration index + 1
  x{^|%}I       repeatedly apply divmod using l[k]+1 from input
                get the index of the first value that returns modulus >0
  cU=C      if the result is -1 (no match), then terminate the program
            get the direction to mutate
  s             get the "div" part of the last div operation called "d"
  ^|1           -1 ^ (d+1)
  ~{+}&     increment element in array at the index by the calculated amount

Run this one

Answer 3

Kotlin, 181 178 bytes

Thanks to: Anush pointed out I misunderstood the challenge saving 2 bytes. ovs pointed out a 1 byte savings.

val p={a:List<Int>->var l=a.size
val v=Array(l,{0})
val i=Array(l,{1})
l-=1
o@while(0<1){println(v)
var p=l
while(v[p]+i[p]!in 0..a[p]){i[p]*=-1
p-=1
if(p<0)break@o}
v[p]+=i[p]}}

Try it online!

Answer 4

JavaScript (Node.js), 114 bytes

a=>{b=a.map(_=>0);c=a.map(_=>1);for(i=0;a[i];b[i]+=c[i]||-1){console.log(b);for(i=0;b[i]==a[i]*c[i];i++)c[i]^=1;}}

Try it online! Ungolfed:

function ggray(maxima) {
    var current = Array(maxima.length).fill(0);
    var flag = Array(maxima.length).fill(1);
    for (;;) {
        console.log(current);
        for (var i = 0; ; i++) {
            if (i == maxima.length) return;
            if (current[i] != maxima[i] * flag[i]) break;
            flag[i] = 1 - flag[i];
        }
        if (flag[i]) current[i]++;
        else current[i]--;
    }
}