How to choose items of an array by defining a skip of constant length

Questions
1

Hello,

I am using arrays of notes and I am wondering whether there is a simple way to choose the items of the array by skipping 1 note, 2 notes, 3 notes, etc. and to stop when the first item chosen repeats.

Let’s say I have this array:
[0,1,2,3,4,5,6,7,8,9,10,11];
and by skipping 0 items, 1 item, 2 items, 3 items, etc. I want to get these arrays:
skipping none: [0,1,2,3,4,5,6,7,8,9,10,11]
skipping one note: [0,2,4,6,8,10,0]
skipping two notes: [0,3,6,9,0]
skipping three notes: [0,4,8,0]
skipping four notes: [0,5,10,3,8,1,6,11,4,9,2,7,0] *
skipping 5 notes: [0,6,0]
skipping six notes: [0,7,2,9,4,11,6,1,8,3,10,5,0] *
skipping seven notes: [0,8,4,0] *
skipping eight notes: [0,9,6,3] *
skipping nine notes: [0,10,8,6,4,2,0] *
skipping ten notes: [0,11,10,9,8,7,6,5,4,3,2,1,0] *
skipping eleven notes: [0,0]
In the cases marked * , the initial array must be wrapped around to get all the values.

May be something so simple, but I just can’t figure it out. Thanks, JF

2

one way of solving that is this:

(
~f = { |array, stride|
	if(stride <= 0) {
		[]
	} {
		array.wrapAt((0, stride .. lcm(array.size, stride)))
	}
};
)

in your example results all your arrays end with 0 except for “skipping none”. was that a mistake? if it wasn’t you would have to add an additional case to the above function:

~f = { |array, stride|
	case
	{ stride <= 0 } { [] }
	{ stride == 1 } { array.copy }
	{
		// default case
		array.wrapAt((0, stride .. lcm(array.size, stride)))
	}
};
3

just to explain the above a bit:

(a, b .. c) // creates an array stepping by `b` from `a` to the greatest value a + b*n <= c for some n.
// for example: (1, 3 .. 10) => [1, 3, 5, 7, 9] ; (1, 4 .. 10) => [1, 4, 7, 10]

lcm(a, b) // least common multiple of a and b

a.wrapAt(b) // if b is an integer, equivalent to a[b % a.size]

a.wrapAt([b, c]) // equivalent to [a.wrapAt(b), a.wrapAt(c)]

knowing when to stop striding through the array is equivalent to asking when an mod b = 0 for some n > 0. this is when an = lcm(a, b).

4

Thanks so much VIRTUALDOG, this is a great solution, I am pretty much a beginner so your help is greatly welcome.
You are right, I made a mistake by re-writing the repeated 0 that closes the “loop” of the procedure.
Now through your example I have a couple of questions:
1 - How can I get the last 0 off the resulting array? so I do not have it repeated everytime (not only in the case observed in your answer?); and
2 - Is there a way to store in some other array the clipped off items from the original array?

I appreciate greatly your help, regards, JF

5

Hey again,
VIRTUALDOG, analyzing your code, I think I found a solution to my first question about not repeating the 0 at the end of each “striding cycle”, though I do not know whether that’s an elegant one:

(
~f = { |array, stride|
	if(stride <= 0) {
		[]
	} {
		array.wrapAt((0, stride .. lcm(array.size, stride)-1))  // I just added -1 to the wrapAt end
	}
};

Anyways, I believe then I just have one question left, and that would be if there is a way to retrieve the discarded elements as another array.
Thanks, JF

6

for your first question, that’s the same solution I would have given!

As for gathering the unused elements, there are a few ways you could approach it. here is what i would write:

(
// returns an array of 2 elements: [chosen items, discarded items]
~f = { |array, stride|
	if(stride <= 0) {
		[[], array.copy]
	} {
		var indices = (0, stride .. lcm(array.size, stride) - 1).wrap(0, array.size - 1);
		var included = array.at(indices);
		var excluded = array.reject { |item, i| indices.includesEqual(i) };
		[included, excluded]
	}
};
)

var excluded = array.reject { |item, i| indices.includesEqual(i) };

reject returns a copy of array with any element removed for which the given predicate – here, whether the index of the element is in the list of indices we are accepting – returns true.

this algorithm has complexity O(n^2), if you have a long list and needed this optimized, an O(n) solution would be:

(
~f = { |array, stride|
	if(stride <= 0) {
		[[], array.copy]
	} {
		var indices = (0, stride .. lcm(array.size, stride) - 1).wrap(0, array.size - 1);
		var flags = Array.fill(array.size, true);
		var included = array.at(indices);
		var excluded;
		indices.do { |i| flags[i] = false };
		excluded = array.select { |item, i| flags[i] };
		[included, excluded]
	}
};
)

for instance, the first solution on my machine takes about 8.2 seconds to run on the input ~f.((1 .. 10000), 4), whereas the latter only takes 0.02 seconds. for small arrays, the difference is negligible and may actually be in the first solution’s favor since it requires fewer allocations.

7

Hi,

It’s great to know you would have that same approach for the first question!
As for the second one… your solutions just work great, I’m still working on exploring what every single line on your code does. That’s a great way to learn, I just want to thank you so much for answering, this has been enlightening. Best Regards, JF

1 Like