Euclidean rhythm
The Euclidean rhythm was proposed by Godfried Toussaint in 2004 and is described in a 2005 paper "The Euclidean Algorithm Generates Traditional Musical Rhythms".[1] It generates many forms of rhythm in music around the world. The program takes 2 integers (m, n) and outputs a binary string with m ones and (n-m) zeros.
![Task](http://static.miraheze.org/rosettacodewiki/thumb/b/ba/Rcode-button-task-crushed.png/64px-Rcode-button-task-crushed.png)
You are encouraged to solve this task according to the task description, using any language you may know.
As an example, here is how it runs on (5, 13):
- Write 5 ones followed by (13-5) zeros, into 13 groups of 1-digit each:
- 1 1 1 1 1 | 0 0 0 0 0 0 0 0
- Repeatedly append substitute the second group into the first group:
- 1 1 1 1 1 | 0 0 0 0 0 0 0 0
- 10 10 10 10 10 | 0 0 0
- 100 100 100 10 10 |
- If the first group consists of elements of the same form, then output. Otherwise, divide the first group into two groups of the two forms, and repeat the process:
- 100 100 100 10 10 |
- 100 100 100 | 10 10
- 10010 10010 100 |
- At this point, we can continue the algorithm until only one form remains, but notice that one of the groups has only one element [100], so the algorithm can actually terminate right here and output the concatenation 1001010010100.
EasyLang
func$ euclrhythm k n .
for i to n
h = if i <= k
s[][] &= [ h ]
.
d = n - k
n = higher k d
k = lower k d
z = d
while z > 0 or k > 1
for i to k
for c in s[len s[][] + 1 - i][]
s[i][] &= c
.
.
len s[][] -k
z = z - k
d = n - k
n = higher k d
k = lower k d
.
for i to len s[][]
for v in s[i][]
r$ &= v
.
.
return r$
.
print euclrhythm 3 8
- Output:
10010010
Java
import java.util.ArrayList;
import java.util.List;
public class SequenceGenerator {
public static void main(String[] args) {
String result = generateSequence(5, 13);
System.out.println(result); // Should print 1001010010100
}
public static String generateSequence(int k, int n) {
List<List<Integer>> s = new ArrayList<>();
for (int i = 0; i < n; i++) {
List<Integer> innerList = new ArrayList<>();
if (i < k) {
innerList.add(1);
} else {
innerList.add(0);
}
s.add(innerList);
}
int d = n - k;
n = Math.max(k, d);
k = Math.min(k, d);
int z = d;
while (z > 0 || k > 1) {
for (int i = 0; i < k; i++) {
s.get(i).addAll(s.get(s.size() - 1 - i));
}
s = s.subList(0, s.size() - k);
z -= k;
d = n - k;
n = Math.max(k, d);
k = Math.min(k, d);
}
StringBuilder result = new StringBuilder();
for (List<Integer> sublist : s) {
for (int item : sublist) {
result.append(item);
}
}
return result.toString();
}
}
- Output:
1001010010100
JavaScript
Copied from here and here, under MIT license.
const E = (k, n) => {
let s = Array(n).fill(0)
.map((_, i) => (i < k ? [1] : [0]))
let d = n - k
n = Math.max(k, d)
k = Math.min(k, d)
let z = d
while (z > 0 || k > 1) {
for (let i = 0; i < k; i++)
s[i].push(...s[s.length - 1 - i])
s.splice(-k)
z = z - k
d = n - k
n = Math.max(k, d)
k = Math.min(k, d)
}
return s.flat()
}
Output:
> E(3,8)
[1, 0, 0, 1, 0, 0, 1, 0]
Python
def E(k, n):
s = [[1] if i < k else [0] for i in range(n)]
d = n - k
n = max(k, d)
k = min(k, d)
z = d
while z > 0 or k > 1:
for i in range(k):
s[i].extend(s[len(s) - 1 - i])
s = s[:-k]
z = z - k
d = n - k
n = max(k, d)
k = min(k, d)
return [item for sublist in s for item in sublist]
print(''.join(map(str, E(5, 13))))
# 1001010010100
Scala
object SequenceGenerator {
def main(args: Array[String]): Unit = {
val result = generateSequence(5, 13)
println(result) // Should print 1001010010100
}
def generateSequence(k: Int, n: Int): String = {
var s = List.fill(n)(List(0)).zipWithIndex.map { case (list, index) =>
if (index < k) List(1) else List(0)
}
var (d, nVar, kVar, z) = (n - k, math.max(k, n - k), math.min(k, n - k), n - k)
while (z > 0 || kVar > 1) {
for (i <- 0 until kVar) {
s = s.updated(i, s(i) ++ s(s.size - 1 - i))
}
s = s.take(s.size - kVar)
z -= kVar
d = nVar - kVar
nVar = math.max(kVar, d)
kVar = math.min(kVar, d)
}
s.flatten.mkString
}
}
- Output:
1001010010100
Swift
import Foundation
class SequenceGenerator {
static func generateSequence(k: Int, n: Int) -> String {
var s = Array(repeating: [Int](), count: n)
for i in 0..<n {
if i < k {
s[i].append(1)
} else {
s[i].append(0)
}
}
var d = n - k
var nVar = max(k, d)
var kVar = min(k, d)
var z = d
while z > 0 || kVar > 1 {
for i in 0..<kVar {
s[i].append(contentsOf: s[s.count - 1 - i])
}
s = Array(s[0..<(s.count - kVar)])
z -= kVar
d = nVar - kVar
nVar = max(kVar, d)
kVar = min(kVar, d)
}
let result = s.flatMap { $0 }.map { String($0) }.joined()
return result
}
}
// Example usage
let result = SequenceGenerator.generateSequence(k: 5, n: 13)
print(result) // Should print 1001010010100
- Output:
1001010010100
Wren
import "./seq" for Lst
var E = Fn.new { |k, n|
var s = (0...n).map { |i| i < k ? [1] : [0] }.toList
var d = n - k
n = k.max(d)
k = k.min(d)
var z = d
while (z > 0 || k > 1) {
for (i in 0...k) s[i].addAll(s[-1 - i])
s = s[0...-k]
z = z - k
d = n - k
n = k.max(d)
k = k.min(d)
}
return Lst.flatten(s)
}
System.print(E.call(5, 13).join())
- Output:
1001010010100
Zig
const std = @import("std");
const allocator = std.heap.page_allocator;
pub fn main() !void {
const result = try generateSequence(5, 13);
for (result) |item| {
std.debug.print("{}", .{item});
}
std.debug.print("\n", .{});
}
fn generateSequence(_k: i32, _n: i32) ![]i32 {
var k=_k; var n=_n;
var s = std.ArrayList(std.ArrayList(i32)).init(allocator);
for (0..@as(usize, @intCast(n))) |i| {
var innerList = std.ArrayList(i32).init(allocator);
if (i < k) {
try innerList.append(1);
} else {
try innerList.append(0);
}
try s.append(innerList);
}
var d:i32 = n-k;
n = @max(k, d);
k = @min(k, d);
var z = d;
while (z > 0 or k > 1) {
for (0..@as(usize, @intCast(k))) |i| {
var lastList = s.items[s.items.len - 1 - i];
for (lastList.items) |item| {
try s.items[i].append(item);
}
}
s.shrinkRetainingCapacity(s.items.len - @as(usize, @intCast(k)));
z -= k;
d = n - k;
n = @max(k, d);
k = @min(k, d);
}
var result = std.ArrayList(i32).init(allocator);
for (s.items) |sublist| {
for (sublist.items) |item| {
try result.append(item);
}
}
return result.toOwnedSlice();
}
- Output:
1001010010100
- ↑ The Euclidean algorithm generates traditional musical rhythms by G. T. Toussaint, Proceedings of BRIDGES: Mathematical Connections in Art, Music, and Science, Banff, Alberta, Canada, July 31 to August 3, 2005, pp. 47–56.