Combinations of stepwise increasing integers

Working on something in probability theory, I stumbled across another combinatorical exercise. These are always fun to solve, searching for intelligent approaches. Of course, one can use brute force for the following task, but this challenge is restricted complexity, so this is not allowed.

Given an integer Input $$\n > 1\$$, print all integer vectors of length $$\n\$$, respecting following conditions:

• $$\v_1 = 1\$$
• $$\v_{i+1} - v_i \in \{0,1\}\$$
• $$\v_n \neq n\$$

example:

Input:

n=4

Output:

[1 1 1 1]

[1 1 1 2]

[1 1 2 2]

[1 1 2 3]

[1 2 2 2]

[1 2 2 3]

[1 2 3 3]


Additionally, time complexity of your solution must be $$\O(2^n)\$$. Note that generating all vectors and then filtering would be $$\O(n^n)\$$, which is not acceptable. A direct construction, not generating any false vector or duplicate vector at all, seems to be a bit more of a challenge.

Having said that, shortest code in bytes, respecting the above condition, wins.

• Would it be correct to assume [1 2 3 4] would also be a valid output for your example, meaning there would be 2^(n-1) total outputs? – Mathgeek Feb 11 at 14:11
• @Neil so this is essentially what mathgeek was saying, except we have $2^{n-1}-1$ – RGS Feb 11 at 14:29
• brute force (…) wouldn't fulfill winning criteria. contradicts code-golf. – Adám Feb 11 at 14:33
• Welcome to the site. I am voting to close this as unclear. This is because a blanket ban on "brute force" answers is not objective. There is a ton of grey area as to what counts as "direct construction". You can make this restricted-complexity to make it objective, where you specify maximum asymptotic complexity requirements, a measure that is objective and indisputable. – Ad Hoc Garf Hunter Feb 11 at 14:55
• I'm voting to close this question as off-topic because it has an unobservable requirement making it impossible to objectively tell if any given answer is valid and thus it's not clear if it wins. – Giuseppe Feb 11 at 17:52

Ruby, 65 55 bytes

->n{(0..2**~-n-2).map{|x|w=1;(1..n).map{|d|w+=x[n-d]}}}


Try it online!

How:

Partial sum of bits (starting with 1) of all numbers up to 2n-1-2

For example: if the number is 111010011 it becomes:

  1 1 1 0 1 0 0 1 1
| | |   |     | |
v v v   v     v v
+1+1+1  +1    +1+1
-----------------
1 2 3 4 4 5 5 5 6 7
|
Initialized to 1


05AB1E, 10 9 bytes

<oxÍŸεbηO


Try it online!

<           # decrement: n-1
o          # 2**(n-1)
x         # push 2 * 2**(n-1) = 2**n without popping
Í        # 2**n - 2
Ÿ       # range [2**(n-1), ..., 2**n - 2]
ε      # for each number in that range:
b     #  convert it to binary
η    #  prefixes
O   #  sum each prefix


Jelly, 1716 11 bytes

’2*
Ç’Ḷ+ÇBÄ


You can try it online!

’2*      Compute 2^(n-1) (let me call it x).
Ç’       Take x and decrement it,
Ḷ      creating the range [0, ..., x-1].
Ç    x to every element in said range,
B   take its binary representation
Ä  and then take the cumulative sums.


This is a golfed version of the following:

The condition $$\v_{i+1} - v_i \in \{0, 1\}\$$ means we can instead generate all the sequences $$\d_i\$$ of $$\n - 1\$$ elements with $$\d_i \in \{0, 1\}\$$ and then generate a vector $$\v\$$ as such:

$$\begin{cases} v_1 = 1 \\ v_{i+1} = v_i + d_i \end{cases}\tag{1}$$

The only sequence we can't consider is when $$\d_i = 1\ \forall i\$$ because in that case, $$\v_n = n\$$, which can't happen as per the OP. On top of that, we can see the sequences $$\\{d_i\}_{i=1}^{n-1}\$$ as the binary numbers from $$\0\$$ to $$\2^{n-1} - 1\$$. So we do just that: find the binary representation of all integers from $$\0\$$ to $$\2^{n-1}-1\$$ and take those sequences as the jumps, to define $$\v\$$ as per $$\(1)\$$.

