Встроенные инструменты для быстрого извлечения кортежей заданной степени с учетом сортировки по [1, 2, ..., n] - PullRequest
Новая
       135

Встроенные инструменты для быстрого извлечения кортежей заданной степени с учетом сортировки по [1, 2, ..., n]

0 голосов
/ 12 июля 2020

Я кодирую 2 математические комбинаторные операции, которые я хочу повторять (как) много раз (насколько это возможно), поэтому скорость, очевидно, имеет решающее значение.

Вот пример того, что я хочу делать как можно быстрее и эффективнее для любого положительного целого числа n и любой оценки (см. пример ниже).

Примечание: Это самостоятельный вопрос, возникший в результате математических экспериментов с Sage. Заранее большое спасибо за вашу помощь.

Пример: Возьмем n = 6 и множество S = {1, 2, ..., n} = {1, 2 , 3, 4, 5, 6}. Есть биномиальные (6, 2) = 15 пар 

[(1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (2, 3), (2, 4), (2, 5), (2, 6), (3, 4), (3, 5), (3, 6), (4, 5), (4, 6), (5, 6)]

в порядке возрастания, которые мы можем извлечь из S. Встроенный инструмент, который мне посоветовали использовать для получения приведенного выше списка, следующий : 

from itertools import combinations
n = 6
iterable = list(range(1, n+1))
r = 2
print(list(combinations(iterable, r)))

Вопрос 0: Есть ли что-нибудь более быстрое в Python?

Теперь позвольте мне выбрать оценку на множестве S в виде функции от S до {1, 2, 3}

оценка: 1, 2, 3 -> 1 и 4, 5 -> 2 и 6 -> 3

Я решил сохранить эту функцию как словарь следующим образом: 

grading = {1: 1, 2: 1, 3: 1, 4: 2, 5: 2, 6: 3}

Что касается этой оценки, мы можем вычислить оценку элементов, пар или кортежей, построенных из S.

Примеры:

  • оценка (2) = 1
  • оценка (5) = 2
  • оценка ((2, 5)) = оценка (2) + оценка (5) = 1 + 2 = 3
  • оценка ((2, 3, 5)) = 1 + 1 + 2 = 5

1 - Первое строительство:

Я хочу, чтобы все пары имели оценку g0 = 4. Вот очевидный способ сделать это, наивно построенный на предыдущем. s строк кода: 

g0 = 4
gradedList = []
for couple in list(combinations(iterable, 2)):
    grade = grading[couple[0]] + grading[couple[1]]
    if grade == g0:
        gradedList.append(couple)
print(gradedList)

Это дает 

[(1, 6), (2, 6), (3, 6), (4, 5)]

по желанию.

Вопрос 1: Есть ли встроенный способ чтобы получить GradedList и / или какой самый быстрый способ сделать это с помощью Python?

2 - Вторая конструкция:

Теперь я хочу извлечь все возрастающие 3-кортежи (i, j, k) с оценкой, равной 4, и которая начинается с i = 1.

Другими словами, мне нужен следующий список: 

[(1, 2, 4), (1, 2, 5), (1, 3, 4), (1, 3, 5)]

Конечно, это можно получить следующим образом: 

newIterable = list(range(2, n+1))
secondGradedList = []
for couple in list(combinations(newIterable, 2)):
    grade = grading[1] + grading[couple[0]] + grading[couple[1]]
    if grade == g0:
        secondGradedList.append((1,) + couple)
print(secondGradedList)

Вопрос 2: Есть ли встроенный способ получить secondGradedList и / или какой самый быстрый способ сделать это с помощью Python?

Спасибо, Жюльен

...