n个列表的Python笛卡尔积,编码时n未知

Question

题

---

• 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格式为
• 预期结果的一行
• 一个空行作为间隔

下载地址:

• http://paste.ubuntu.com/1229857/

我的解决方案

---

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论坛.在这种情况下,我会将解决方案发布到"Code Review".

相反,我的问题是小而精确且毫不含糊,适合这个网站的格式(希望如此).

在我的代码中,我使用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等组合.我将从每个"层"的元素推入堆栈并在达到所需深度时弹出它们.我想我不会害怕"堆栈溢出",因为深度可达是合理的.然后,我努力选择一种数据结构,以尽可能最有效(内存/空间)的方式完成此操作,而不会向递归调用传递太多参数.数据结构是否应该存在于调用之外？在电话中传递？我能达到任何级别的并行度吗？怎么样？有这么多的问题和很少的答案,我意识到我需要知道更多来解决这个问题,我可以使用正确的方向轻推.你可以提供一个代码片段,我会研究它.或者只是向我解释一下处理这类问题的正确"计算机科学"方法是什么.我确信有一些我不在考虑的事情.

最后,我的东西都在我的解决方案考虑以上是谢天谢地滤波器滤波发生器等等全笛卡儿积是永远不会保存在内存中(因为它想如果我在代码中的任何时候做了一个列表(ALL_PERMUTATIONS_OF_WEIGHTS)),所以我只占那些实际上可以用作加权和的组合占用记忆中的空间.如果应用于任何系统允许我在不使用itertools的情况下生成笛卡尔积,那么类似的警告会很好.

Answer 1

想想数字是如何书写的（十进制或任何其他系统）。即使不需要也包含零：

00000
00001
00002
...
00009
00010
00011
00012
...
99998
99999

您可以看到这看起来像 5 个列表的笛卡尔积list(range(10))（在本例中）。您可以通过增加“最低”数字来非常轻松地生成此输出，当它到达列表中的最后一个数字时，将其设置为第一个元素并增加“下一个最高”数字。for当然，您仍然需要循环，但数量非常少。当您处理任意数量的任意列表时，请使用类似的方法。

例如，如果您有 3 个列表：['a', 'b', 'c'], ['x', 'y'], ['1', '2']，您将得到：

ax1
ax2
ay1
ay2
bx1
bx2
by1
by2
cy1
cy2
cx1
cx2

祝你好运！

编辑：

如果您愿意，这里有一个示例代码来执行此操作。我不使用递归只是为了表明这是多么简单。当然，递归也是一个很好的方法。

def lex_gen(bounds):
    elem = [0] * len(bounds)
    while True:
        yield elem
        i = 0
        while elem[i] == bounds[i] - 1:
            elem[i] = 0
            i += 1
            if i == len(bounds):
                raise StopIteration
        elem[i] += 1

def cart_product(lists):
    bounds = [len(lst) for lst in lists]
    for elem in lex_gen(bounds):
        yield [lists[i][elem[i]] for i in range(len(lists))]


for k in cart_product([['1', '2'], ['x', 'y'], ['a', 'b', 'c']]):
    print(k)