# Reverse Range Successors

Given a positive integer n, do the following (and output every stage):

1. start with a list containing n copies of n.
2. do the following n times:
3. at the ith step, gradually decrement the ith entry of the list until it reaches i

So, for example, if the given n is 4, then you start with [4,4,4,4], and then at the first step you have [3,4,4,4], [2,4,4,4], [1,4,4,4]. At the second step, you have [1,3,4,4], [1,2,4,4]. At the third step you have [1,2,3,4]. Nothing is done on the fourth step.

So your output is [[4,4,4,4],[3,4,4,4],[2,4,4,4],[1,4,4,4],[1,3,4,4],[1,2,4,4],[1,2,3,4]].

Any reasonable input/output format is permitted.

Standard loopholes apply. This is : the answer with the smallest byte-count wins.

• You might want to explicitly state that ith is always 1-indexed. Mar 28, 2018 at 10:01
• Do we really have to manipulate array? I get to a shorter answer without manipulating any array, producing an acceptable output. Mar 28, 2018 at 14:20
• @OlivierGrégoire You do not have to follow the steps, you just need to produce the output in a reasonable format. (i.e. go ahead) Mar 28, 2018 at 14:21

# Jelly, 9 bytes

r€⁸Œp»\QṚ


Try it online!

### How?

