如何交错或创建两个字符串的唯一排列（不使用递归）

Question

如何交错或创建两个字符串的唯一排列（不使用递归）

pythonarraysstringalgorithmcomplexity-theory

10

这个问题是要输出两个给定字符串的所有可能交错排列。我在Python中编写了一个可行的代码，运行如下：

def inter(arr1,arr2,p1,p2,arr):
    thisarr = copy(arr)
    if p1 == len(arr1) and p2 == len(arr2):
        printarr(thisarr)
    elif p1 == len(arr1):
        thisarr.extend(arr2[p2:])
        printarr(thisarr)
    elif p2 == len(arr2):
        thisarr.extend(arr1[p1:])
        printarr(thisarr)
    else:
        thisarr.append(arr1[p1])
        inter(arr1,arr2,p1+1,p2,thisarr)
        del thisarr[-1]
        thisarr.append(arr2[p2])
        inter(arr1,arr2,p1,p2+1,thisarr)
    return

该代码在字符串的每个位置进行递归调用，对于一个递归调用，它将当前元素视为属于第一个数组，在下一次调用中，则视为属于另一个数组。因此，如果输入字符串是ab和cd，则输出abcd、acbd、cdab、cabd等。p1和p2是指向数组的指针（因为Python字符串是不可变的，我使用了数组！）。有人能告诉我这段代码的复杂度吗？它是否可以改进？我编写了类似的代码来打印给定数组长度为k的所有组合：

def kcomb(arr,i,thisarr,k):
     thisarr = copy(thisarr)
     j,n = len(thisarr),len(arr)
     if n-i<k-j or j >k:
        return
     if j==k:
        printarr(thisarr)
        return
     if i == n:
         return
     thisarr.append(arr[i])
     kcomb(arr,i+1,thisarr,k)
     del thisarr[-1]
     kcomb(arr,i+1,thisarr,k)
     return

这也是基于相同原理的。那么一般来说，如何找到这种函数的复杂度，以及如何对它们进行优化？可以通过DP完成吗？以下是第一个问题的示例输入输出：

>>> arr1 = ['a','b','c']
>>> arr2 = ['d','e','f']
>>> inter(arr1,arr2,0,0,[])
abcdef
abdcef
abdecf
abdefc
adbcef
adbecf
adbefc
adebcf
adebfc
adefbc
dabcef
dabecf
dabefc
daebcf
daebfc
daefbc
deabcf
deabfc
deafbc
defabc

- SexyBeast

请问您能否发布“printarr”代码？ - Inbar Rose

1

很难理解你在做什么。你能发布输入和期望的输出吗？ - monkut

2

几乎可以实现，但要保留每个字符串的顺序。也就是说，如果string1是“abcd”，而string2是“efgh”，那么在交错的字符串中，“a”应该出现在“b”之前，后者应该出现在“c”之前，后者应该出现在“d”之前。在这些字符之间，应该插入来自string2的字符，但在同样的条件下，保留每个字母的顺序。 - SexyBeast

如果您能提供一些您当前工作代码的“输入”和“输出”，那将非常有帮助。 - Inbar Rose

请查看下面的注释。 - SexyBeast

显示剩余3条评论

4个回答

1

好的，经过一些工作，并使用其他答案的建议，主要是来自lazyr。（现在已将其转换为类）__all_perms 来自：https://dev59.com/OHVD5IYBdhLWcg3wDXJ3#104436

class Interleave():

    def __init__(self, A, B):
        self.A = A
        self.B = B
        self.results = list(self.__interleave())

    # from https://dev59.com/OHVD5IYBdhLWcg3wDXJ3#104436
    def __all_perms(self, elements):
        if len(elements) <=1:
            yield elements
        else:
            for perm in self.__all_perms(elements[1:]):
                for i in range(len(elements)):
                    #nb elements[0:1] works in both string and list contexts
                    yield perm[:i] + elements[0:1] + perm[i:]

    def __sequences(self):
        return list( sorted( set(
            ["".join(x) for x in self.__all_perms(['a'] * len(self.A) + ['b'] * len(self.B))] ) ) )

    def __interleave(self):
        for sequence in self.__sequences():
            result = ""
            a = 0
            b = 0
            for item in sequence:
                if item == 'a':
                    result+=self.A[a]
                    a+=1
                else:
                    result+=self.B[b]
                    b+=1
            yield result

    def __str__(self):
        return str(self.results)

    def __repr__(self):
        return repr(self.results)

