How to implement a recursive version of this program?-CodePudding

I'd like some help, perhaps some pointers to how to think about the solution to the following recursively.

The program is supposed to take a sentence and print all different ways we could emphasize the words in this sentence.

Something like this:

Input: 

what are you doing

Output:
 
what are you doing?
what are you DOING?
what are YOU doing?
what are YOU DOING?
what ARE you doing?
what ARE you DOING?
what ARE YOU doing?
what ARE YOU DOING?
WHAT are you doing?
WHAT are you DOING?
WHAT are YOU doing?
WHAT are YOU DOING?
WHAT ARE you doing?
WHAT ARE you DOING?
WHAT ARE YOU doing?
WHAT ARE YOU DOING?

My iterative implementation:

from itertools import chain, combinations


inputStr = "what are you doing"
wordList = inputStr.split()


# getting all possible subsets which are all possible word combinations from inputStr
def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
   
    a = chain.from_iterable(combinations(iterable, r) for r in range(len(iterable) 1))
    return a

# list of tuples of subsets
temp = list(powerset(wordList))

# function that converts tuple to string
def join_tuple_string(strings_tuple) -> str:
   return ' '.join(strings_tuple)

# joining all the tuples into strings
result = map(join_tuple_string, temp)
listOfListsOfSubsets = list(result)

#  getting list of lists of words that form all possible subsets of inputStr and converting them to uppercase
for i in range(0,len(listOfListsOfSubsets)):
    listOfListsOfSubsets[i] = listOfListsOfSubsets[i].split()
# print(listOfListsOfSubsets)

# converting every word in in every possible subset of words from inputStr into upper-case
for i in range(0, len(listOfListsOfSubsets)):
    listOfListsOfSubsets[i] = [x.upper() for x in listOfListsOfSubsets[i]]



# reconstructing each subset of words to the full sentence (matching inputStr) while being case sensitive so that what was converted
# previously to uppper case, stays upper-case
for li in listOfListsOfSubsets:
    for word in wordList:
        if word.upper() not in li:
            i = wordList.index(word)
            li.insert(i, word)
    
    # printing all possible allEmphasesOf inputStr
    print(" ".join(li))

CodePudding user response：

Whenever I need to solve a problem recursively, I think of two main questions:

Given an input, how can I solve the problem by finding the solution to a simpler version of the same problem?
What is the simplest possible version of this problem?

Specifically with your problem, I would start by taking a look at the range of possible outputs. Notice that the first and last half of the inputs are mostly the same, except for the first word:

[what/WHAT] are you doing?
[what/WHAT] are you DOING?
[what/WHAT] are YOU doing?
[what/WHAT] are YOU DOING?
[what/WHAT] ARE you doing?
[what/WHAT] ARE you DOING?
[what/WHAT] ARE YOU doing?
[what/WHAT] ARE YOU DOING?

So if we could find a way to produce a list of all possible variations of the last 3 words, then we could simply make two copies of that list, and prepend what to every element of the first list, and WHAT to every element of the second list.

So how can we solve that subproblem? Notice that the outputs are duplicated again:

[are/ARE] you doing?
[are/ARE] you DOING?
[are/ARE] YOU doing?
[are/ARE] YOU DOING?

...and so on.

As for the simplest possible version of the program, that would be when there are zero or one words. The output is obvious there.

Putting this all together:

We need to write a function which produces a list of all possible variations of capitalisation
In the simple case, where there are zero or one words, you can hard-code the solution
In all other cases, we call our function on all but the first word, then make two copies, and add the two different capitalisations on to each.

Does that help you think about the problem?

CodePudding user response：

The base case is, if there is only one word, return it as it is, and add a capitalized version as well.
Else, generate all options for the remaining words. For each option, add either the word or the capitalized word in the beginning.

def dfs(words):
    if not words:
        return []
    if len(words)==1:
        return [[words[0]], [words[0].capitalize()]]
    else:
        ans = []
        options = dfs(words[1:])
        for option in options:
            ans.append([words[0]]   option)
            ans.append([words[0].capitalize()]   option)
        return ans

s = "what are you doing"
print(dfs(s.split()))

CodePudding user response：

So, another way to express this problem is: find the power set of the given set.

I see that you have already written a function for that (I copied from your question). And I guess you got this code from the itertools recipe page.

# getting all possible subsets which are all possible word combinations from inputStr
def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
   
    a = chain.from_iterable(combinations(iterable, r) for r in range(len(iterable) 1))
    return a

What we need to do now is to re-write this function using recursion. For that, here is my approach:

def get_powerset(lst):
    if not lst:
        return [[]]
    with_first = [[lst[0]]   rest for rest in get_powerset(lst[1:])]
    without_first = get_powerset(lst[1:])
    return with_first   without_first


input_string = 'what are you doing'
input_length = len(input_string.split(' '))

powerset = get_powerset(range(input_length))
print(powerset)

After running the function, you get a list of all subsets. Simply loop through them and capitalize the word at the corresponding index.

CodePudding user response：

My observation was that if you count the number of combinations and represent each one as a binary number, then that binary number expressed as a string can be used to indicate which words should be uppercase words:

def to_upper(sentence, i = 0):
    upper = f"{i:0{len(sentence)}b}"
    to_print = []
    for s in range(len(sentence)):
        if upper[s] == '1': to_print.append(sentence[s].upper())
        else: to_print.append(sentence[s])
    print(' '.join(to_print))
    if i < 2**len(sentence)-1:
        to_upper(sentence, i = i   1)

to_upper('what are you doing'.split(''))

CodePudding user response：

I see you've found module itertools. It offers a lot of useful functions to combine possibilities.

Here you have two possibilities for each word: the capitalized and the uncapitalized versions. You can combine all the possibilities with itertools.product.

from itertools import product

def all_emphases(s):
    for c in product(*((w, w.upper()) for w in s.split())):
        yield ' '.join(c)

for c in all_emphases('what are you doing?'):
    print(c)

Output:

what are you doing?
what are you DOING?
what are YOU doing?
what are YOU DOING?
what ARE you doing?
what ARE you DOING?
what ARE YOU doing?
what ARE YOU DOING?
WHAT are you doing?
WHAT are you DOING?
WHAT are YOU doing?
WHAT are YOU DOING?
WHAT ARE you doing?
WHAT ARE you DOING?
WHAT ARE YOU doing?
WHAT ARE YOU DOING?