如何实现这个程序的递归版本?
How to implement a recursive version of this program?
我需要一些帮助,也许是关于如何递归地考虑以下问题的解决方案的一些指示。
该程序应该接受一个句子并打印我们可以强调该句子中单词的所有不同方式。
像这样:
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?
我的迭代实现:
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))
基本情况是,如果只有一个单词,return原样,加上大写。
否则,为剩余的单词生成所有选项。对于每个选项,在开头添加单词或大写单词。
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()))
每当我需要递归解决一个问题时,我都会想到两个主要问题:
- 给定输入,我如何通过找到同一问题的更简单版本的解决方案来解决问题?
- 这个问题最简单的版本是什么?
具体针对您的问题,我将从查看可能输出的范围开始。请注意,输入的前半部分和后半部分大部分相同,除了第一个单词:
[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?
因此,如果我们能找到一种方法来生成最后 3 个单词的所有可能变体的列表,那么我们可以简单地制作该列表的两个副本,并将 what
添加到第一个单词的每个元素之前列表,和 WHAT
第二个列表的每个元素。
那么我们如何解决这个子问题呢?请注意,输出再次重复:
[are/ARE] you doing?
[are/ARE] you DOING?
[are/ARE] YOU doing?
[are/ARE] YOU DOING?
...等等。
至于程序的最简单版本,那就是只有零个或一个单词。那里的输出很明显。
综合起来:
- 我们需要编写一个函数来生成所有可能的大写变体列表
- 在简单的情况下,有零个或一个单词,您可以hard-code解决方案
- 在所有其他情况下,我们在 除了第一个单词 之外的所有单词上调用我们的函数,然后制作两个副本,并在每个单词上添加两个不同的大写字母。
我的观察是,如果你计算组合的数量并将每个组合表示为二进制数,那么表示为字符串的二进制数可以用来指示哪些单词应该是大写单词:
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(''))
所以,这个问题的另一种表达方式是:找到给定集合的幂集。
我看到你已经为此编写了一个函数(我从你的问题中复制过来)。我猜你是从 itertools 食谱页面得到的代码。
# 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
我们现在要做的是re-write这个函数使用递归。为此,这是我的方法:
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)
在 运行 函数之后,您将获得所有子集的列表。只需遍历它们并将相应索引处的单词大写即可。
我看到您找到了模块 itertools
。它提供了很多有用的功能来组合各种可能性。
此处每个单词有两种可能:大写和非大写版本。您可以将所有可能性与 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)
输出:
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?
我需要一些帮助,也许是关于如何递归地考虑以下问题的解决方案的一些指示。
该程序应该接受一个句子并打印我们可以强调该句子中单词的所有不同方式。
像这样:
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?
我的迭代实现:
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))
基本情况是,如果只有一个单词,return原样,加上大写。
否则,为剩余的单词生成所有选项。对于每个选项,在开头添加单词或大写单词。
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()))
每当我需要递归解决一个问题时,我都会想到两个主要问题:
- 给定输入,我如何通过找到同一问题的更简单版本的解决方案来解决问题?
- 这个问题最简单的版本是什么?
具体针对您的问题,我将从查看可能输出的范围开始。请注意,输入的前半部分和后半部分大部分相同,除了第一个单词:
[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?
因此,如果我们能找到一种方法来生成最后 3 个单词的所有可能变体的列表,那么我们可以简单地制作该列表的两个副本,并将 what
添加到第一个单词的每个元素之前列表,和 WHAT
第二个列表的每个元素。
那么我们如何解决这个子问题呢?请注意,输出再次重复:
[are/ARE] you doing?
[are/ARE] you DOING?
[are/ARE] YOU doing?
[are/ARE] YOU DOING?
...等等。
至于程序的最简单版本,那就是只有零个或一个单词。那里的输出很明显。
综合起来:
- 我们需要编写一个函数来生成所有可能的大写变体列表
- 在简单的情况下,有零个或一个单词,您可以hard-code解决方案
- 在所有其他情况下,我们在 除了第一个单词 之外的所有单词上调用我们的函数,然后制作两个副本,并在每个单词上添加两个不同的大写字母。
我的观察是,如果你计算组合的数量并将每个组合表示为二进制数,那么表示为字符串的二进制数可以用来指示哪些单词应该是大写单词:
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(''))
所以,这个问题的另一种表达方式是:找到给定集合的幂集。
我看到你已经为此编写了一个函数(我从你的问题中复制过来)。我猜你是从 itertools 食谱页面得到的代码。
# 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
我们现在要做的是re-write这个函数使用递归。为此,这是我的方法:
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)
在 运行 函数之后,您将获得所有子集的列表。只需遍历它们并将相应索引处的单词大写即可。
我看到您找到了模块 itertools
。它提供了很多有用的功能来组合各种可能性。
此处每个单词有两种可能:大写和非大写版本。您可以将所有可能性与 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)
输出:
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?