在python中生成不同的字符串组合

Question

我正在做一个项目，并停留在我下面讨论的问题。 我有权限集。P0，P1等。权限可以是单独的，如P0，P1，P2等，也可以是分组P1P2，P3P4P5，P1P7P11P34……权限被视为字符串，我们将它们按排序顺序（基于长度）排列。以下是一个可能的输入字符串序列： 第1页 第2页 第4页 第23页 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是当前字符串的子集（没有额外的权限）
• 将其添加到主集。你知道吗
• 检查主集合；如果它是输入行的超集
• 报告新字符串已被优先级覆盖
• 否则将新字符串添加到优先级列表。你知道吗

我还假设您不需要知道覆盖当前输入行所需的。你知道吗

代码：

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

---

更新：下面是如何跟踪用于生成新字符串的权限集。关注新对象封面和封面团队。请注意，这并没有找到最小的覆盖范围，尽管如果您在前面而不是末尾向prior添加新元素，您将接近这个覆盖范围。这使得例行搜索从最长到最短。你知道吗

我已经采取了“廉价”的方式进行报告，只是打印权限集。我会让你担心格式的问题。你知道吗

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的BitVector package，每当相应的权限p[i]包含在您的字符串中时，就设置向量的位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

例如，如果reduced包含P0、P1、P1P2和P2P3，并且下一个值是v=P0P1P2，则coll=P0 | P1 | P1P2=P0P1P2。因为这是我们正在测试的字符串，所以我们不会把它推到简化列表上。你知道吗

如果后面的值是v=P0P1P3，那么coll=P0 | P1，它不等于v，所以这个值相加。发生这种情况是因为你不能得到P3没有同时采取P2。你知道吗