Rosetta Code

Euclidean rhythm

Revision as of 16:25, 10 February 2024 by Hkdtam (talk | contribs) (→‎{{header|Raku}}: Simplify)

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
Euclidean rhythm
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#

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!

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

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=360797"