Создайте процент всех возможных комбинаций из списка чисел - PullRequest
Новая
       5

Создайте процент всех возможных комбинаций из списка чисел

0 голосов
/ 04 марта 2020

Я знаю, что itertools.combinations(iterable, r) возвращает комбинации списка / кортежа элементов (как итерируемые). Как я могу построить функцию вокруг нее, которая возвращает только х% всех комбинаций? (мне просто нужен список кортежей, поэтому он не должен быть итератором). Я хочу, чтобы, если комбинаций было очень мало, например, nCn, он должен возвращать все (в данном случае одну) из них (так минимум 1).

Ответы [ 2 ]

2 голосов
/ 04 марта 2020

С помощью itertools.islice вы можете создать итератор с верхней границей числа элементов: 

import itertools

MAX_COMBS = 2
combs = itertools.combinations(range(3), 2)
combs_slice = itertools.islice(combs, MAX_COMBS)
print(*combs_slice, sep='\n')
# (0, 1)
# (0, 2)

Если размер повторяемого элемента равен len, то Вы можете сделать верхний предел зависимым от общего количества комбинаций: 

import itertools
import math

# Percentage of combinations to draw
COMB_RATIO = 0.2
# Lower bound for number of combinations
MIN_COMBS = 2

iterable = range(5)
k = 3
combs = itertools.combinations(iterable, k)
max_combs = max(round(COMB_RATIO * math.comb(len(iterable), k)), MIN_COMBS)
combs_slice = itertools.islice(combs, max_combs)
print(*combs_slice, sep='\n')
# (0, 1, 2)
# (0, 1, 3)
# (0, 1, 4)

iterable = range(3)
k = 2
combs = itertools.combinations(iterable, k)
max_combs = max(round(COMB_RATIO * math.comb(len(iterable), k)), MIN_COMBS)
combs_slice = itertools.islice(combs, max_combs)
print(*combs_slice, sep='\n')
# (0, 1)
# (0, 2)

Примечание: math.comb был введен в Python 3.8, если вы находитесь в предыдущей версии, вы может потребоваться развернуть собственную реализацию или взять ее, например, от SciPy .

0 голосов
/ 04 марта 2020

Поскольку итераторы не несут информацию о длине своих коллекций, вы не можете получить длину из нее.

В вашем случае вы можете определить размер комбинации, используя формулу n! / (k! (nk)!) и итерация до вашего процента.

Например: 

from math import factorial, ceil

def my_combinations():
    ratio = .2 # 20 percent
    a = range(10)
    n = len(a)
    k = 5
    it = itertools.combinations(a, k)
    total_combinations = factorial(n) / factorial(k) / factorial(n-k)

    for _ in range(ceil(total_combinations * ratio)):
        yield it.next()
...