Number of unique permutations in the K-path Viterbi algorithm ------------------------------------------------------------- See NOTES/combos for background information about the number of states in the K-path Viterbi algorithm with missed target events. When missed target events are considered, the measurement index MM+1 which represents those events can occur more than once in the combinations. For example: m:1112> MISSED=1; MM=4; K=3; setup_combos m:1113> combos combos = 1 2 3 1 2 4 1 3 4 2 3 4 1 2 5 1 3 5 1 4 5 2 3 5 2 4 5 3 4 5 1 5 5 2 5 5 3 5 5 4 5 5 5 5 5 m:1114> sizeof(combos) ans = 15 3 m:1115> perms perms = 1 2 3 1 3 2 2 3 1 2 1 3 3 1 2 3 2 1 m:1116> sizeof(perms) ans = 6 3 Each row of the permutation array (perms) specifies a way of selecting the elements of a row of the combination array (combos) in a specific permutation. The size of the permutation array is K! by K. For example, taking the 4th row of combos and listing all of the possible permutations: m> c=combos(4) m> c(perms) ans = 2 3 4 2 4 3 3 4 2 3 2 4 4 2 3 4 3 2 m> But for rows which include more than one missed target event, not all of the possible permutations are unique. For example, the last row of combos above, which is all 5's, has only one unique permutation of the elements. To simplify access to the unique permutations during operation of the K-path Viterbi algorithm, a unique_perms array is precomputed. For the example above it is: m:1117> unique_perms unique_perms = 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 1 3 4 0 0 0 1 3 4 0 0 0 1 3 4 0 0 0 1 3 4 0 0 0 1 0 0 0 0 0 m:1118> sizeof(unique_perms) ans = 15 6 Each row of the unique_perms array corresponds to a row of the combos array and indicates which of the possible permutations (rows of the perms array) are unique. The 0 elements in the unique_perms array are just placeholders and are not used. So, for example, row 14 of unique_perms indicates that permutations 1, 3, and 4 are unique for row 14 of the combos array. The number of rows and columns of the unique_perms array are: rows(unique_perms) == rows(combos), cols(unique_perms) == rows(perms) == K! In each iteration of the K-path Viterbi algorithm, the number of costs which must be computed is equal to the number of non-zero elements in the unique_perms array. If missed target events were not being considered, there would be no zero elements in the unique_perms array and the number of costs would be rows(combos)*rows(perms), where rows(perms) = K! When missed target events are considered, this increases the total number of states, but the unique_perms array will contain some zero elements so the total number of costs to compute will be less than rows(combos)*rows(perms). Checking for the example above: m:1119> rows(combos)*rows(perms) ans = 90 m:1120> sum(unique_perms(:)!=0) ans = 73 An expression for the number of costs can easily be stated: NP = C(MM,K)*K! + C(MM,K-1)*K! + C(MM,K-2)*K!/2! + ... + C(MM,1)*K!/(K-1)! + 1 = K! * sum i=0..K { C(MM,i)/(K-i)! } We would like to have a closed-form equation for NP. Checking this formula for the example above, with MM=4, K=3: NP = C(4,3)*6 + C(4,2)*6 + C(4,1)*6/2 + 1 = 4*6 + 6*6 + 4*3 + 1 = 73 Another example: m:1121> MM=5; K=4; setup_combos m:1122> combos combos = 1 2 3 4 1 2 3 5 1 2 4 5 1 3 4 5 2 3 4 5 1 2 3 6 1 2 4 6 1 2 5 6 1 3 4 6 1 3 5 6 1 4 5 6 2 3 4 6 2 3 5 6 2 4 5 6 3 4 5 6 1 2 6 6 1 3 6 6 1 4 6 6 1 5 6 6 2 3 6 6 2 4 6 6 2 5 6 6 3 4 6 6 3 5 6 6 4 5 6 6 1 6 6 6 2 6 6 6 3 6 6 6 4 6 6 6 5 6 6 6 6 6 6 6 m:1123> sizeof(combos) ans = 31 4 m:1124> perms perms = 1 2 3 4 1 2 4 3 1 3 4 2 1 3 2 4 1 4 2 3 1 4 3 2 2 3 4 1 2 3 1 4 2 4 1 3 2 4 3 1 2 1 3 4 2 1 4 3 3 4 1 2 3 4 2 1 3 1 2 4 3 1 4 2 3 2 4 1 3 2 1 4 4 1 2 3 4 1 3 2 4 2 3 1 4 2 1 3 4 3 1 2 4 3 2 1 m:1125> sizeof(perms) ans = 24 4 m:1126> sizeof(unique_perms) ans = 31 24 m:1127> rows(combos)*rows(perms) ans = 744 m:1128> sum(unique_perms(:)!=0) ans = 501 Checking: NP = C(5,4)*24 + C(5,3)*24 + C(5,2)*24/2 + C(5,1)*24/6 + 1 = 5*24 + 10*24 + 10*12 + 5*4 + 1 = 501