Wejście: Tablica I od k liczb całkowitych dodatnich. Liczba całkowita nie będzie większa niż 100 i k ≤ 100 .

Dane wyjściowe: Twój kod musi wypisywać wszystkie możliwe tablice O nieujemnych liczb całkowitych o długości k z zastrzeżeniem, że 0 ≤ O _i ≤ I _i . Aby przejść z jednej tablicy do drugiej, możesz dodać lub odjąć 1 do jednej wartości w tablicy. Twój kod nie może wyprowadzać tej samej tablicy dwukrotnie. Jeśli liczba różnych tablic, które mają być wyprowadzone, jest bardzo duża, twój kod powinien po prostu wyprowadzać wyjście w nieskończoność, dopóki nie zostanie zabity.

Przykłady

• Jeśli jestem tablicą k tych, to jest to dokładnie problem iteracji po wszystkich kodach Graya o szerokości bitu k , z tym wyjątkiem, że pierwszy i ostatni element nie muszą być osiągalne w jednym kroku.

• Jeśli tak, I = [2,1]to możliwe jest uporządkowanie tablic wyjściowych(0,0),(0,1),(1,1),(1,0),(2,0),(2,1)

• Jeśli tak, I = [2,1,3]to możliwe jest uporządkowanie tablic wyjściowych (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),....

To jest wyzwanie dla golfa, wygrywa zgłoszenie z kodem źródłowym o najkrótszej długości. Nie pozwól, aby krótkie odpowiedzi w językach golfowych zniechęciły cię do zamieszczania odpowiedzi w innych językach. Spróbuj znaleźć najkrótszą odpowiedź w dowolnym języku.

Jest to również wyzwanie o ograniczonej złożoności. Każda nowa tablica powinna być wyprowadzana z upływem czasu O (k) od czasu poprzedniej tablicy wyjściowej (lub początku programu dla pierwszej tablicy wyjściowej). Oznacza to, że czas działania dla nowej tablicy wyjściowej (każda z nich ma długość k ) nie powinien być większy niż O (k) . To znaczy, że powinno to zająć czas proporcjonalny do k, a nie, na przykład k ² lub 2 ^k . Zauważ, że nie jest to średni czas na wyjście, ale najgorszy przypadek dla każdej wysłanej tablicy.

Możesz założyć, że cała arytmetyka na 64-bitowych liczbach całkowitych może być wykonywana w stałym czasie, podobnie jak ich odczyt i wysyłanie, a także przypisywanie, wyszukiwanie i zmiana wartości w tablicach.

Jedną z konsekwencji ograniczonej złożoności jest to, że rozwiązania, które pojawiają się tylko przy wyjściu z programu, są niedopuszczalne.

Python 3 , 116 bajtów

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]

Wypróbuj online!

Dzięki Mnemonic za -1 bajt.

Funkcja generatora. (dzięki Dennis za przypomnienie, zapomniałem, że funkcja istnieje) Jeśli wyjście powinno zostać wydrukowane na standardowym wyjściu, użyj print(t,flush=1)9 dodatkowych bajtów lub, jeśli wywoływany jest Python -u, print(t)wystarcza na +1 bajtów.

Zatrzymuje się z błędem ( IndexError). Jeśli chcesz wywołać tę funkcję, a następnie kontynuować program, musisz ją złapać.

Stax , 22 bajty

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

Uruchom i debuguj

Oto duży, aby pokazać asymptotyczne zachowanie Naciśnij bieg.

Rozpakowane, niepolowane i skomentowane, wygląda to tak.

,           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

Uruchom ten

JavaScript (Node.js) , 114 bajtów

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;}}

Wypróbuj online! Nie golfowany:

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]--;
    }
}

Kotlin , 181 178 bajtów

Dzięki: Anush wskazał, że źle zrozumiałem wyzwanie, oszczędzając 2 bajty. ovs wskazał 1 bajt oszczędności.

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]}}

Wypróbuj online!