这里是用法：

>>> A = ['a', 'b', 'c']
>>> B = ['d', 'e', 'f']
>>> Interleave(A, B)
['abcdef', 'abdcef', 'abdecf', 'abdefc', 'adbcef', 'adbecf', 'adbefc', 'adebcf', 'adebfc', 'adefbc', 'dabcef', 'dabecf', 'dabefc', 'daebcf', 'daebfc', 'daefbc', 'deabcf', 'deabfc', 'deafbc', 'defabc']

此外，您可以像下面这样访问类成员：

>>> inter = Interleave(A, B)
>>> inter.results
['abcdef', 'abdcef', 'abdecf', 'abdefc', 'adbcef', 'adbecf', 'adbefc', 'adebcf', 'adebfc', 'adefbc', 'dabcef', 'dabecf', 'dabefc', 'daebcf', 'daebfc', 'daefbc', 'deabcf', 'deabfc', 'deafbc', 'defabc']
>>> inter.A
['a', 'b', 'c']
>>> inter.B
['d', 'e', 'f']

- Inbar Rose

@Cupidvogel 好的，all_perms() 函数来自于这个回答：https://dev59.com/OHVD5IYBdhLWcg3wDXJ3#104436，因此我不会在这里开始讨论它，因为那里已经讨论过了。`_sequences()` 只是调用了 all_perms()，然后将结果列表转换为字符串，使它们唯一并排序，最后将它们转换为列表并发送到 interleave()，该函数读取列表并根据序列给出的顺序简单地添加来自 A 或 B 的值。 - Inbar Rose

2

请注意，该算法生成所有排列，然后过滤掉重复项，与我的答案中的算法不同。例如，对于长度为10的两个字符串，“__all_perms”会产生2432902008176640000次，而“next_permutation”仅产生必要的184756次。 - Lauritz V. Thaulow

@lazyr 是的，你说得对。在这种情况下最好使用两个答案的组合。当我写这个答案时，我没有看到你写的代码，只看到了你提供的链接，其中有人遇到了类似的问题，以及你制作唯一组合的想法。我想我没有考虑到缩放的问题。 - Inbar Rose

0

permutations 对你有用吗？或者，这是编程惯例吗？

>>> from itertools import permutations
>>> s1 = "ab"
>>> s2 = "cd"
>>> all_values = [c for c in s1 + s2]
>>> ["".join(r) for r in permutations(all_values)]
['abcd', 'abdc', 'acbd', 'acdb', 'adbc', 'adcb', 'bacd', 'badc', 'bcad', 'bcda', 'bdac', 'bdca', 'cabd', 'cadb', 'cbad', 'cbda', 'cdab', 'cdba', 'dabc', 'dacb', 'dbac', 'dbca', 'dcab', 'dcba']

- monkut

不，我正在尝试开发一个可工作的代码，而不是依靠这些内置函数。此外，您的输出是不正确的，在许多输出字符串中，b 在 a 之前出现，而 a 应该始终在 b 之前出现。那是交错，不是排列！ - SexyBeast

我认为这里需要一组排列输出的子集——其中两个输入字符串按顺序交错。因此，abdc不是一个有效的输出。 - Dhara

@Cupidvogel，你完全不感兴趣使用itertools来解决问题吗？ - Lauritz V. Thaulow

1

@Cupidvogel 你对“使用”内置函数有什么意见？ - Dhara

好的，我明白了，一开始我没有看到有序部分。 - monkut

显示剩余2条评论

0

我认为这是你试图做的事情：

from itertools import product, chain

