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.
C#
using System;
using System.Collections.Generic;
using System.Text;
public class SequenceGenerator
{
public static void Main(string[] args)
{
string result = GenerateSequence(5, 13);
Console.WriteLine(result); // Should print 1001010010100
}
public static string GenerateSequence(int k, int n)
{
List<List<int>> s = new List<List<int>>();
for (int i = 0; i < n; i++)
{
List<int> innerList = new List<int>();
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[i].AddRange(s[s.Count - 1 - i]);
}
s = s.GetRange(0, s.Count - k);
z -= k;
d = n - k;
n = Math.Max(k, d);
k = Math.Min(k, d);
}
StringBuilder result = new StringBuilder();
foreach (List<int> sublist in s)
{
foreach (int item in sublist)
{
result.Append(item);
}
}
return result.ToString();
}
}
- Output:
1001010010100
Dart
List<int> E(int k, int n) {
List<List<int>> s = List.generate(n, (i) => i < k ? [1] : [0]);
int d = n - k;
n = k > d ? k : d;
k = k < d ? k : d;
int z = d;
while (z > 0 || k > 1) {
for (int i = 0; i < k; i++) {
s[i].addAll(s[s.length - 1 - i]);
}
s = s.sublist(0, s.length - k);
z -= k;
d = n - k;
n = k > d ? k : d;
k = k < d ? k : d;
}
return s.expand((sublist) => sublist).toList();
}
void main() {
print(E(5, 13).join());
// Expected output: 1001010010100
}
- Output:
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
Raku
# 20240208 Raku programming solution
say sub ($k is copy, $n is copy) {
my @s = [ [1] xx $k ].append: [0] xx ($n - $k);
my $z = my $d = $n - $k;
($k, $n) = ($d, $k).minmax.bounds;
while $z > 0 || $k > 1 {
^$k .map: { @s[$_].append: |@s[*-1 - $_] }
@s.splice(*-$k);
($z, $d) = ($z, $n) >>->> $k;
($k, $n) = ($d, $k).minmax.bounds;
}
return [~] @s>>.List.flat;
}(5, 13);
You may Attempt This Online!
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.