9

問題は、2つの指定された文字列のすべての可能なインターリーブを印刷することです。だから私は次のように実行される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

文字列の各ポイントで発生し、1回の再帰呼び出しでは、現在の要素が最初の配列に属していると見なされ、次の呼び出しでは、他の配列に属していると見なされます。したがって、入力文字列がabandの場合、、、、、などがcd出力され、abcd配列acbdへのポインタになります（Python文字列は不変であるため、配列を使用しています！）。誰かが私に、このコードの複雑さは何ですか、そしてそれが改善できるかどうか教えてもらえますか？特定の配列から長さのすべての組み合わせを出力するための同様のコードを作成しました。cdabcabdp1p2k

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
4

4 に答える 4

26

問題は、特定のリストのすべての一意の順列を作成する問題に減らすことができます。と言うAと、それぞれ文字列とBの長さです。次に、次のようなリストを作成します。arr1arr2

[0] * A + [1] * B

このリストの一意の順列から、2つの文字列arr1とのすべての可能なインターリーブへの1対1の対応（全単射）が存在します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のThe Art of Computer Programming、Volume 4、Fascicle 2：GeneratingAllPermutationsで説明されているアルゴリズムを使用することを示唆しています。ドラフトのオンライン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！）

次に、リアルタイムの複雑さを見つけるために、各歩留まりの平均の複雑さと、順列に基づいて結果の文字列を構築する複雑さを合計する必要があります。この合計に上記の式を掛けると、合計時間計算量が得られます。

于 2012-10-11T10:38:43.920 に答える
1

さて、いくつかの作業の後、そして他の答えからのアドバイスを使用してください。主にlazyr。（そして今それをクラスに変換しました）__all_permsはhttps://stackoverflow.com/a/104436/1561176からのものです

class Interleave():

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

    # from https://stackoverflow.com/a/104436/1561176
    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']
于 2012-10-11T11:05:44.593 に答える
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']
于 2012-10-11T09:48:03.147 に答える
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))
于 2012-10-11T09:55:06.623 に答える