def interleave(a, b):
    if len(b) > len(a):
        a, b = b, a

    boolean = (True, False)
    for z in range(len(a) - len(b) + 1):
        pairs = list(zip(a[z:], b))
        for vector in product(*[boolean] * max(map(len, (a, b)))):
            permutation = (pair if i else reversed(pair)
                           for i, pair in zip(vector, pairs))
            yield a[:z] + ''.join(chain.from_iterable(permutation))

- Joel Cornett

你能看一下我的解决方案并告诉我它的复杂度吗？我正在寻找一种非递归解决方案，而不使用 itertools。 - SexyBeast

好的，你可以轻松地修改它，以不使用itertools。在这种情况下，“product”只是在二进制中迭代所有值之间的“0”和“2 ^ len（a）”，你可能只需执行“range（2 ^ len（a））：”并转换为二进制。我刚意识到，这段代码遗漏了某些交错。但是，可以很容易地修改它以包括它们。我可能能够在几个小时后重新访问这个问题。 - Joel Cornett

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Lauritz V. Thaulow · Accepted Answer

你的问题可以转化为创建特定列表的所有唯一排列。假设arr1和arr2是字符串的长度，分别为A和B，那么可以构建如下列表：

[0] * A + [1] * B

这个列表的唯一排列与字符串 arr1 和 arr2 的所有可能交错序列之间存在一一对应关系（双射）。想法是让排列的每个值指定从哪个字符串中获取下一个字符。以下是一个示例实现，展示如何从排列构造出一个交错序列：

>>> def make_interleave(arr1, arr2, permutation):
...     iters = [iter(arr1), iter(arr2)]
...     return "".join(iters[i].next() for i in permutation)
... 
>>> make_interleave("ab", "cde", [1, 0, 0, 1, 1])
'cabde'

我在Python邮件列表中发现了这个问题，询问如何以高效的方式解决此问题。答案建议使用一个算法，该算法在Knuth的《计算机程序设计艺术》第4卷第2部分“生成所有排列”中进行了描述。我在这里找到了在线草稿PDF版本。该算法还在维基百科文章中进行了描述。

下面是我自己注释过的实现next_permutation算法的Python生成器函数。

def unique_permutations(seq):
    """
    Yield only unique permutations of seq in an efficient way.

    A python implementation of Knuth's "Algorithm L", also known from the 
    std::next_permutation function of C++, and as the permutation algorithm 
    of Narayana Pandita.
    """

    # Precalculate the indices we'll be iterating over for speed
    i_indices = list(range(len(seq) - 1, -1, -1))
    k_indices = i_indices[1:]

    # The algorithm specifies to start with a sorted version
    seq = sorted(seq)

    while True:
        yield seq

        # Working backwards from the last-but-one index,           k
        # we find the index of the first decrease in value.  0 0 1 0 1 1 1 0
        for k in k_indices:
            if seq[k] < seq[k + 1]:
                break
        else:
            # Introducing the slightly unknown python for-else syntax:
            # else is executed only if the break statement was never reached.
            # If this is the case, seq is weakly decreasing, and we're done.
            return

        # Get item from sequence only once, for speed
        k_val = seq[k]

        # Working backwards starting with the last item,           k     i
        # find the first one greater than the one at k       0 0 1 0 1 1 1 0
        for i in i_indices:
            if k_val < seq[i]:
                break

        # Swap them in the most efficient way
        (seq[k], seq[i]) = (seq[i], seq[k])                #       k     i
                                                           # 0 0 1 1 1 1 0 0

        # Reverse the part after but not                           k
        # including k, also efficiently.                     0 0 1 1 0 0 1 1
        seq[k + 1:] = seq[-1:k:-1]

根据此问题，算法每次产生的摊销复杂度为O(1), 但是根据下方评论的rici所说，这只有在所有数字都唯一的情况下才成立，在这种情况下肯定不是这样。

无论如何，产生的次数提供了时间复杂度的下界，它由以下公式给出：

(A + B)! / (A! * B!)

为了找到真正的时间复杂度，我们需要将每个yield的平均复杂度与基于排列构建结果字符串的复杂度相加。如果我们将此总和乘以上述公式，则得到总时间复杂度。