Itertools с условиями в Python 3 - PullRequest
Новая
       37

Itertools с условиями в Python 3

0 голосов
/ 25 сентября 2018

Я пытаюсь сгенерировать несколько векторов с числами [0....k-1] и длиной k ^ n.n и k были даны ранее. 

k = 4
n = 2
args = list(product(range(k), repeat=n))
# vector=str([i for i in range(k)]*(n+1))
for i in product(range(k), repeat=k ** n):
    if (check(i, args)): print(i)

Комментированная строка не важна, это была моя идея.Мне нужно сгенерировать эти векторы с условием: я хочу видеть каждое число из [0; k-1] в моих векторах больше или равно (n) раз.Так что это задача о перестановках с заменами на специальные условия для контроля чисел, которые я могу получить.Что мне делать?

Например, у меня есть вектор k = 2, n = 2 из 4 элементов, и я хочу видеть 0 и 1 ДВА или более раз.Я должен получить 0011 0101 0110 1001 1010 1100

Все просто, например, но когда k = 5, n = 2 (например), есть вектор размером 25, и я хочу видеть 0 1 2 3 4 2 раза и другие 17цифры должны быть от 0 1 2 3 4 становится трудно.

1 Ответ

0 голосов
/ 25 сентября 2018

ОБНОВЛЕНИЕ:

Вот решение, которое генерирует только необходимые комбинации.Это в принципе быстрее, хотя сложность все еще экспоненциальна, и вы можете быстро выйти за пределы рекурсии. 

def my_vectors(k, n):
    # Minimum repetitions per element
    base_repetitions = [n] * k
    # "Unassigned" repetitions
    rest = k ** n - k * n
    # List reused for permutation construction
    permutation = [-1] * (k ** n)
    # For each possible repetition assignment
    for repetitions in make_repetitions(base_repetitions, rest):
        # Make all possible permutations
        yield from make_permutations(repetitions, permutation)

# Finds all possible repetition assignments
def make_repetitions(repetitions, rest, first=0):
    if rest <= 0:
        yield repetitions
    else:
        for i in range(first, len(repetitions)):
            repetitions[i] += 1
            yield from make_repetitions(repetitions, rest - 1, i)
            repetitions[i] -= 1

# Make all permutations with repetitions
def make_permutations(repetitions, permutation, idx=0):
    if idx >= len(permutation):
        yield list(permutation)
        # If you are going to use the permutation within a loop only
        # maybe you can avoid copying the list and do just:
        # yield permutation
    else:
        for elem in range(len(repetitions)):
            if repetitions[elem] > 0:
                repetitions[elem] -= 1
                permutation[idx] = elem
                yield from make_permutations(repetitions, permutation, idx + 1)
                repetitions[elem] += 1

for v in my_vectors(3, 2):
    print(v)

Вывод: 

(0, 0, 0, 0, 0, 1, 1, 2, 2)
(0, 0, 0, 0, 0, 1, 2, 1, 2)
(0, 0, 0, 0, 0, 1, 2, 2, 1)
(0, 0, 0, 0, 0, 2, 1, 1, 2)
(0, 0, 0, 0, 0, 2, 1, 2, 1)
(0, 0, 0, 0, 0, 2, 2, 1, 1)
(0, 0, 0, 0, 1, 0, 1, 2, 2)
(0, 0, 0, 0, 1, 0, 2, 1, 2)
(0, 0, 0, 0, 1, 0, 2, 2, 1)
(0, 0, 0, 0, 1, 1, 0, 2, 2)
...

Это неэффективно, нопростой способ реализовать это: 

from itertools import product
from collections import Counter

def my_vectors(k, n):
    for v in product(range(k), repeat=k ** n):
        count = Counter(v)
        if all(count[i] >= n for i in range(k)):
            yield v

for v in my_vectors(3, 2):
    print(v)

Вывод: 

(0, 0, 0, 0, 0, 1, 1, 2, 2)
(0, 0, 0, 0, 0, 1, 2, 1, 2)
(0, 0, 0, 0, 0, 1, 2, 2, 1)
(0, 0, 0, 0, 0, 2, 1, 1, 2)
(0, 0, 0, 0, 0, 2, 1, 2, 1)
(0, 0, 0, 0, 0, 2, 2, 1, 1)
(0, 0, 0, 0, 1, 0, 1, 2, 2)
(0, 0, 0, 0, 1, 0, 2, 1, 2)
(0, 0, 0, 0, 1, 0, 2, 2, 1)
(0, 0, 0, 0, 1, 1, 0, 2, 2)
...

Очевидно, что, как только ваши числа станут немного больше, они будут работать вечно, так что это полезно только дляочень маленькие проблемы или в качестве базового уровня для сравнения.

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

...