37 lines
1.0 KiB
Factor
37 lines
1.0 KiB
Factor
! Copyright (c) 2012 Anonymous
|
||
! See http://factorcode.org/license.txt for BSD license.
|
||
USING: kernel math math.statistics math.vectors sequences ;
|
||
IN: rosetta-code.equilibrium-index
|
||
|
||
! http://rosettacode.org/wiki/Equilibrium_index
|
||
|
||
! An equilibrium index of a sequence is an index into the
|
||
! sequence such that the sum of elements at lower indices is
|
||
! equal to the sum of elements at higher indices. For example,
|
||
! in a sequence A:
|
||
! A0 = − 7
|
||
! A1 = 1
|
||
! A2 = 5
|
||
! A3 = 2
|
||
! A4 = − 4
|
||
! A5 = 3
|
||
! A6 = 0
|
||
|
||
! 3 is an equilibrium index, because:
|
||
! A0 + A1 + A2 = A4 + A5 + A6
|
||
|
||
! 6 is also an equilibrium index, because:
|
||
! A0 + A1 + A2 + A3 + A4 + A5 = 0
|
||
! (sum of zero elements is zero)
|
||
|
||
! 7 is not an equilibrium index, because it is not a valid index
|
||
! of sequence A.
|
||
|
||
! Write a function that, given a sequence, returns its
|
||
! equilibrium indices (if any). Assume that the sequence may be
|
||
! very long.
|
||
|
||
: equilibrium-indices ( seq -- indices )
|
||
[ cum-sum0 ] [ <reversed> cum-sum0 <reversed> ] bi
|
||
v= t swap indices ;
|