Generating Euclidean rhythms

Question

Did you know that the Euclidean algorithm is capable of generating traditional musical rhythms? We'll see how this works by describing a similar, but slightly different algorithm to that in the paper.

Pick a positive integer n, the total number of beats, and a positive integer k, the number of beats which are sounded (notes). We can think of the rhythm as a sequence of n bits, k of which are 1s. The idea of the algorithm is to distribute the 1s as evenly as possible amongst the 0s.

For example, with n = 8 and k = 5, we start with 5 ones and 3 zeroes, each in its own sequence:

[1] [1] [1] [1] [1] [0] [0] [0]

At any point we will have two types of sequences — the ones at the start are the "core" sequences and the ones at the end are the "remainder" sequences. Here the cores are [1]s and the remainders are [0]s. As long as we have more than one remainder sequence, we distribute them amongst the cores:

[1 0] [1 0] [1 0] [1] [1]

Now the core is [1 0] and the remainder is [1], and we distribute again:

[1 0 1] [1 0 1] [1 0]

Now the core is [1 0 1] and the remainder is [1 0]. Since we only have one remainder sequence, we stop and get the string

10110110

This is what it sounds like, repeated 4 times:

Here's another example, with n = 16 and k = 6:

[1] [1] [1] [1] [1] [1] [0] [0] [0] [0] [0] [0] [0] [0] [0] [0]
[1 0] [1 0] [1 0] [1 0] [1 0] [1 0] [0] [0] [0] [0]
[1 0 0] [1 0 0] [1 0 0] [1 0 0] [1 0] [1 0]
[1 0 0 1 0] [1 0 0 1 0] [1 0 0] [1 0 0]
[1 0 0 1 0 1 0 0] [1 0 0 1 0 1 0 0]
1001010010010100

Note how we terminated on the last step with two core sequences and no remainder sequences. Here it is, repeated twice:

Input

You may write a function or a full program reading from STDIN, command line or similar. Input will be two positive integers n and k <= n, which you may assume is in either order.

Output

Your task is to output the generated rhythm as an n character long string. You may pick any two distinct printable ASCII characters (0x20 to 0x7E) to represent notes and rests.

Test cases

The following test cases use x to represent notes and .s to represent rests. Input is given in the order n, then k.

1 1    ->  x
3 2    ->  xx.
5 5    ->  xxxxx
8 2    ->  x...x...
8 5    ->  x.xx.xx.
8 7    ->  xxxxxxx.
10 1   ->  x.........
11 5   ->  x.x.x.x.x..
12 7   ->  x.xx.x.xx.x.
16 6   ->  x..x.x..x..x.x..
34 21  ->  x.xx.x.xx.xx.x.xx.x.xx.xx.x.xx.x.x
42 13  ->  x...x..x..x..x...x..x..x..x...x..x..x..x..
42 18  ->  x..x.x.x..x.x.x..x.x.x..x.x.x..x.x.x..x.x.

Scoring

This is code-golf, so the code in the fewest bytes wins.

Answer 1

CJam, 37 34 30 27 24 bytes

3 bytes saved by user23013.

q~,f>{_(a-W<}{e`:a:e~z}w

This takes the input as k first, n second. It uses 1 and 0 to indicate notes and rests, respectively.

Try it here. Alternatively, here is a test harness which runs all of the given test cases (swapping the input order) and also reformats the output to use x and . for easier comparison with the reference solutions. (The results appearing in the input of the test harness are discarded before running the code. They could be safely removed without affecting the program.)

Explanation

q~                       e# Read and eval the input, dumping k and n on the stack.
  ,                      e# Create a range [0 .. n-1]
   f>                    e# For each of them, check if it's less than k.
                         e# This gives k 1s and n-k 0s.
     {      }{        }w e# While the first block yields a truthy result, execute
                         e# the second block.
      _                  e# Duplicate the array.
       (a-               e# Remove all instances of core sequences.
          W<             e# Remove one remainder sequence if there is one. This
                         e# gives an empty array (falsy) whenever there are less
                         e# than two remainder sequences.
              e`         e# Run-length encode. I.e. this turns an array into a list
                         e# of pairs of run-length and element.
                :a:e~    e# Wrap each RLE pair in an array and RLD it. This
                         e# partitions the array into cores and remainders.
                     z   e# Zip the two parts, interleaving cores and remainders.

This process very deeply nested arrays, but the important part is that all cores (and all remainders) always have the same nested structure, so they are still equal to each other. CJam automatically prints the stack contents at the end of the program and omits array delimiters entirely, hence this structure does not affect the output either.

Answer 2

Haskell, 125 bytes

r=replicate
g z(a:b)(c:d)=g((a++c):z)b d
g z x y=(z,x++y)
f(x,y)|length y>1=f$g[]x y|1<2=concat$x++y
n#k=f(r k "x",r(n-k)".")

Usage example: 42 # 13 -> x...x..x..x..x...x..x..x..x...x..x..x..x...

f takes two parameters: core and remainder list. It either zips both lists (via g) and calls itself again or stops if the remainder is too short. The main function # creates the starting lists and calls f.

Answer 3

Python, 85

f=lambda n,k,a='1',b='0':n-k<2and a*k+b*(n-k)or[f(n-k,k,a+b,b),f(k,n-k,a+b,a)][2*k>n]

The natural recursive solution. The parameters (n,k,a,b) represent a core of k a's followed by a remainder of n-k b's.

This solution is inefficient because both recursive calls to f are evaluated, causing an exponential number of calls.

I tried to compress the conditional invocation of f like

f(max(n-k,k),min(n-k,k),a+b,[a,b][2*k<n])
f(*[n-k,k,k,n-k,b,a][2*k>n::2]+[a+b])

but none turned out shorter.