问题
what is the best way to generate a cartesian product of some lists, not knowing in advance how many lists there are?
如果你喜欢，你可以在这里停止阅读。
背景
我没有钱上学，所以我一边在高速公路收费站上夜班，一边尝试使用互联网自学一些编程。我决定尝试解决一些“编程挑战”问题作为练习。
编程作业
这是我要解决的问题，TopCoder 的属性：
http://community.topcoder.com/stat?c=problem_statement&pm=3496
我不会复制和粘贴完整的描述以尊重他们的版权声明，但我假设我可以总结它，前提是我不逐字使用它的片段（尽管是 IANAL）。
概括
如果历史股票价格的“加权总和”是通过将这些价格的一个子集乘以相等数量的“加权”因子获得的增补总和，前提是后者加起来为1.0，并且是从给定的一组有效值中选择的[-1.0, -0.9, ..., 0.9, 1.0]，对作为函数参数提供的所有历史数据使用此公式，一次检查5 个价格，预测下一个价格并返回“加权因子”的排列" 产生最低的平均预测误差。每次运行将至少有 6 个股票价格，因此保证至少有一个预测，最终结果应在 1E-9 内准确。
测试数据
格式：
- 一行输入数据，
list格式为 - 一行代表预期结果
- 一个空行作为间隔
下载自：
我的解决方案
import itertools
# For a permutation of factors to be used in a weighted sum, it should be chosen
# such than the sum of all factors is 1.
WEIGHTED_SUM_TOTAL = 1.0
FACTORS_CAN_BE_USED_IN_WEIGHTED_SUM = lambda x: sum(x) == WEIGHTED_SUM_TOTAL
# Historical stock price data should be examined using a sliding window of width
# 5 when making predictions about the next price.
N_RECENT_PRICES = 5
# Valid values for weighting factors are: [-1.0, -0.9, ..., 0.9, 1.0]
VALID_WEIGHTS = [x / 10. for x in range(-10, 11)]
# A pre-calculated list of valid weightings to consider. This is the cartesiant
# product of the set of valid weigths considering only the combinations which
# are valid as components of a weighted sum.
CARTESIAN_PRODUCT_FACTORS = [VALID_WEIGHTS] * N_RECENT_PRICES
ALL_PERMUTATIONS_OF_WEIGHTS = itertools.product(*CARTESIAN_PRODUCT_FACTORS)
WEIGHTED_SUM_WEIGHTS = filter(FACTORS_CAN_BE_USED_IN_WEIGHTED_SUM,
ALL_PERMUTATIONS_OF_WEIGHTS)
# Generator function to get sliding windows of a given width from a data set
def sliding_windows(data, window_width):
for i in range(len(data) - window_width):
yield data[i:i + window_width], data[i + window_width]
def avg_error(data):
# The supplied data will guarantee at least one iteration
n_iterations = len(data) - 5
best_average_error = None
# Consider each valid weighting (e.g. permutation of weights)
for weighting in WEIGHTED_SUM_WEIGHTS:
# Keep track of the prediction errors for this weighting
errors_for_this_weighting = []
for historical_data, next_to_predict in sliding_windows(data,
N_RECENT_PRICES):
prediction = sum([a * b for a, b in zip(weighting, historical_data)])
errors_for_this_weighting.append(abs(next_to_predict - prediction))
average_error = sum(errors_for_this_weighting) / n_iterations
if average_error == 0: return average_error
best_average_error = (average_error if not best_average_error else
min(average_error, best_average_error))
return best_average_error
def main():
with open('data.txt') as input_file:
while True:
data = eval(input_file.readline())
expected_result = eval(input_file.readline())
spacer = input_file.readline()
if not spacer:
break
result = avg_error(data)
print expected_result, result, (expected_result - result) < 1e-9
if __name__ == '__main__':
main()
我的问题
我不是要求对我的解决方案进行代码审查，因为这将是错误的 StackExchange 论坛。在这种情况下，我会将我的解决方案发布到“代码审查”。
相反，我的问题是小而精确和明确的，适合这个网站的格式（希望如此）。
在我的代码中，我使用 itertools 生成列表的笛卡尔积。本质上，我并没有自己解决问题的症结，而是将解决方案委托给为我做这件事的图书馆。如果我想从这些练习中学习，我认为这是错误的方法。我应该自己做最难的部分，否则为什么要锻炼呢？所以我想问你：
what is the best way to generate a cartesian product of some lists, not knowing in advance how many lists there are?
这就是我想知道的全部内容，如果您愿意，可以批评我的代码。这很受欢迎，即使它通过了所有测试（总是有更好的做事方式，特别是如果你是像我这样的初学者）但是对于这个问题来说“恰到好处”，我只关注一个方面代码，我遇到的一个具体问题和我不满意的事情。让我告诉你更多，我还将分享规范的“你已经尝试过什么”......
显然，如果我知道列表的数量，我可以输入一些嵌套的 for 循环，就像本练习的顶级求解器在比赛中所做的那样。我尝试编写一个为未知数执行此操作的函数列表的数量，但我不确定采用哪种方法。第一种方法是编写递归函数。从列表 1 中取出元素 1 并将其与列表 2 的元素 1 组合，然后与列表 3 的元素 1 组合，等等。我会将每个“层”中的元素推入堆栈，并在达到所需深度时弹出它们。我想我不会担心“堆栈溢出”，因为可达到的深度是合理的。然后，我努力选择一种数据结构，以尽可能最有效（内存/空间）的方式执行此操作，而不向递归调用传递太多参数。数据结构是否应该存在于调用之外？在通话中被传递？我能达到任何水平的并行性吗？如何？有这么多的问题和这么少的答案，我意识到我需要知道更多来解决这个问题，我可以在正确的方向上轻推。你可以提供一个代码片段，我会研究它。或者只是向我解释处理此类问题的正确“计算机科学”方式是什么。我确信有些事情我没有考虑。
最后，我在上面的解决方案中考虑的事情是，谢天谢地，过滤器过滤了一个生成器，因此完整的笛卡尔积永远不会保存在内存中（就像我在代码中的任何时候执行 list(ALL_PERMUTATIONS_OF_WEIGHTS) 一样）所以我我只为那些实际上可以用作加权和的组合占用内存空间。如果应用于任何允许我在不使用 itertools的情况下生成笛卡尔积的系统，类似的警告会很好。