’                  Take the input integer and subtract 1,
2*                take 2 to the power of that
’               and finally decrement again (this builds 2^(n-1) - 1).
Ḷ              Take the lower range [0, ... (2^(n-1)-1) - 1]
B             and write every number in the range in binary.
€      Now, for each binary representation
¿       While said binary representation
L<³Ɗ        has length smaller than the input number,
Ż            prepend a 0 to it.
Ä     Take the cumulative sum of every binary representation
+1   and add 1 to every element.


Charcoal, 20 bytes

ＩＥ⊖Ｘ²⊖θ⮌ＥＩθ⊕Σ⍘÷ιＸ²λ²


Try it online! Link is to verbose version of code. Explanation:

    ²                  Literal 2
Ｘ                   To power
θ                 Input
⊖                  Decremented
⊖                     Decremented
Ｅ                      Map over implicit range
θ             Input
Ｉ              Cast to integer
Ｅ               Map over implicit range
ι        Outer index
÷         Integer divide by
²      Literal 2
Ｘ       To power
λ     Inner index
⍘     ²    Convert to base 2
Σ           Digital sum
⊕            Incremented
⮌                Reversed
Ｉ                       Cast to string
Implicitly print


APL (Dyalog Unicode), 29 bytesSBCS

Full program.

¯1↓{⊃,/(⊂,¨0 1+⊢/)¨⍵}⍣(⎕-1),1


Try it online!

,1 the list [1]

{}⍣(⎕-1) apply the following anonymous lambda one-less-than input times:

()⍵ on the argument:

⊢/ take the last element (lit. right-argument reduction)

0 1+ add [0,1] to that

⊂,¨ concatenate each to the entire argument

,/ flatten (lit. concatenation reduction)

⊃ disclose (since the reduction enclosed to reduce rank from 1 to 0)

¯1↓ drop the last

GolfScript, 70 bytes

[]\(:m 2\?:p{(.[2 base]@\+\.}do;{.,m\-[0]\*\+}%{1:s;{s+:s}%[1]\+ }%(;


Try it online!

This is just my first stab, I have a few ideas on how to improve, but this is my hot garbage to start with. My goal is to get it under 50, then I'll write a full explanation.

The short is that it writes every binary combination, sums the elements recursively, then adds 1 to the front.

JavaScript (V8),  72 69  68 bytes

f=(n,a=1,p=1,m=n)=>--m?[p,p+1].map(p=>p<n&&f(n,a+[,p],p,m)):print(a)


Try it online!

Pyth, 12 bytes

msM._dPh#^U2


Try it online!

Make all length n sequences of 0,1, filler for the ones that start with 1, remove the all ones sequence, form prefixes, soon the prefixes.

Python 3, 111 108 bytes

def f(n):
for i in range(2**(n-1)-1):
v,j=[],1
for c in bin(i)[2:].zfill(n):j+=int(c);v+=[j]
print(v)


Try it online!

No gigantic superset just straight up generation of vectors using G B's partial sum of bits idea.

Python 2, 62 bytes

f=lambda n:1/n*[[1]]or[x+[x[-1]+d]for d in 0,1for x in f(n-1)]


Try it online!

R, 69 bytes

f=function(n,m=1,?=cbind)"if"(n-1,rbind(f(n-1,1?m),f(n-1,1?m+1)),m)


Try it online!

Simple recursive solution; returns a matrix where each row is one of the valid lists.

6502, 31 bytes

0016           .function
0016 A0 FE     LDY #FEh   ; starting bit pattern
0018           .again
0018 84 41     STY 41h    ; store current bit pattern in scratchpad
001A A9 31     LDA #049   ; ASCII "1"
001C A6 40     LDX 40h    ; load index with vector size
001E           .more_bits
001E 46 41     LSR 41h    ; shift lsb into carry
0022 85 0F     STA 0Fh    ; display ASCII char
0029 CA        DEX        ; decrease index
002A D0 F2     BNE 1Eh    ; more bits if index not zero
0024 C9 31     CMP #049   ; sequence ends in "1" so all bits zero
0026 D0 01     BNE 2Ch    ; continue
0028 60        RTS        ; exit function
0029           .continue
002C A9 2C     LDA #044   ; display...
002E 85 0F     STA 0Fh    ; ... comma
0030 88        DEY        ; next ...
0031 88        DEY        ; ... bit pattern
0032 4C 18 00  JMP 0018h  ; go again
`

Try It On Visual6502.org

(Press the Play button to run the program. Press Trace Less to speed up simulation). Input is at memory location 40 hex - click and enter hex numbers to modify before running. Since the 6502 is an eight bit microprocessor, for golfing purposes input is restricted from 1 to 8.