Combinations of stepwise increasing integers

Question

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.

Task

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.

Answer 1

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 2^n-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

Answer 2

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

Answer 3

Jelly, 17 16 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].
   +     Then add
    Ç    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.

Answer 4

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

Answer 5

APL (Dyalog Unicode), 29 bytes^SBCS

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

Answer 6

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.

Answer 7

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!

Answer 8

Python 3, ¹¹¹ 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.

Answer 9

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.

Answer 10

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!

Answer 11

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.

Answer 12

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
0020 69 00     ADC #0     ; add with 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.