Generate lists in which every sublist has a unique element

The problem is defined as follows:

Create a function that takes an integer and returns a list of integers, with the following properties:

• Given a positive integer input, n, it produces a list containing n integers ≥ 1.
• Any sublist of the output must contain at least one unique element, which is different from all other elements from the same sublist. Sublist refers to a contiguous section of the original list; for example, [1,2,3] has sublists [1], [2], [3], [1,2], [2,3], and [1,2,3].
• The list returned must be the lexicographically smallest list possible.

There is only one valid such list for every input. The first few are:

f(2) = [1,2]         2 numbers used
f(3) = [1,2,1]       2 numbers used
f(4) = [1,2,1,3]     3 numbers used

• Wouldn't [1,2,1] be incorrect because elements 1 are the same? Commented Jan 31, 2014 at 16:52
• I'm sorry, you're going to have to better define "lexicographically" better over the solution space. Commented Jan 31, 2014 at 16:52
• e.g. why isn't [0,1] better than [1,2] for f(2)? Commented Jan 31, 2014 at 16:54
• @Timtech: No, because the first 1 is in another sublist than the second 1. A sublist is a contiguous section of the original list, so there are three sublists: [1] [1,2] [1] Commented Jan 31, 2014 at 16:55
• @ProgramFOX and everyone who voted to close this, since this question is tagged as code-golf I think we do have an objective winning criterion? Commented Jan 31, 2014 at 22:55

APL, 18

{+⌿~∨⍀⊖(⍵/2)⊤2×⍳⍵}


1 + number of trailing zeros in base 2 of each natural from 1 to N.

Example

      {+⌿~∨⍀⊖(⍵/2)⊤2×⍳⍵} 32
1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 6


GolfScript (20 18 chars)

{,{.)^2base,}%}:f;


This is a simple binary ruler function, A001511.

Equivalently

{,{).~)&2base,}%}:f;
{,{~.~)&2base,}%}:f;
{,{).(~&2base,}%}:f;
{,{{1&}{2/}/,)}%}:f;


Thanks for primo for saving 2 chars.

• ).~)& -> .)^ for 2. Commented Jan 31, 2014 at 18:37

Sclipting, 26 23 characters

감⓶上가增❷要❶감雙是가不감右⓶增⓶終終丟丟⓶丟終并


This piece of code generates a list of integers. However, if run as a program it will concatenate all the numbers together. As a stand-alone program, the following 25-character program outputs the numbers separated by commas:

감⓶上가增❷要감嚙是가不⓶增⓶終終丟丟⓶丟껀終合鎵


Example output:

Input: 4

Output: 1,2,1,3

Input: 10

Output: 1,2,1,3,1,2,1,4,1,2

Jelly, 4 bytes

ọ€2‘


Try it online!

Explanation

ọ€2‘
€      For each integer from 1 to {the command-line argument}
ọ         calculate the number of trailing zeroes in base
2         2
‘    and increment {each resulting integer} {and output them}


Python 2.7, 65 characters

print([len(bin(2*k).split('1')[-1]) for k in range(1,input()+1)])


The number of trailing zeros in 2, 4, 6, ..., 2n.

n&p=n:p++(n+1)&(p++n:p)
f n=take n\$1&[]


Example runs:

λ: f 2
[1,2]
λ: f 3
[1,2,1]
λ: f 4
[1,2,1,3]
λ: f 10
[1,2,1,3,1,2,1,4,1,2]
λ: f 38
[1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,6,1,2,1,3,1,2]


Japt, 9 bytes

õÈ¤q1 ÌÊÄ


Try it

(taket)