Geek Answers Handbook

Count the number of alternations in a coin transfer sequence

I have a sequence of ones and zeros, and I would like to count the number of alternations. eg.

x <- rbinom(10, 1, 1/2) > x [1] 0 0 1 1 1 1 1 0 1 0

So I would like to count (in R) how many times the sequence alternates (or flips) from one to zero. In the above sequence, the number of alternations (calculated manually) is 4.

+4
source share
4 answers

You can use diff ():

 > x <- rbinom(10,1,1/2) > x [1] 0 0 0 1 1 1 1 0 1 0 > sum(diff(x)!=0) [1] 4
+12
source

The rle function will count the number of "runs" of the same value in the vector. Therefore, the length of this vector (minus 1) gives you the number of changes:

 > x [1] 0 0 0 1 1 1 1 0 1 0 > rle(x) Run Length Encoding lengths: int [1:5] 3 4 1 1 1 values : num [1:5] 0 1 0 1 0 > length(rle(x)$lengths)-1 [1] 4

It may be faster or slower than the diff () method, but it also gives you a run length if you need it ...

+6
source

This will definitely not surpass the difference in terms of elegance, but in a different way:

 sum(x[-1] != head(x, n=-1))

On my system, this seems faster:

 > x <- rbinom(1e6, 1, 0.5) > system.time(replicate(100, sum(x[-1] != head(x, n=-1)))) user system elapsed 8.421 3.688 12.150 > system.time(replicate(100, sum(diff(x) != 0))) user system elapsed 9.431 4.525 14.248

There seems to be a good analytical solution for distributing the number of unequal adjacent elements in a sequence.

+3
source

Pseudocode (a sequence is an array with your flags):

 variable count = 0 variable state = sequence[0] iterate i from sequence[1] to sequence[n] if (state not equal sequence[i]) state = 1 - state count++

count should be your result

0
source

More articles:


All Articles