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? – Timtech Jan 31 '14 at 16:52
• I'm sorry, you're going to have to better define "lexicographically" better over the solution space. – McKay Jan 31 '14 at 16:52
• e.g. why isn't [0,1] better than [1,2] for f(2)? – McKay Jan 31 '14 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] – ProgramFOX Jan 31 '14 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? – ace Jan 31 '14 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. – primo Jan 31 '14 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

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]


Golfscript - 1 character

,


I'm pretty sure this meets the criteria, but it does seem weirdly worded.

• It seems to me that something like this would work, +1. – Timtech Jan 31 '14 at 16:47
• Excuse me? For input 3 this would generate 1,2,3, which is wrong because 1,2,1 is correct and lexicographically smaller. – Timwi Jan 31 '14 at 16:48
• Timwi's point aside, the convention for questions which ask specifically for a function is that GolfScript answers should define a named block and then clear it from the stack: i.e. the boilerplate is a prefix of { and a suffix of }:f; – Peter Taylor Jan 31 '14 at 17:17
• @PeterTaylor So, when they say "function", and most programming languages get to cut out crap like classes and using directives..., GolfScript has more boilerplate that has to be thrown on? – McKay Jan 31 '14 at 18:07
• And even if actually creating a named block is important, why does it have to be dropped from the stack? – McKay Jan 31 '14 at 18:12