Исключить значения при создании списка перестановок

Question

Я знаю, что в Python я могу легко создать список, содержащий все перестановки данной строки, используя функцию permutations(). Теперь представьте, если бы я хотел генерировать только перестановки строки "3212323", которые не содержат строку "33". Как мне достичь этого результата?

Пример:

• "3231322"
• "3332122" <- я не хочу тебя </li>
• "3213223"
• "3223213"
• "2223313" <- я не хочу тебя </li>
• "2322313"
• "2312332" <- я не хочу тебя </li>
• ЕСС ...

Примечание : я знаю, что могу сначала сгенерировать все перестановки, а затем удалить указанные из списка, но мне нужно вообще не генерировать эти перестановки, поэтому откажитесь от них при создании список перестановок.

Любое предложение будет оценено. Заранее спасибо.

Answer 1

Аналогично первой опции _mads , вы также можете использовать функцию filterfalse (предикат, повторяемая) из itertools:

from itertools import permutations, filterfalse

_str = "3212323"

def predicate(iterable):
    return '33' in ''.join(iterable)

filterfalse(predicate, permutations(_str)))

Answer 2

Вы можете использовать генераторы:

original = "3212323"
excluded_substring = '33'
p = (''.join(x) for x in permutations(original))
p = (x for x in p if excluded_substring not in x)

# Or as a one-liner
p = (x for x in (''.join(parts) for parts in permutations(original)) if excluded_substring not in x)

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

Answer 3

Если вы посмотрите на документацию для перестановок , они дадут вам, что это за функция. Вы можете изменить это, чтобы исключить '33'

def permutations(iterable, r=None):
    # permutations('ABCD', 2) --> AB AC AD BA BC BD CA CB CD DA DB DC
    # permutations(range(3)) --> 012 021 102 120 201 210
    pool = tuple(iterable)
    n = len(pool)
    r = n if r is None else r
    if r > n:
        return
    indices = list(range(n))
    cycles = list(range(n, n-r, -1))
    yield tuple(pool[i] for i in indices[:r])
    while n:
        for i in reversed(range(r)):
            cycles[i] -= 1
            if cycles[i] == 0:
                indices[i:] = indices[i+1:] + indices[i:i+1]
                cycles[i] = n - i
            else:
                j = cycles[i]
                indices[i], indices[-j] = indices[-j], indices[i]
                seq = tuple(pool[i] for i in indices[:r])

                # Check if '33' is in sequence
                if '33' not in ''.join(seq):
                    yield seq
                break
        else:
            return

Answer 4

Решение с пользовательским фильтром

from itertools import permutations
a="3212323"
def my_filter(temp):
    if '33' not in ''.join(temp):
        return temp
filter(my_filter,(permutations(a)))

Это Python, так что вы можете увидеть исходный код и изменить его

def permutations1(iterable, r=None):
    # permutations('ABCD', 2) --> AB AC AD BA BC BD CA CB CD DA DB DC
    # permutations(range(3)) --> 012 021 102 120 201 210
    pool = tuple(iterable)
    n = len(pool)
    r = n if r is None else r
    if r > n:
        return
    indices = range(n)
    cycles = range(n, n-r, -1)
    yield tuple(pool[i] for i in indices[:r]) 
    while n:
        for i in reversed(range(r)):
            cycles[i] -= 1
            if cycles[i] == 0:
                indices[i:] = indices[i+1:] + indices[i:i+1]
                cycles[i] = n - i
            else:
                j = cycles[i]
                indices[i], indices[-j] = indices[-j], indices[i]
                temp=tuple(pool[i] for i in indices[:r])
                if '33' not in ''.join(temp):
                    yield temp
                break
        else:
            return

list((permutations1(a)))