r€⁸Œp»\QṚ - Link: integer, N    e.g. 4
€        - for €ach of implicit range of N (i.e. for i in [1,2,3,...N])
⁸       -   with the chain's left argument, N on the right:
r         -     inclusive range (for i<=N this yields [i, i+1, ..., N]
- ...leaving us with a list of lists like the post-fixes of [1,2,3,....,N]
-                     e.g. [[1,2,3,4],[2,3,4],[3,4],]
Œp     - Cartesian product* of these N lists
-                     e.g. [[1,2,3,4],[1,2,4,4],[1,3,3,4],[1,3,4,4],[1,4,3,4],[1,4,4,4],[2,2,3,4],[2,2,4,4],[2,3,3,4],[2,3,4,4],[2,4,3,4],[2,4,4,4],[3,2,3,4],[3,2,4,4],[3,3,3,4],[3,3,4,4],[3,4,3,4],[3,4,4,4],[4,2,3,4],[4,2,4,4],[4,3,3,4],[4,3,4,4],[4,4,3,4],[4,4,4,4]]
\   - cumulative reduce with:
»    -   maximum (vectorises)
-                     e.g. [[1,2,3,4],[1,2,4,4],[1,3,4,4],[1,3,4,4],[1,4,4,4],[1,4,4,4],[2,4,4,4],[2,4,4,4],[2,4,4,4],[2,4,4,4],[2,4,4,4],[2,4,4,4],[3,4,4,4],[3,4,4,4],[3,4,4,4],[3,4,4,4],[3,4,4,4],[3,4,4,4],[4,4,4,4],[4,4,4,4],[4,4,4,4],[4,4,4,4],[4,4,4,4],[4,4,4,4]]
Q  - de-duplicate        e.g. [[1,2,3,4],[1,2,4,4],[1,3,4,4],[1,4,4,4],[2,4,4,4],[3,4,4,4],[4,4,4,4]]
Ṛ - reverse             e.g. [[4,4,4,4],[3,4,4,4],[2,4,4,4],[1,4,4,4],[1,3,4,4],[1,2,4,4],[1,2,3,4]]


* It may be easier to see what's going on with the Cartesian product used above with a different input:

the Cartesian product of [[0,1,2],[3,4],]
is [[0,3,5],[0,4,5],[1,3,5],[1,4,5],[2,3,5],[2,4,5]]

• You outgolfed the un-outgolf-able. Mar 29, 2018 at 0:58

# R, 8382 74 bytes

N=rep(n<-scan(),n);while({print(N);any(K<-N>1:n)})N[x]=N[x<-which(K)]-1


Try it online!

Instead of a double for-loop, a while loop is sufficient here: we find the first index where the list is greater than the index, and decrement there.

K has TRUE wherever N[i]>i, which(K) returns the true indices, and we take the first with .

# Jelly, 12 bytes

R‘®¦<³S©$Ð¿Ṛ  Try it online! • 13 bytes without register: Try it online! Mar 28, 2018 at 5:37 # JavaScript (ES6), 75 bytes f=(n,a=Array(n).fill(n))=>[[...a],...a.some(v=>v>++j,j=0)?f(a[j-1]--,a):[]]  Try it online! # APL+WIN, 54 bytes Prompts for screen input of integer ((⍴m)⍴n)-+⍀m←0⍪(-0,+\⌽⍳n-1)⊖((+/+/m),n)↑m←⊖(⍳n)∘.>⍳n←⎕  Outputs a matrix with each row representing the result of each step e.g. for 4: 4 4 4 4 3 4 4 4 2 4 4 4 1 4 4 4 1 3 4 4 1 2 4 4 1 2 3 4  # Jelly, 11 bytes x’Jḟḣ1Ʋ¦ÐĿ  Try it online! ### How it works x’Jḟḣ1Ʋ¦ÐĿ Main link. Argument: n x Repeat self; yield an array of n copies of n. ÐĿ While the results are unique, repeatedly call the link to the left. Return the array of all unique results, including the initial value. ’ ¦ Decrement the return value at all indices specified by the chain in between. Ʋ Combine the four links to the left into a monadic chain. J Indices; yield [1, ..., n]. ḟ Filterfalse; remove all indices that belong to the return value. ḣ1 Head 1; truncate the result to length 1.  # Python 3, 91 bytes n=int(input()) x=[n]*n;print(x) for i in range(n): for j in*(n-i-1):x[i]-=1;print(x)  Try it online! • 1 space is enough to indent code in python. Removing unnecessary spaces and switching to python 2 saves 10 bytes: check it out Mar 29, 2018 at 9:56 • @DeadPossum, even though I know I could do better in Python 2, its soon going to be obsolete so I wanted to practice my Python 3 skills as most as possible. – Dat Mar 29, 2018 at 14:22 # Java (OpenJDK 8), 135 bytes a->{int r[]=new int[a],i=0;java.util.Arrays x=null;x.fill(r,a);for(r++;i<a;r[i++]++)for(;--r[i]>i;System.out.print(x.toString(r)));}  Try it online! Explanation: int r[]=new int[a],i=0; //Initialize array and loop counter java.util.Arrays x=null; //reduces the number of of “Arrays” needed from 3 to 1 x.fill(r,a); //Sets each value in array length n to int n for(r++;i<a;r[i++]++) //Increment everything! for(;--r[i]>i; //If decremented array element is larger than element number: System.out.print(x.toString(r)));} //Print the array  Credit: -8 bytes thanks to Jonathan Frech! -16 bytes thanks to Kevin Cruijssen! -1 byte thanks to Okx! • The import java.util.*; is part of the byte-count I'm afraid. And @JonathanFrech's code can be golfed by 4 more bytes by putting the ,i=0 after the r[], and changing <-~a to <=a. (Try it online. 144 bytes) (and I changed ~-i to i-1 to make it more readable..) Mar 28, 2018 at 12:09 • 139 bytes by getting rid of the import java.util.*; by using java.util.Arrays x=null; and x.fill and x.toString. (Note that your current solution is 155 bytes with the required import java.util.*;.) Mar 28, 2018 at 12:16 • Golf a byte by using for(;r[i-1]>i; rather than for(;r[i-1]!=i;. – Okx Mar 28, 2018 at 12:24 • @KevinCruijssen Another byte could be saved by golfing ++i<=a to i++<a. Mar 28, 2018 at 12:55 • Another -2 byte changing the last part to for(r++;i<a;r[i++]++)for(;--r[i]>i;System.out.print(x.toString(r)));. :) Try it online 135 bytes Mar 29, 2018 at 9:16 # Haskell, 69 67 65 63 bytes Recursive definition: f 0=[[]] f a=map(:(a<$[2..a]))[a,a-1..2]++[1:map(+1)x|x<-f$a-1]  Thanks to Laikoni for 2 bytes! • The second map is two bytes shorter with a list comprehension: Try it online! Mar 29, 2018 at 9:22 ## PHP, 153 Bytes Try it online! Code function f($n){
$a=array_fill(0,$n,$n);$r=json_encode($a)."\n";$p=0;while($p<$n)
{if($a[$p]!=$p+1){$a[$p]--;$r.=json_encode($a)."\n";}else{$p++;}}echo$r;}  Gonna try to lower the bytes, or finish the recursive function Explanation function f($n){
$a=array_fill(0,$n,$n); #start with$nlength array filled with $n$r=json_encode($a)."\n"; #pushed to the string to output$p=0;                            #first position
while($p<$n){                    #on position $n ($n-1) we do nothing
if($a[$p]!=$p+1){ #comparing the position+1 to the value$a[$p]--; #it gets decreased by 1$r.= json_encode($a)."\n"; #and pushed } else {$p++;                       #when position+1 = the value,
}                               #position is changed ++
}
echo $r; }  • seems like you have some unnecessary whitespace so this should be 153 bytes -- note that I don't know PHP. Apr 4, 2018 at 20:28 • yep, just realize, thank you, editing now. Apr 4, 2018 at 20:30 # Python 2, 80 76 bytes i=input();l=[i]*i;print l for x in range(i): while l[x]>x+1:l[x]-=1;print l  Try it online! Bit wasteful having two print statements but I can't think of a better way at the moment. • Mar 28, 2018 at 11:45 # Python 2, 70 bytes -2 bytes thanks to @LeakyNun -2 bytes thanks to @JonathanFrech i=I=input() l=[I]*I exec"exec'print l;l[-i]-=1;'*max(~-i,2);i-=1;"*~-I  Try it online! • (I-1) --> ~-I Mar 28, 2018 at 13:50 • 70 bytes, initializing i=I and decrementing. Mar 28, 2018 at 13:58 # Java (JDK 10), 112 bytes n->{var s="";for(int i=1,k=n,j;i<=n;k=--k>i?k:n-++i+i)for(j=0;j++<n;)s+=(j<i?j:j>i?n:k)+(j<n?",":";");return s;}  Try it online! # J, 17 15 bytes +/\@,(#=)@i.&.-  Try it online! ## Explanation +/\@,(#=)@i.&.- Input: n - Negate n i. Reverse of range [0, n) = Identity matrix of order n # Copy each row by the reverse range - Negate , Prepend n +/\ Cumulative sum of rows  # Retina, 49 bytes .+ * _$_,$= .{*\_+,(_+)$.1
0(\b(_+),\2)_
$1  Try it online! Explanation: .+ *  Convert the input to unary. _$_,$=  Create a list of n copies of i,n where i is the index of the copy. .  Don't print anything (when the loop finishes). {  Loop until the pattern does not change. *\_+,(_+)$.1


