;---------------------------------------------------------------------------- ; $Id: find_forbid.pro,v 1.5 2002/02/16 00:20:35 johnny Exp $ ;+ ; NAME: ; FIND_FORBID ; ; PURPOSE: ; Given an array of unique words (symbolic sequence of 0's and 1's) of ; length length_n, find which words are "forbidden". "Forbidden" words ; are those words that are "possible" but are not in the set of the input ; unique words. See "Notes" section below for a useful reference. ; ; CATEGORY: ; Statistics. ; ; CALLING SEQUENCE: ; Result = FIND_FORBID(in_words) ; ; INPUTS: ; in_words: Array of unique words, dimensioned (length_n, number of ; unique words). Each row or the array is assumed to be ; a unique word. Each element is either '0' or '1'. ; String array. ; ; KEYWORD PARAMETERS: ; COUNT: If set to a variable, the number of forbidden words in ; Result is returned. Scalar long. Created. ; ; VERBOSE: If keyword is set true, diagnostic messages are printed ; to stdout. ; ; OUTPUTS: ; Result: Array of forbidden words, dimensioned (length_n, number ; of forbidden words). Each row of the array is a ; forbidden word. String array. If no forbidden words ; are found, the scalar -1L is returned. ; ; FILE DEVICE I/O: ; None. ; ; COMMON BLOCKS: ; None. ; ; EXAMPLE: ; Create test list of unique words and run function: ; input = [ ['0','0','0'], ['0','1','1'], ['1','0','1'] ] ; result = FIND_FORBID(input) ; PRINT, result ; IDL prints: ; 0 0 1 ; 0 1 0 ; 1 0 0 ; 1 1 0 ; 1 1 1 ; ; MODIFICATION HISTORY: ; - 29 Jan 2002: Orig. ver. Johnny Lin, CIRES/University of Colorado. ; Email: air_jlin@yahoo.com. Passed reasonably adequate tests. ; - 30 Jan 2002: Add Count keyword and ability to handle no forbidden ; words situation. Also can handle 1-D vector input. Passed minimally ; passable tests. ; ; NOTES: ; - Written for IDL 5.4. May work with earlier versions (haven't tested ; yet). ; - Reference: Elsner, J. B. and A. A. Tsonis (1993), "Complexity and ; predictability of hourly precipitation," J. Atmos. Sci., Vol. 50, ; No. 3, pp. 400-405. ; - All keyword parameters are optional unless otherwise stated. ; - No procedures called with _Extra keyword invoked. ; - User-written procedures called: DEC2BIN (from the SolarSoft library). ;- ; Copyright (c) 2002 Johnny Lin. For licensing, distribution conditions, ; and contact information, see http://www.johnny-lin.com/lib.html. ;---------------------------------------------------------------------------- FUNCTION FIND_FORBID, in_words $ , COUNT = out_count $ , VERBOSE = verbose $ , _EXTRA = extra ; -------------------- Error Check and Parameter Setting -------------------- ON_ERROR, 0 words_found_ln = in_words ;- protect input length_n = (SIZE(words_found_ln, /Dimensions))[0] ;- length of a word if (SIZE(words_found_ln, /Type) ne 7) then $ ;- error check MESSAGE, 'error--bad input words type' if (length_n gt 30L) then $ MESSAGE, 'error--word length too big' if (SIZE(words_found_ln, /N_Dimensions) eq 1) then $ words_found_ln = REFORM(words_found_ln, length_n, 1) tmp = WHERE((words_found_ln ne '0') and (words_found_ln ne '1'), count) if (count ne 0) then $ MESSAGE, 'error--bad values in input words' ; -------------- Create All Possible Words of Length length_n --------------- ; ; Algorithm: There are 2^n possible words of word length n. Make an ; array of base 10 values from 0 to (2^n) and convert to binary to get ; an array of all possible words of length n. ; ; Selected variable key: ; NALL Number of all possible combination of length length_n. ; words_all_ln Array of all possible words of length length_n (this ; variable is the key output from this section). NALL = 2L^length_n ;- no. of possible combinations all_decimal = LINDGEN(NALL) ;- array of decimal numbers DEC2BIN, all_decimal, words_all_ln_byte $ ;- find all words of length , /Quiet ; length_n (output as byte arr.) dim_walb = SIZE(words_all_ln_byte, /Dimensions) ;- dim of words_all_ln_byte if (N_ELEMENTS(dim_walb) ne 2) then $ MESSAGE, 'error--bad walb array' words_all_ln = STRARR(dim_walb[0], dim_walb[1]) ;- change words_all_ln from pts = WHERE(words_all_ln_byte eq 0B, count) ; byte to string type if (count gt 0) then words_all_ln[pts] = '0' pts = WHERE(words_all_ln_byte eq 1B, count) if (count gt 0) then words_all_ln[pts] = '1' words_all_ln = words_all_ln[(dim_walb[0]-length_n):*, *] ;- trunc. lead. 0's ; -------------- Find All Forbidden Words of Length length_n ---------------- ; ; Algorithm: Go through each words in words_all_ln. If it matches with no ; word in words_found_ln (non-forbidden words) then it is a forbidden word. ; The while loop goes through all words in words_found_ln until either a ; match to the ith word in words_all_ln is found (at which point no_match ; is set to 0), or until all NOK words are gone through matchless. ; ; Selected variable key: ; NOK Number of non-forbidden words of length length_n. ; check_word Candidate comparison word from words_all_ln. ; compare_word Candidate comparison word from words_found_ln. ; words_found_ln Non-forbidden words of length length_n (read in ; as input parameter in_words). ; words_forbid_ln Forbidden words of length length_n (this is the ; key output variable from this section). NOK = (SIZE(words_found_ln, /Dimensions))[1] ;- num. of non-forbidden words for i=0L,NALL-1L do begin check_word = words_all_ln[*,i] ;+ candidate word no_match = 1 ;+ flag (true) if no match is made yet iwf = 0L ;+ initialize iwf and count count = 0L while ((no_match) and (iwf le NOK-1L)) do begin compare_word = words_found_ln[*,iwf] tmp = WHERE(check_word eq compare_word, count) iwf = iwf+1L if (count eq length_n) then no_match = 0 endwhile case no_match of 0: begin if (KEYWORD_SET(verbose) eq 1) then begin fmt = STRTRIM(STRING(N_ELEMENTS(check_word)),2) + 'a2)' fmt = '("FIND_FORBID: Match found for word: ",' + fmt PRINT, Format=fmt, check_word[*] endif end 1: if (N_ELEMENTS(words_forbid_ln) eq 0) then $ words_forbid_ln = REFORM(check_word, length_n,1) $ else $ words_forbid_ln = [ [words_forbid_ln], [check_word] ] else: MESSAGE, 'error--bad no_match value' endcase endfor ; ----------------------------- Prepare Output ------------------------------ if (N_ELEMENTS(words_forbid_ln) eq 0L) then begin out_count = 0 Result = -1L endif else begin out_count = (SIZE(words_forbid_ln, /Dimensions))[1] Result = TEMPORARY(words_forbid_ln) endelse RETURN, Result END ;=== end of function === ; ========== end file ==========