Наиболее эффективный способ построить все возможные комбинации четверки для 1 к n - PullRequest
Новая
       8

Наиболее эффективный способ построить все возможные комбинации четверки для 1 к n

0 голосов
/ 17 января 2019

Идея состоит в том, чтобы создать все возможные комбинации [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].

У меня есть код ниже, который работает, но имеет недостаток в том, что а) чрезвычайно медленный и б) занимает безумное количество памяти (в настоящее время я пытаюсь n = 30 и использую 13+ ГБ памяти.) 

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

Есть ли более эффективный способ достижения того, чего я хочу?

1 Ответ

0 голосов
/ 17 января 2019

Отрываясь от головы, так что здесь может быть какой-то плохой синтаксис. Должно быть достаточно, чтобы дать вам представление о том, как вы могли бы правильно решить проблему самостоятельно: 

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
...