以不同的顺序生成itertools.product

Question

我有一些排序/评分参数列表。我想生成可能的参数组合（笛卡尔积）。但是，如果参数的数量很大，这个很快（很快!!）就变成了一个非常大的数字。基本上，我想做一个笛卡尔产品，但要早点停下来。

import itertools 
parameter_options = ['1234', 
        '123', 
        '1234'] 
for parameter_set in itertools.product(*parameter_options): 
    print ''.join(parameter_set) 

产生：

111 
112 
113 
114 
121 
122 
123 
124 
131 
132 
133 
134 
... 

我想生成（或类似的东西）：

111 
112 
121 
211 
122 
212 
221 
222 
... 

所以，如果我提前停止，我会至少获得一对夫妇的“好”参数集合，其中一组好的参数主要来自列表的早期。这个特定的顺序会很好，但我对任何改变“下一个排列”选择顺序的技术感兴趣。我希望生成的早期结果包含列表前面的大部分内容，但并不在乎解决方案是先生成113还是122，还是先生成211或112。

我的计划是停止一些排列后产生（也许10K左右？取决于结果）。所以如果有少于截止日期，最终都应该生成。最好每个产生一次。

Answer 1

该解决方案可能不是最好的，因为它会将每个组合简单地存储到内存中，但它确实有效。大数据集可能需要一点时间。

import itertools 
import random 
count = 100 # the (maximum) amount of results 
results = random.sample(list(itertools.product(*parameter_options)), count) 

for parameter_set in results: 
    print "".join(parameter_set) 

这会给你一个随机顺序的产品列表。

Answer 2

我想你可以按照你想要的顺序得到你的结果，如果你想到输出空间的图形遍历输出。你想要一个最接近第一遍，而itertools.product函数是一个深度优先遍历。

尝试这样：

import heapq 

def nearest_first_product(*sequences): 
    start = (0,)*len(sequences) 
    queue = [(0, start)] 
    seen = set([start]) 
    while queue: 
     priority, indexes = heapq.heappop(queue) 
     yield tuple(seq[index] for seq, index in zip(sequences, indexes)) 
     for i in range(len(sequences)): 
      if indexes[i] < len(sequences[i]) - 1: 
       lst = list(indexes) 
       lst[i] += 1 
       new_indexes = tuple(lst) 
       if new_indexes not in seen: 
        new_priority = sum(index * index for index in new_indexes) 
        heapq.heappush(queue, (new_priority, new_indexes)) 
        seen.add(new_indexes) 

输出示例：

for tup in nearest_first_product(range(1, 5), range(1, 4), range(1, 5)): 
    print(tup) 

(1, 1, 1) 
(1, 1, 2) 
(1, 2, 1) 
(2, 1, 1) 
(1, 2, 2) 
(2, 1, 2) 
(2, 2, 1) 
(2, 2, 2) 
(1, 1, 3) 
(1, 3, 1) 
(3, 1, 1) 
(1, 2, 3) 
(1, 3, 2) 
(2, 1, 3) 
(2, 3, 1) 
(3, 1, 2) 
(3, 2, 1) 
(2, 2, 3) 
(2, 3, 2) 
(3, 2, 2) 
(1, 3, 3) 
(3, 1, 3) 
(3, 3, 1) 
(1, 1, 4) 
(2, 3, 3) 
(3, 2, 3) 
(3, 3, 2) 
(4, 1, 1) 
(1, 2, 4) 
(2, 1, 4) 
(4, 1, 2) 
(4, 2, 1) 
(2, 2, 4) 
(4, 2, 2) 
(3, 3, 3) 
(1, 3, 4) 
(3, 1, 4) 
(4, 1, 3) 
(4, 3, 1) 
(2, 3, 4) 
(3, 2, 4) 
(4, 2, 3) 
(4, 3, 2) 
(3, 3, 4) 
(4, 3, 3) 
(4, 1, 4) 
(4, 2, 4) 
(4, 3, 4) 

您可以通过在代码中改变了的new_priority计算得到一堆略有不同的订单。当前版本使用平方笛卡尔距离作为优先级，但如果您想要（例如，将序列中的值合并到索引中，则可以使用其他值）。

如果你没有太在意(1, 1, 3)是否到来之前(1, 2, 2)（只要他们都来后(1, 1, 2)，(1, 2, 1)和(2, 1, 1)），你很可能做一个广度优先遍历，而不是最近一。这会更简单一些，因为您可以使用常规队列（如collections.deque）而不是优先级队列。

这种图遍历使用的队列表示此代码使用一定量的内存。但是，如果您必须在整理结果之前先完成结果，内存的数量会少很多。使用的最大内存与结果空间的表面积成正比，而不是其体积。

Answer 3

您的问题有点模糊不清，但是阅读您的意见和其他答案，似乎您希望实现广度搜索而不是深度搜索的笛卡尔产品实现。

最近我有你同样的需求，但也与它不存储中间结果在内存的要求。这对我来说非常重要，因为我正在处理大量参数（因此是一个非常大的笛卡尔积），而任何存储值或执行递归调用的实现都是不可行的。正如你在你的问题中所述，这似乎也是你的情况。

，因为我没有找到满足这一要求的答案，我来到这个解决方案：

def product(*sequences): 
    '''Breadth First Search Cartesian Product''' 
    # sequences = tuple(tuple(seq) for seqin sequences) 

    def partitions(n, k): 
     for c in combinations(range(n+k-1), k-1): 
      yield (b-a-1 for a, b in zip((-1,)+c, c+(n+k-1,))) 

    max_position = [len(i)-1 for i in sequences] 
    for i in range(sum(max_position)): 
     for positions in partitions(i, len(sequences)): 
      try: 
       yield tuple(map(lambda seq, pos: seq[pos], sequences, positions)) 
      except IndexError: 
       continue 
    yield tuple(map(lambda seq, pos: seq[pos], sequences, max_position)) 

在速度方面，该发生器在一开始不错，但在开始的最新成果越来越慢。所以，虽然这个实现有点慢，但它作为一个不使用内存并且不给出重复值的生成器。

正如我在@Blckknght答案中所提到的，这里的参数也必须是序列（可下标和长度定义的迭代）。但是你也可以通过取消注释第一行来绕过这个限制（牺牲一点内存）。如果您正在使用生成器/迭代器作为参数，这可能很有用。

我希望我帮你，让我知道这是否有助于你的问题。