Euclidean rhythm

You are encouraged to solve this task according to the task description, using any language you may know.
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.
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.
ALGOL 68
BEGIN # Euclidean Rhythm #
# returns the Euclidean rhythm string generated by m and n #
# 0 < m < n must be true #
PROC e rhythm = ( INT m, n )STRING:
BEGIN
[ 1 : n ]STRING r;
# the rhythm string is n elements, initially the first m are #
# set to "1" and the remainder set to "0" #
# the first part is defined by a start and a end and the #
# second part by b start and b end #
FOR i TO m DO r[ i ] := "1" OD;
FOR i FROM m + 1 TO n DO r[ i ] := "0" OD;
INT a start := 1, a end := m;
INT b start := m + 1, b end := n;
# the b elements are appended to the a elements and removed #
# until either a or b or both have less than two elements left #
WHILE a end > a start # at least two elements in a #
AND b end > b start # at least two elements in b #
DO
INT a pos := a start, b pos := b start;
WHILE a pos <= a end AND b pos <= b end DO
r[ a pos ] +:= r[ b pos ];
a pos +:= 1;
b pos +:= 1
OD;
IF b pos < b end THEN
# 2 or more unused elements left in b #
b start := b pos
ELSE
# nothing left in b - use the remains of a #
b start := a pos;
b end := a end;
a end := a pos - 1
FI
OD;
STRING result := "";
FOR i FROM a start TO a end DO result +:= r[ i ] OD;
FOR i FROM b start TO b end DO result +:= r[ i ] OD;
result
END # e rhythm # ;
print( ( e rhythm( 5, 13 ), newline ) ); # task test case #
print( ( e rhythm( 3, 8 ), newline ) ) # JaveScriipt test case #
END
- Output:
1001010010100 10010010
Asymptote
int m = 5;
int n = 13;
string r[] = new string[n];
int a_pio = 1, a_fin = m;
int b_pio = m + 1, b_fin = n;
int a_pos, b_pos;
for (int i = 1; i <= m; ++i)
r[i] = "1";
for (int i = m + 1; i <= n; ++i)
r[i] = "0";
while (a_fin > a_pio && b_fin > b_pio) {
a_pos = a_pio;
b_pos = b_pio;
while (a_pos <= a_fin && b_pos <= b_fin) {
r[a_pos] += r[b_pos];
++a_pos;
++b_pos;
}
if (b_pos < b_fin)
b_pio = b_pos;
else {
b_pio = a_pos;
b_fin = a_fin;
a_fin = a_pos - 1;
}
}
string result = "";
for (int i = a_pio; i <= a_fin; ++i)
result += r[i];
for (int i = b_pio; i <= b_fin; ++i)
result += r[i];
write(result);
- Output:
10010010
BASIC
BASIC256
arraybase 1
call euclideanrhythm(5, 13)
call euclideanrhythm(3, 8)
end
subroutine euclideanrhythm (m,n)
dim r$(n)
a_pio = 1
a_fin = m
b_pio = m+1
b_fin = n
for i = 1 to m
r$[i] = "1"
next i
for i = m+1 to n
r$[i] = "0"
next i
while a_fin > a_pio and b_fin > b_pio
a_pos = a_pio
b_pos = b_pio
while a_pos <= a_fin and b_pos <= b_fin
r$[a_pos] = r$[a_pos] & r$[b_pos]
a_pos = a_pos+1
b_pos = b_pos+1
end while
if b_pos < b_fin then
b_pio = b_pos
else
b_pio = a_pos
b_fin = a_fin
a_fin = a_pos-1
end if
end while
result$ = ""
for i = a_pio to a_fin
result$ = result$ & r$[i]
next i
for i = b_pio to b_fin
result$ = result$ & r$[i]
next i
print result$
end subroutine
- Output:
Same as FreeBASIC entry.
Chipmunk Basic
100 sub euclideanrhythm(m,n)
110 dim r$(n)
120 apio = 1
130 afin = m
140 bpio = m+1
150 bfin = n
160 for i = 1 to m
170 r$(i) = "1"
180 next i
190 for i = m+1 to n
200 r$(i) = "0"
210 next i
220 while afin > apio and bfin > bpio
230 apos = apio
240 bpos = bpio
250 while apos <= afin and bpos <= bfin
260 r$(apos) = r$(apos)+r$(bpos)
270 apos = apos+1
280 bpos = bpos+1
290 wend
300 if bpos < bfin then
310 bpio = bpos
320 else
330 bpio = apos
340 bfin = afin
350 afin = apos-1
360 endif
370 wend
380 result$ = ""
390 for i = apio to afin
400 result$ = result$+r$(i)
410 next i
420 for i = bpio to bfin
430 result$ = result$+r$(i)
440 next i
450 print result$
460 end sub
470 euclideanrhythm(5,13)
480 euclideanrhythm(3,8)
490 end
Same as FreeBASIC entry.
FreeBASIC
Sub EuclideanRhythm (m As Integer, n As Integer)
'Devuelve la cadena de ritmo euclidiano generada por m y n
'0 < m < n debe ser verdadero
Dim As String r(n)
Dim As Integer a_pio = 1, a_fin = m
Dim As Integer b_pio = m + 1, b_fin = n
Dim As Integer a_pos, b_pos
Dim As Integer i
'La cadena rítmica r() tiene n elementos, inicialmente los primeros m
'se establecen en "1" y el resto en "0". La primera parte se define por
'a_inicio y a_final y la segunda parte por b_inicio y b_final
For i = 1 To m
r(i) = "1"
Next i
For i = m + 1 To n
r(i) = "0"
Next i
'Los elementos b se añaden a los elementos a y se eliminan
'hasta que a o b o ambos tienen menos de dos elementos
While a_fin > a_pio And _ 'al menos dos elementos en a
b_fin > b_pio 'al menos dos elementos en b
a_pos = a_pio
b_pos = b_pio
While a_pos <= a_fin And b_pos <= b_fin
r(a_pos) += r(b_pos)
a_pos += 1
b_pos += 1
Wend
If b_pos < b_fin Then '2 o más elementos no utilizados quedan en b
b_pio = b_pos
Else 'no queda nada en b - usa los restos de a
b_pio = a_pos
b_fin = a_fin
a_fin = a_pos - 1
End If
Wend
Dim As String result = ""
For i = a_pio To a_fin
result += r(i)
Next i
For i = b_pio To b_fin
result += r(i)
Next i
Print result
End Sub
EuclideanRhythm(5, 13) 'caso de prueba de la tarea
EuclideanRhythm(3, 8) 'caso de prueba de JavaScript
Sleep
- Output:
Same as ALGOL 68 entry.
Gambas
Sub EuclideanRhythm(m As Integer, n As Integer)
Dim r As New String[]
Dim a_pio As Integer = 1, a_fin As Integer = m
Dim b_pio As Integer = m + 1, b_fin As Integer = n
Dim a_pos As Integer, b_pos As Integer, i As Integer
For i = 0 To m
r.Add("1")
Next
For i = m + 1 To n
r.Add("0")
Next
While a_fin > a_pio And b_fin > b_pio
a_pos = a_pio
b_pos = b_pio
While a_pos <= a_fin And b_pos <= b_fin
r[a_pos] &= r[b_pos]
a_pos += 1
b_pos += 1
Wend
If b_pos < b_fin Then
b_pio = b_pos
Else
b_pio = a_pos
b_fin = a_fin
a_fin = a_pos - 1
End If
Wend
Dim result As String = ""
For i = a_pio To a_fin
result &= r[i]
Next
For i = b_pio To b_fin
result &= r[i]
Next
Print result
End Sub
Public Sub Main()
EuclideanRhythm(5, 13) 'caso de prueba de la tarea
EuclideanRhythm(3, 8) 'caso de prueba de JavaScript
End
- Output:
Same as FreeBASIC entry.
PureBasic
Procedure EuclideanRhythm(m, n)
Dim r.s(n)
Protected.i a_pio = 1, a_fin = m
Protected.i b_pio = m + 1, b_fin = n
Protected.i a_pos, b_pos, i
For i = 1 To m
r(i) = "1"
Next
For i = m + 1 To n
r(i) = "0"
Next
While a_fin > a_pio And b_fin > b_pio
a_pos = a_pio
b_pos = b_pio
While a_pos <= a_fin And b_pos <= b_fin
r(a_pos) + r(b_pos)
a_pos + 1
b_pos + 1
Wend
If b_pos < b_fin
b_pio = b_pos
Else
b_pio = a_pos
b_fin = a_fin
a_fin = a_pos - 1
EndIf
Wend
Protected.s result = ""
For i = a_pio To a_fin
result + r(i)
Next
For i = b_pio To b_fin
result + r(i)
Next
PrintN(result)
EndProcedure
OpenConsole()
EuclideanRhythm(5, 13)
EuclideanRhythm(3, 8)
Input()
CloseConsole()
- Output:
Same as FreeBASIC entry.
QBasic
SUB EuclideanRhythm (m, n)
DIM r$(n)
apio = 1
afin = m
bpio = m + 1
bfin = n
FOR i = 1 TO m
r$(i) = "1"
NEXT i
FOR i = m + 1 TO n
r$(i) = "0"
NEXT i
WHILE afin > apio AND bfin > bpio
apos = apio
bpos = bpio
WHILE apos <= afin AND bpos <= bfin
r$(apos) = r$(apos) + r$(bpos)
apos = apos + 1
bpos = bpos + 1
WEND
IF bpos < bfin THEN
bpio = bpos
ELSE
bpio = apos
bfin = afin
afin = apos - 1
END IF
WEND
result$ = ""
FOR i = apio TO afin
result$ = result$ + r$(i)
NEXT i
FOR i = bpio TO bfin
result$ = result$ + r$(i)
NEXT i
PRINT result$
END SUB
CALL EuclideanRhythm(5, 13)
CALL EuclideanRhythm(3, 8)
- Output:
Same as FreeBASIC entry.
True BASIC
SUB euclideanrhythm (m,n)
DIM r$(0)
MAT redim r$(n)
LET a_pio = 1
LET a_fin = m
LET b_pio = m+1
LET b_fin = n
FOR i = 1 to m
LET r$(i) = "1"
NEXT i
FOR i = m+1 to n
LET r$(i) = "0"
NEXT i
DO while a_fin > a_pio and b_fin > b_pio
LET a_pos = a_pio
LET b_pos = b_pio
DO while a_pos <= a_fin and b_pos <= b_fin
LET r$(a_pos) = r$(a_pos) & r$(b_pos)
LET a_pos = a_pos+1
LET b_pos = b_pos+1
LOOP
IF b_pos < b_fin then
LET b_pio = b_pos
ELSE
LET b_pio = a_pos
LET b_fin = a_fin
LET a_fin = a_pos-1
END IF
LOOP
LET result$ = ""
FOR i = a_pio to a_fin
LET result$ = result$ & r$(i)
NEXT i
FOR i = b_pio to b_fin
LET result$ = result$ & r$(i)
NEXT i
PRINT result$
END SUB
CALL euclideanrhythm(5, 13)
CALL euclideanrhythm(3, 8)
END
- Output:
Same as FreeBASIC entry.
Yabasic
euclideanrhythm(5, 13)
euclideanrhythm(3, 8)
end
sub euclideanrhythm (m,n)
dim r$(n)
apio = 1
afin = m
bpio = m+1
bfin = n
for i = 1 to m
r$(i) = "1"
next i
for i = m+1 to n
r$(i) = "0"
next i
while afin > apio and bfin > bpio
apos = apio
bpos = bpio
while apos <= afin and bpos <= bfin
r$(apos) = r$(apos) + r$(bpos)
apos = apos+1
bpos = bpos+1
wend
if bpos < bfin then
bpio = bpos
else
bpio = apos
bfin = afin
afin = apos-1
fi
wend
result$ = ""
for i = apio to afin
result$ = result$ + r$(i)
next i
for i = bpio to bfin
result$ = result$ + r$(i)
next i
print result$
end sub
- Output:
Same as FreeBASIC entry.
C++
But the vector r
is subscripted from 0
to n - 1
.
// Euclidean rhythm
#include <iostream>
#include <string>
#include <vector>
using namespace std;
string euclidean_rhythm(const unsigned int m, const unsigned int n)
{
vector<string> r(n);
unsigned int a_start = 0, a_end = m - 1, b_start = m, b_end = n - 1;
for (unsigned int i = 0; i < m; i++)
r[i] = "1";
for (unsigned int i = m; i < n; i++)
r[i] = "0";
while (a_end > a_start && b_end > b_start)
{
unsigned int a_pos = a_start, b_pos = b_start;
while (a_pos <= a_end && b_pos <= b_end)
{
r[a_pos] += r[b_pos];
a_pos++;
b_pos++;
}
if (b_pos <= b_end)
b_start = b_pos;
else
{
b_start = a_pos;
b_end = a_end;
a_end = a_pos - 1;
}
}
string result = "";
for (unsigned int i = a_start; i <= a_end; i++)
result += r[i];
for (unsigned int i = b_start; i <= b_end; i++)
result += r[i];
return result;
}
int main()
{
cout << euclidean_rhythm(5, 13) << "\n";
cout << euclidean_rhythm(3, 8) << "\n";
}
- Output:
1001010010100 10010010
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
M2000 Interpreter
module Euclidean_Rhythm {
module Rhythm (a, b) {
'if b<a+1 then b=a+1
data "Rhythm for "+a+", "+b
function fillgroup(n, v) {
dim a(n) as string=str$(v, "")
=a()
}
g1=fillgroup(a, 1)
g2=fillgroup(b-a, 0)
while len(g2)>1
displayGroups()
onemore()
end while
displayGroups()
data g1#str$("")+g2#str$("")
sub onemore()
local k=each(g1), m=each(g2)
stack new {
while k, m
data array$(k)+array$(m)
end while
if len(g1)<len(g2) then
g2=g2#slice(len(g1))
g1=array([])
else.if len(g1)>len(g2) then
g2=g1#slice(len(g2))
g1=array([])
else
g1=array([])
g2=(,)
end if
}
end sub
sub displayGroups()
data g1#str$()+" | "+g2#str$()
end sub
}
flush
Rhythm 5, 13
Rhythm 3, 8
Rhythm 4, 5
string s
document d$
while not empty
read s
d$=s+{
}
print s
end while
clipboard d$
}
Euclidean_Rhythm
- Output:
Rhythm for 5, 13 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 10010 10010 | 100 1001010010100 Rhythm for 3, 8 1 1 1 | 0 0 0 0 0 10 10 10 | 0 0 100 100 | 10 10010010 Rhythm for 4, 5 1 1 1 1 | 0 11110
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
Nim
import std/[sequtils, strutils, sugar]
type Bit = 0..1
proc e(k, n: Natural): seq[Bit] =
var d = n - k
var s = repeat(@[Bit 1], k) & repeat(@[Bit 0], d)
var n = max(k, d)
var k = min(k, d)
var z = d
while z > 0 or k > 1:
for i in 0..<k:
s[i].add s[s.high - i]
s.setLen(s.len - k)
z -= k
d = n - k
n = max(k, d)
k = min(k, d)
result = collect:
for subList in s:
for item in subList:
item
echo e(5,13).join()
- Output:
1001010010100
PascalABC.NET
##
function E(k, n: integer): string;
begin
var s := (1..n).Select(i -> (if i <= k then |'1'| else |'0'|)).ToArray;
var d := n - k;
n := Max(k, d);
k := Min(k, d);
var z := d;
while (z > 0) or (k > 1) do
begin
for var i := 0 to k - 1 do
s[i] := s[i] + s[s.Length - i - 1];
s := s[0:s.Length - k];
z := z - k;
d := n - k;
n := Max(k, d);
k := Min(k, d);
end;
result := s.SelectMany(x -> x).JoinToString;
end;
E(5, 13).Println;
E(3, 8).Println;
- Output:
1001010010100 10010010
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
Quackery
Uses an alternative algorithm described in the YouTube video How to Calculate Euclidean Rhythms by Hand. This gives results which are equivalent under rotation to those given by the algorithm described by Toussaint. (As the paper notes, "since the sequence is cyclic it does not matter".)
[ dup temp put
[] swap 1+ times
[ i^ 1 - join ]
[] unrot
witheach
[ over *
temp share mod
rot join swap ]
drop
temp release
[] swap
behead swap
witheach
[ tuck <
rot join swap ]
drop ] is rhythm ( n n --> [ )
3 8 rhythm echo cr
5 13 rhythm echo cr
- Output:
[ 1 0 0 1 0 0 1 0 ] [ 1 0 0 1 0 0 1 0 1 0 0 1 0 ]
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.splice(*-1) }
($z, $d) = ($z, $n) X- $k;
($k, $n) = ($d, $k).minmax.bounds;
}
return [~] @s>>.List.flat;
}(5, 13);
You may Attempt This Online!
RPL
« DUP2 SWAP - DUP
« j » 'j' 1 6 ROLL 1 SEQ 4 PICK ≤ 1 « →STR » DOLIST
→ z s
« 1 CF
DO MAX LASTARG MIN
IF z 0 > OVER 1 > OR THEN
1 OVER FOR j
s j GET
s DUP SIZE j - 1 + GET
+ 's' j ROT PUT
NEXT
s 1 OVER SIZE 4 PICK SUB 's' STO
'z' OVER STO-
SWAP OVER -
ELSE 1 SF END
UNTIL 1 FS? END
DROP2 s ∑LIST
» 'EUCLRYTHM' STO
5 13 EUCLRYTHM
- Output:
1: "1001001010100"
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
Sidef
func e(k, n) {
var s = (^n -> map { |i| i < k ? [1] : [0] })
var d = (n - k)
n = max(k, d)
k = min(k, d)
var z = d
while ((z > 0) || (k > 1)) {
k.times { |i|
s[i] += s[-1 - i]
}
s = s.first(-k)
z -= k
d = (n - k)
n = max(k, d)
k = min(k, d)
}
s.flat.join
}
say e(5, 13)
- 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.
- Programming Tasks
- Solutions by Programming Task
- ALGOL 68
- Asymptote
- BASIC
- BASIC256
- Chipmunk Basic
- FreeBASIC
- Gambas
- PureBasic
- QBasic
- True BASIC
- Yabasic
- C++
- C sharp
- Dart
- EasyLang
- Go
- Java
- Jq
- JavaScript
- Julia
- Kotlin
- Lua
- M2000 Interpreter
- Mathematica
- Wolfram Language
- MATLAB
- Nim
- PascalABC.NET
- Perl
- Phix
- PHP
- Python
- Quackery
- R
- Raku
- RPL
- Ruby
- Rust
- Scala
- Sidef
- Swift
- Wren
- Wren-seq
- Zig