Creating Even Distributed Sequences

Projects General Guidance
1

Hi, I have recently approached a problem I had on cue for a long time, an Euclid divider.

What does an Euclid Sequence Generator does?

An Euclid Sequence Generator is an algorithm that distributes as even as possible 2 numbers in a sequence. So lets say that for example you want a sequence with a length of 12 with 5 pulses distributed as even as possible. So the approach would be as follows:

We need to know how many steps are off, so: (lenght - pulses) 12 - 5 = 7
Start with the following numbers:

7 - 0: 0 0 0 0 0 0 0
5 - 1: 1 1 1 1 1

having now 5 sequences of "01" and 2 sequences of "0" to distribute, so we are going to do the same but we are calling "01" -> a, and "0" -> b. We are going to iterate until max - min <= 1.

a = 01; b = 0;

5 - a: a a a a a
2 - b: b b

doing another iteration:

x = ab; y = a;

3 - y: y y y
2 - x: x x

p = yx
q = y

In here max - min is 1 so in this iteration we can create our sequence:

p-p-q

(yx)-(yx)-(y)

([a][a.b])-([a][a.b])-([a])

([01][01.0])-([01][01.0])-([01])

the sequence would be 010100101001 being a sequence o 12 y 5 pulses evenly distributed.

Take in mind that this pseudo algorithm is only to explain functionality, there are several things to do to do this more efficiently.

you can skip steps as with a Greatest common divisor algorithm ( by swapping "max - min" to "max % min"):

for example:

str_a = 1;
str_b = 0;

a = 5;
b = 2;

x = a/b = 2;
y = a%b = 1;

str1 = str_b + (str_a * x) = 011

output = (str1 * b) + str_a = 011 011 0

Now my next step is taking this to the next level by trying to distrubute more numbers in a sequence.

Lets say that you want a sequence with a length of 12, and have 5 a's , 4 b's and 3 c's distributed as evenly as possible, how would you people approach this problem?? I am interested in your opinion :slight_smile:

2

cheche_romo:
So the approach would be as follows:

We need to know how many steps are off, so: (length - pulses) 12 - 5 = 7
Start with the following numbers:

7 - 0: 0 0 0 0 0 0 0
5 - 1: 1 1 1 1 1

I can understand what you mean by length '12', but what do you mean by '5' pulses?

And when you say 'start with the following numbers'...... you chose arbitrarily two numbers, which are '7' and '5', right?

And what does this following code imply? "7 - 0: 0 0 0 0 0 0 0 "
Does '7 - 0' mean a sequence of seven zeros? ie. 0 0 0 0 0 0 0

..... and what does this mean? "having now 5 sequences of "01" and 2 sequences of "0" to distribute"?
As far as I can see, I can see 1 sequence containing 5 lots of '1', and I can see 1 sequence containing 7 lots of '0. I do not see 2 sequences of '0', and I do not see 5 sequences of '01'.

3

Southpark:
I can understand what you mean by length '12', but what do you mean by '5' pulses?

And when you say 'start with the following numbers'...... you chose arbitrarily two numbers, which are '7' and '5', right?

And what does this following code imply? "7 - 0: 0 0 0 0 0 0 0 "
Does '7 - 0' mean a sequence of seven zeros? ie. 0 0 0 0 0 0 0

..... and what does this mean? "having now 5 sequences of "01" and 2 sequences of "0" to distribute"?
As far as I can see, I can see 1 sequence containing 5 lots of '1', and I can see 1 sequence containing 7 lots of '0. I do not see 2 sequences of '0', and I do not see 5 sequences of '01'.

Sorry for the lack of explanation

a sequence of length 12, with 5 pulses (1) and 7 rests (0), and yes 7 - 0 means a sequence of 7 zeros, and 5 - 1 a sequence of 5 ones .

if you align those sequences vetically, you get:

0 0 0 0 0 0 0
1 1 1 1 1

in this arrangement we can visually see that there are 5 sequences of 01 and 2 sequences of 0 (Vertically).

It is a recursive algorithm, so the iterations would be as explained above.

I changed the variable names each iteration so it is easy to follow the creation of the sequence:
ie.

a = 01; b = 0;

x = ab; y = a;

p = yx; q = y;

given the sequence "p-p-q" replace the letters:

p-p-q

(yx)-(yx)-(y)

([a][a.b])-([a][a.b])-([a])

([01][01.0])-([01][01.0])-([01])

"()", "[]", and "." are used to show graphically the iterations variables

4

Thanks for explaining that. I see exactly what you mean now. Yep.... this technique you showed could certainly be indexed --- maybe 2 dimensional indexing ....so the first level variables like 'a' and 'b' etc, could be x[00], x[01], etc. Second level variables could be x[10], x[11], x[12] etc. Third level x[20], x[21], x[22] etc.

5

Okay, first thanks for taking the time :slight_smile:

Let's try an example with 3 variables

length = 12;
a = 5; b = 3; c = 4;
str_a = 0; str_b = 1; str_c = 2;

(Vertical Arrangement ordered from bigger to smaller)

a a a a a
c c c c
b b b

x = abc; y = ac; z = a;

now we have the following groups: 3x 1y 1z

In here is the tricky part, now you have a reminder such as (y + z) < x. This means that you can create your sequence in this iteration, because (1 + 1) < 3.

How would you divide the secuence??

3x-1y-1z: x-y-x-z-x
3x-1y-1z: x-y-z-x-x

the second option in not as evenly as distributed, I'm stuck here.

Also it is not that clear what happens when the two lower numbers are the same.