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

Question

Я работаю над проектом и застреваю в точке, о которой я расскажу ниже. У меня есть наборы разрешений. P0, P1 и т. Д. Разрешения могут быть индивидуальными, например, P0, P1, P2 и т. Д. Или в группах P1P2, P3P4P5, P1P7P11P34 ...... разрешения обрабатываются как строки, и мы имеем их в отсортированном порядке (по длине). Вот один из возможных последовательностей входных строк: P1 P2 P4 P23 P0P1 P3P5 P8P13P45P67 .......... .......

Теперь моя работа чтобы увидеть, может ли каждая длинная строка быть сформирована некоторой комбинацией меньших строк. То, что я делаю, я вставляю строки в trie и проверяю, могут ли большие строки быть сделаны с использованием предыдущей строки. Если да, я ничего не делаю; в противном случае, я помещал последнюю увиденную строку в trie.

Проблема у меня в том, что по мере увеличения длины строк мне нужно выполнить перестановки/комбинации строк и проверить, присутствуют они или нет. Теперь классические перестановки строк не будут работать, потому что сначала я должен иметь все перестановки вместе (не один за другим), чтобы проверить, находятся ли они в trie. Перестановка носит порядок, поэтому P0P1 возможен, а не P1P0. Кроме того, существует слишком много перестановок.

Я приводил пример различных комбинаций, чтобы сделать его более понятным. Предположим, у меня есть новая строка разрешений, такая как P0P1P2. Различные комбинации, которые я должен проверить, прежде чем объявить, что мои предыдущие записи в trie не подходят для построения строки.

Обратите внимание, что перестановка не должна содержать никаких разрешений не в строке назначения (новый ввод).

P0 P1 P2 P0P1 P2 P0P1 P1P2 P0P1 P0P2 P0P2 P1 P0P2 P0P1 P0 P1P2

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

Answer 1

Я неправильно понял ваше заявление о проблемах ранее: я думал, что вам нужно получить разрешения в заданном порядке, так что P0P1 позже не будет достаточным для покрытия строки P1P0. Извините за задержку.

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

• Извлечь номера разрешений в набор.
• Очистить мастер-набор.
• Для каждой строки предыдущей,
• Если перед является подмножество текущей строки (без дополнительных разрешений),
• добавить его в основном набор.
• Проверить мастер-набор; если это надмножество входной строки,
• Сообщите, что новая строка покрыта первичными;
• еще добавить новую строку в список приоритетов.

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

Код:

prior = [] # list of prior input sets (only those that weren't redundant) 

with open("permission.txt") as in_file: 
    for in_line in in_file: 
    master = set([]) 
    perm_line = set([int(s) for s in in_line.split('P') if len(s)>0]) 

    # Check each of the shorter (prior) permission strings 
    for short in prior: 
     # If the prior string has no superfluous permissions, add it to the master set. 
     extra = short - perm_line 
     if len(extra) == 0: 
     master = master.union(short) 

    # Did the combination of prior strings cover all of the input line permissions? 
    print in_line, 
    if len(perm_line - master) == 0: 
     print "\tPermissions included in prior strings" 
    else: 
     print "\tFound New permission combinations; adding to reference list" 
     prior.append(perm_line) 

Выход: (входной файл вторит, чтобы сделать эту часть очевидна, я добавил несколько строк)

P1 
    Found New permission combinations; adding to reference list 
P2 
    Found New permission combinations; adding to reference list 
P4 
    Found New permission combinations; adding to reference list 
P23 
    Found New permission combinations; adding to reference list 
P0P1 
    Found New permission combinations; adding to reference list 
P3P5 
    Found New permission combinations; adding to reference list 
P8P13P45P67 
    Found New permission combinations; adding to reference list 
P0P2 
    Found New permission combinations; adding to reference list 
P0P1P3P5 
    Permissions included in prior strings 
P0P1P2 
    Permissions included in prior strings 
P0P1P2P3 
    Found New permission combinations; adding to reference list 

---

UPDATE: Вот как отслеживать наборы разрешений используется для создания новой строки. Сосредоточьтесь на новых объектах обложка и cover_team. Обратите внимание, что это не соответствует минимальному покрытию, хотя вы приблизитесь к этому, если вы добавите новые элементы в до спереди, а не в конец. Это делает обыденный поиск от самого длинного к кратчайшему.

Я взял «дешевый» выход для отчетности, просто распечатав наборы разрешений. Я позволю вам беспокоиться о форматировании.

prior = [] # list of prior input sets (only those that weren't redundant) 

with open("permission.txt") as in_file: 
    for in_line in in_file: 
    master = set([]) 
    cover = set([]) 
    cover_team = [] 
    perm_line = set([int(s) for s in in_line.split('P') if len(s)>0]) 

    # Check each of the shorter (prior) permission strings 
    for short in prior: 
     # If the prior string has no superfluous permissions, add it to the master set. 
     extra = short - perm_line 
     if len(extra) == 0: 
     master = master.union(short) 
     # Does this string add anything new to the coverage? 
     ### print "compare", short, cover 
     if len(short - cover) > 0: 
      cover = cover.union(short) 
      cover_team.append(short) 
      ### print "Add to cover_team:", short 

    # Did the combination of prior strings cover all of the input line permissions? 
    print in_line, 
    if len(perm_line - master) == 0: 
     print "\tPermissions included in prior strings", cover_team 
    else: 
     print "\tFound New permission combinations; adding to reference list" 
     prior.append(perm_line) 

Выход:

P1 
    Found New permission combinations; adding to reference list 
P2 
    Found New permission combinations; adding to reference list 
P4 
    Found New permission combinations; adding to reference list 
P23 
    Found New permission combinations; adding to reference list 
P0P1 
    Found New permission combinations; adding to reference list 
P3P5 
    Found New permission combinations; adding to reference list 
P8P13P45P67 
    Found New permission combinations; adding to reference list 
P0P2 
    Found New permission combinations; adding to reference list 
P0P1P3P5 
    Permissions included in prior strings [set([1]), set([0, 1]), set([3, 5])] 
P0P1P2 
    Permissions included in prior strings [set([1]), set([2]), set([0, 1])] 
P0P1P2P3 
    Found New permission combinations; adding to reference list 
P0P1P2P3P4P5 
    Permissions included in prior strings [set([1]), set([2]), set([4]), set([0, 1]), set([3, 5])] 

Answer 2

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

Вот альтернатива: вы можете представлять каждую строку разрешений в виде битового вектора (используя Python's BitVector package, где бит i вектора задается всякий раз, когда соответствующее разрешение P [i] включено в вашу строку ... это работает с порядок разрешений не имеет значения.

Предположим, у вас есть список ваших бит-бит-бит, называемый bv, который уже отсортирован по длине. Затем вы можете создать свой сокращенный список следующим образом (я принимаю только 68 разрешений , От 0 до 67, с учетом вашего примера):

for v in bv: coll = BitVector(intval=0, size=68) # Null vector for x in reduced: # Look at all accepted strings if (x & v == x): # If all permissions in x are needed coll = coll | x # Record this as a possible substring if (coll != v): # If some permission is missing reduced.append(v) # String can't be represented

В качестве примера, если приведенное содержит P0, P1, P1P2 и P2P3, а следующее значение v = P0P1P2, то coll = P0 | P1 | P1P2 = P0P1P2. Поскольку это строка, которую мы тестируем, мы не нажимаем ее на уменьшенный список.

Если последующее значение равно v = P0P1P3, то coll = P0 | P1, который не равен v, поэтому это значение добавляется. Это происходит потому, что вы не можете получить P3, не принимая P2.