Temporarily delete the is and convert the ns to decimal and output.

0(\b(_+),\2)_
\$1


Take the first list entry whose value exceeds its index and decrement it.

# Python 3, 7067 65 bytes

def f(n):
k=0;a=[n]*n
while k<n-1:print(a);k+=a[k]==k+1;a[k]-=1


Try it online!

• (67) Converting to function: -3 bytes
• (65) Removing unneeded parentheses: -2 bytes

Ungolfed version:

def f(n):
k = 0
a = [n] * n             # create n-item list with all n's
while k < n - 1:        # iterate through columns 0..n-1
print(a)            # print whole list
if a[k] == k + 1:   # move to the next column when current item reaches k+1
k += 1
a[k] -= 1           # decrement current item


# C (clang), 131 141 bytes

i,j,k,m;p(){for(k=0;m[k];printf("%d ",m[k++]));puts("");}f(n){for(j=k=m[n]=0;k<n;m[k++]=n);p();for(;j<n;j++)for(i=1;i++<n-j;m[j]--,p());}


Try it online!

This will work for all n upto 99. TIO truncates output. It can support arbitrarily larger n by changing size of array m as memory permits.

Following is limited to n=1..9 but is significantly shorter

# C (clang), 89 92 bytes

i,j;char m;f(n){j=!puts(memset(m,n+48,n));for(;j<n;j++)for(i=1;i++<n-j;m[j]--,puts(m));}


Try it online!

Updated: Modified to avoid dependence on static initialization

• Your static/global initialization because multiple test cases is not allowed, as functions have to be callable more than once. Mar 28, 2018 at 19:07
• @Jonathan Updated answers. I always wondered if this should be allowed, and couldn't make up my mind.
– GPS
Mar 29, 2018 at 9:05
• Here is the relevant meta post: codegolf.meta.stackexchange.com/a/4940/73111 Mar 29, 2018 at 10:33
• You could golf m[j]--,p() to p(m[j]--) and save a byte. Mar 29, 2018 at 10:36
• 128 bytes Oct 6, 2018 at 5:05

## Clojure, 132 bytes

#(loop[R[(vec(repeat % %))]j(- % 2)i 0](if(> i j)R(recur(conj R(update(last R)i dec))(if(= i j)(- % 2)(dec j))(if(= i j)(inc i)i))))


I was hoping this to be shorter...

Less stateful but longer at 141 bytes:

#(apply map list(for[i(range %)](concat(repeat(nth(cons 0(reductions +(reverse(range %))))i)%)(range % i -1)(if(>(dec %)i)(repeat(inc i))))))


# Python 3, 101 bytes

def f(n):
p=print;m=[n for_ in range(n)];p(m)
for i in range(n):
while m[i]>1+i:m[i]-=1;p(m)


I could probably golf more with the print, but I'm away from my computer and am not entirely sure of python 2's rules on setting a variable to print. I'll update later when I get to a computer or if someone clarifies in the comments.

# K (ngn/k), 34 32 bytes

{{x[y]-:1;x}\(,x#x),,/(|!x)#'!x}
`

Try it online!