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.
Euclidean rhythm
You are encouraged to solve this task according to the task description, using any language you may know.
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
Go
package main
import (
"fmt"
"math"
)
func main() {
result := generateSequence(5, 13)
fmt.Println(result) // Should print 1001010010100
}
func generateSequence(k int, n int) string {
var s [][]int
for i := 0; i < n; i++ {
var innerList []int
if i < k {
innerList = append(innerList, 1)
} else {
innerList = append(innerList, 0)
}
s = append(s, innerList)
}
d := n - k
n = int(math.Max(float64(k), float64(d)))
k = int(math.Min(float64(k), float64(d)))
z := d
for z > 0 || k > 1 {
for i := 0; i < k; i++ {
s[i] = append(s[i], s[len(s)-1-i]...)
}
s = s[:len(s)-k]
z -= k
d = n - k
n = int(math.Max(float64(k), float64(d)))
k = int(math.Min(float64(k), float64(d)))
}
var result string
for _, sublist := range s {
for _, item := range sublist {
result += fmt.Sprintf("%d", item)
}
}
return result
}
- Output:
1001010010100
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
jq
Adapted from Wren
Works with gojq, the Go implementation of jq
def E(k; n):
def list($value): [range(0,.) | $value];
{s: ((k|list([1])) + ((n-k)|list([0]))),
d: (n - k) }
| .n = ([k, .d]|max)
| .k = ([k, .d]|min)
| .z = .d
| until (.z <= 0 and .k <= 1;
reduce range(0; .k) as $i (.; .s[$i] += .s[-1 - $i])
| .s = .s[0: -.k]
| .z -= .k
| .d = .n - .k
| .n = ([.k, .d] | max)
| .k = ([.k, .d] | min) )
| .s
| [.[][]]
| join("");
E(5; 13)
- 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]
Julia
function E(k, n)
s = [[i <= k ? 1 : 0] for i in 1:n]
d = n - k
n, k = max(k, d), min(k, d)
z = d
while z > 0 || k > 1
for i in 1:k
append!(s[i], s[end - i + 1])
end
s = s[1:end-k]
z -= k
d = n - k
n, k = max(k, d), min(k, d)
end
return vcat(s...)
end
# Test the function
print(join(E(5, 13), ""))
# Output should be 1001010010100
- Output:
1001010010100
Kotlin
class SequenceGenerator {
companion object {
fun generateSequence(k: Int, n: Int): String {
var s = Array(n) { mutableListOf<Int>() }
for (i in 0 until n) {
if (i < k) {
s[i].add(1)
} else {
s[i].add(0)
}
}
var d = n - k
var nVar = maxOf(k, d)
var kVar = minOf(k, d)
var z = d
while (z > 0 || kVar > 1) {
for (i in 0 until kVar) {
s[i].addAll(s[s.size - 1 - i])
}
s = s.copyOfRange(0, s.size - kVar)
z -= kVar
d = nVar - kVar
nVar = maxOf(kVar, d)
kVar = minOf(kVar, d)
}
val result = s.flatMap { it }.joinToString(separator = "") { it.toString() }
return result
}
}
}
// Example usage
fun main() {
val result = SequenceGenerator.generateSequence(k = 5, n = 13)
println(result) // Should print 1001010010100
}
- Output:
1001010010100
Lua
function E(k, n)
local s = {}
for i = 1, n do
if i <= k then
table.insert(s, {1})
else
table.insert(s, {0})
end
end
local d = n - k
n = math.max(k, d)
k = math.min(k, d)
local z = d
while z > 0 or k > 1 do
for i = 1, k do
for _, v in ipairs(s[#s - i + 1]) do
table.insert(s[i], v)
end
end
for i = 1, k do
table.remove(s)
end
z = z - k
d = n - k
n = math.max(k, d)
k = math.min(k, d)
end
local result = {}
for _, sublist in ipairs(s) do
for _, item in ipairs(sublist) do
table.insert(result, item)
end
end
return result
end
local result = E(5, 13)
for _, v in ipairs(result) do
io.write(v)
end
io.write('\n')
-- Output should be 1001010010100
- Output:
1001010010100
Mathematica/Wolfram Language
funcE[inputk_, inputn_] := Module[{s, d, z, i},
k=inputk; n=inputn;
s = Table[If[i <= k, {1}, {0}], {i, 1, n}];
d = n - k;
{n, k} = {Max[k, d], Min[k, d]};
z = d;
While[z > 0 || k > 1,
For[i = 1, i <= k, i++,
s[[i]]=Join[s[[i]], s[[Length[s] - i + 1]]]
];
s = Take[s, Length[s] - k];
z -= k;
d = n - k;
{n, k} = {Max[k, d], Min[k, d]};
];
Flatten[s]
]
(* Test the function *)
StringJoin[ToString /@ funcE[5, 13]] //Print
(* The output should be "1001010010100" *)
- Output:
1001010010100
MATLAB
clear all;close all;clc;
disp(num2str(funcE(5, 13)))
function result = funcE(k, n)
s = cell(1, n);
for i = 1:n
s{i} = (i <= k);
end
d = n - k;
[n, k] = deal(max(k, d), min(k, d));
z = d;
while z > 0 || k > 1
for i = 1:k
s{i} = [s{i}, s{end - i + 1}];
end
s = s(1:end-k);
z = z - k;
d = n - k;
[n, k] = deal(max(k, d), min(k, d));
end
result = [s{:}];
end
- Output:
1 0 0 1 0 1 0 0 1 0 1 0 0
Perl
use strict;
use warnings;
sub E {
my ($k, $n) = @_;
my @s = map { $_ < $k ? [1] : [0] } (0..$n-1);
my $d = $n - $k;
$n = $k > $d ? $k : $d;
$k = $k < $d ? $k : $d;
my $z = $d;
while ($z > 0 || $k > 1) {
foreach my $i (0..$k-1) {
push(@{$s[$i]}, @{$s[-1 - $i]});
}
splice(@s, -$k);
$z -= $k;
$d = $n - $k;
$n = $k > $d ? $k : $d;
$k = $k < $d ? $k : $d;
}
return map { @$_ } @s;
}
my $sequence = join('', E(5, 13));
print "$sequence\n";
# Expected output: 1001010010100
- Output:
1001010010100
Phix
function Euclidean_rhythm(integer k, n)
integer d = n - k, z = d
sequence s = repeat("1",k) & repeat("0",d)
n = max(k, d)
k = min(k, d)
while z > 0 or k > 1 do
string last = s[$]
assert(s[-k]==last)
for i=1 to k do
s[i] &= last
end for
s = s[1..-k-1]
z -= k
d = n - k
n = max(k, d)
k = min(k, d)
end while
return join(s,"")
end function
?Euclidean_rhythm(5,13)
- Output:
"1001010010100"
PHP
<?php
function E($k, $n) {
$s = array();
for ($i = 0; $i < $n; $i++) {
$s[] = $i < $k ? array(1) : array(0);
}
$d = $n - $k;
$n = max($k, $d);
$k = min($k, $d);
$z = $d;
while ($z > 0 || $k > 1) {
for ($i = 0; $i < $k; $i++) {
$s[$i] = array_merge($s[$i], $s[count($s) - 1 - $i]);
}
$s = array_slice($s, 0, -$k);
$z = $z - $k;
$d = $n - $k;
$n = max($k, $d);
$k = min($k, $d);
}
$result = array();
foreach ($s as $sublist) {
$result = array_merge($result, $sublist);
}
return $result;
}
// Example usage
echo implode('', E(5, 13)); // 1001010010100
- Output:
1001010010100
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
R
E <- function(k, n) {
s <- lapply(1:n, function(i) if (i <= k) 1 else 0)
d <- n - k
n <- max(k, d)
k <- min(k, d)
z <- d
while (z > 0 || k > 1) {
for (i in 1:k) {
s[[i]] <- c(s[[i]], s[[length(s) - i + 1]])
}
s <- s[1:(length(s) - k)]
z <- z - k
d <- n - k
n <- max(k, d)
k <- min(k, d)
}
unlist(s)
}
# Test the function
cat(E(5, 13), sep = "")
# Output should be 1001010010100
- Output:
1001010010100
Ruby
def e(k, n)
s = (0...n).map { |i| i < k ? [1] : [0] }
d = n - k
n = [k, d].max
k = [k, d].min
z = d
while z > 0 or k > 1
k.times do |i|
s[i].concat(s[-1 - i])
end
s = s[0...-k]
z -= k
d = n - k
n = [k, d].max
k = [k, d].min
end
s.flatten.join
end
puts e(5, 13)
# Should output: 1001010010100
- Output:
1001010010100
Rust
fn e(k: i32, n: i32) -> Vec<u8> {
let mut s: Vec<Vec<u8>> = (0..n)
.map(|i| if i < k { vec![1] } else { vec![0] })
.collect();
let mut d = n - k;
let mut n = std::cmp::max(k, d);
let mut k = std::cmp::min(k, d);
let mut z = d;
while z > 0 || k > 1 {
for i in 0..(k as usize) {
let mut extension = s[s.len() - 1 - i].clone();
s[i].append(&mut extension);
}
s.truncate(s.len() - (k as usize));
z -= k;
d = n - k;
n = std::cmp::max(k, d);
k = std::cmp::min(k, d);
}
s.into_iter().flatten().collect()
}
fn main() {
let result = e(5, 13);
let result_string: String = result.into_iter().map(|digit| digit.to_string()).collect();
println!("{}", result_string);
}
- Output:
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.