时间戳

首页 > 解决方案 > 构造 1 到 n 的四元组所有可能组合的最有效方法

python - 构造 1 到 n 的四元组所有可能组合的最有效方法

问题描述

这个想法是创建 [a,b,c,d][e,f,g,h] 的所有可能组合，其中 a,b,c,d,e,f,g,h 是从 1 到n. 顺序无关紧要，所以如果我有 [a,b,c,d] 我不想要 [c,b,d,a]。同样适用于 [e,f,g,h]。

我有下面的代码，但它的缺点是 a) 非常慢 b) 占用大量内存（我目前正在尝试 n=30 并使用 13+ GB 的内存。）

def build(n):
    a = []
    b = []
    for i in range(1,n):
       for j in [x for x in range(1,n) if x!= i]:
            for k in [y for y in range(1,n) if (y!= i and y !=j)]:
                for l in [z for z in range(1,n) if (z!= i and z!=j and z !=k)]:
                    if sorted([i,j,k,l]) not in a:
                        a.append(sorted([i,j,k,l]))



    b = a

    c = [i for i in product(a,b) if list(set(i[0]).intersection(i[1])) == []]
    print 'INFO: done building (total: %d sets)'%len(c)
    return c

有没有更有效的方法来实现我想要的？

标签： pythonitertools

解决方案

离开我的脑海，所以这里可能有一些不好的语法。不过，应该足以让您了解如何正确解决问题：

import itertools

def quads(n, required_results=None):
    arr1, arr2 = range(1,n+1), range(1,n+1)
    results = set() # only admits unique combinations
    for combination in itertools.product(arr1, arr2):
        results.add(combination)
        if required_results and required_results = len(results): 
            # if the second argument is passed, no need to go through the whole combination-space
            break
    return results

推荐阅读