Count number of alternations in a coin flip sequence
-
01-10-2019 - |
문제
I have a sequence of ones and zeros and I would like to count the number of alternations. e.g.
x <- rbinom(10, 1, 1/2)
> x
[1] 0 0 1 1 1 1 1 0 1 0
Thus 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 (counted by hand) is 4.
해결책
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
다른 팁
The rle function will count the number of 'runs' of the same value in a vector. Hence the length of this vector (minus 1) gives you the number of alterations:
> 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
Might be quicker or slower than the diff() method, but it also gives you the run lengths if you need them...
It definitely doesn't beat diff in terms of elegance but another way:
sum(x[-1] != head(x, n=-1))
On my system, this seems to be a teeny bit 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
It seems like there ought to be a nice analytic solution for the distribution of the number of unequal adjacent elements in the sequence.
Pseudocode (sequence is an array with your coin flips):
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