Euclidean rhythm

From Rosetta Code
Task
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

Translation of: FreeBASIC
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

Translation of: FreeBASIC
Works with: Chipmunk Basic version 3.6.4
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

Translation of: ALGOL 68
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

Translation of: FreeBASIC
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

Translation of: FreeBASIC
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

Translation of: FreeBASIC
Works with: QBasic version 1.1
Works with: QuickBasic version 4.5
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

Translation of: FreeBASIC
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

Translation of: FreeBASIC
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++

Translation of: ALGOL 68

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#

Translation of: Java
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

Translation of: Python
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

Translation of: JavaScript
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

Translation of: Java
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

Translation of: Python
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: jq

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

Translation of: R
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

Translation of: Swift
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

Translation of: Python
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

Translation of: Julia
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

Translation of: Julia
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

Translation of: Python
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

Translation of: Python
<?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

Translation of: JavaScript
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

Translation of: Python
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

Translation of: Perl
# 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

Translation of: Julia
« 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

Translation of: Python
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

Translation of: Python
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

Translation of: Java
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

Translation of: Ruby
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

Translation of: Java
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

Translation of: Python
Library: Wren-seq
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

Translation of: Python
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
  1. ↑ 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.
Retrieved from "https://rosettacode.org/wiki/Euclidean_rhythm?oldid=363708"