#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2013
    Posts
    6
    Rep Power
    0

    Sub word combinations


    Accept any number of lines of input entered from standard input. A valid line contains a word and a number. The word comes first, and is up to twenty alphabetic characters (A-Z) in upper or lower case. The word may be preceeded and followed by any number of blanks. The number is a decimal integer greater than zero, and may be followed by any number of blanks or a return. Input is terminated by EOF character. For each input word, print all possible "subwords" that have as many characters as specified by the number. A "subword" is a n-letter word comprised of only characters that are found in the given word. If you are familiar with the game Scrabble, it's as though the input word is your pool of letters, and you want to find all possible arrangements of n letters from your pool. .nf For example, CAT 2 would produce CA CT AC AT TA TC and DOG 1 would produce D O G and BIRD 3 would produce BIR BID IRD RID DIR RIB ... Note, that we are producing combinations WITHOUT replacement, so in the BIRD 3 example, BBB and RRR are NOT possible subwords. The output should echo the input line to standard output, followed by the list of subwords, one word per line, left justified. Each set of output words should be followed by one blank line. The program should respond to invalid input by echoing the input line to the output, and then issuing a one line message indicating the nature of the error:

    "Illegal character in word"
    "Illegal character in number"

    "Number greater than length of word"

    "Word longer than 20 characters"

    After issuing the message, processing should resume with the next input line. When all input has been processed, issue a message indicating the number of input words that were processed (including word with errors) e.g., "End of input encountered, 4 words processed."
  2. #2
  3. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,901
    Rep Power
    481
    You need all permutations of all combinations of length k from a set of n items, k <= n.

    The "cat" example indicates a recursive solution. Furthermore, the input length restriction to 20 characters limits the recursion depth. All-in-all the project suggests to me a solution such as
    Code:
    main procedure:
        get and process input
        call Homework_XIII(set, k_items, current_solution)
        wrap it up.
        
    
    procedure Homework_XIII(set, k, current_solution):
        if k is less than one:
            show current_solution
            return
        else:
            for item in set:
                append item to current_solution
                remove item from set
                call Homework_XIII(set, k-1, current_solution)
                restore item to set
                remove item from current_solution
    (oh! Sets are unordered. While a computer implementation would probably work, this is mathematically wrong. Where I said "set" you need a "list".)
    Last edited by b49P23TIvg; November 21st, 2013 at 10:48 AM. Reason: improve consistency of k's and n's. (later still I inserted the set note)
    [code]Code tags[/code] are essential for python code and Makefiles!

IMN logo majestic logo threadwatch logo seochat tools logo