2

a2つのソートされたベクトルとが与えられた場合、の合計といくつかの順列であり、一度ソートされると一意でbあるすべてのベクトルを見つけます。ab

次の方法で、求めるベクトルの1つを作成できます。

  • ベクトルaとベクトルの順列を取りbます。
  • それらを合計してくださいc[i]=a[i]+b[i]。
  • 並べ替えc。

一意のベクトルbのセット全体を生成する-順列のセットを見つけることに興味があります。c

例0：a='ccdd'および合計されたベクトルをb='xxyy'
与えます： 'cycydxdx'、、。：と の順列が等しいことに注意してください。どちらの場合も、「ボックスc」と「ボックスd」の両方が正確に1つと1つを取得するためです。'cxcxdydy''cxcydxdy'
b'xyxy''yxyx''x''y'

これは、ボールとボックスのいくつかのグループが同一であるボックス（それぞれに1つ）にMボールを入れることに似ていると思います。更新：文字列が与えられた場合、問題は4つのボックスに10個のボールになります。サイズ2、3、1、4の4つの異なるボックスがあります。ボールはペアごとに区別できません。M
a='aabbbcdddd'b='xxyyzzttqq'

例1：与えられた文字列はとa='xyy'ですb='kkd'。
考えられる解決策：'kkd'、'dkk'。
理由：のすべての一意の順列は、、bおよび'kkd'で'kdk'あることがわかり'dkk'ます。'y'ただし、私たちの制約により、最初の2つの順列は、異なる文字列の同じ文字にマップされるインデックスと等しいと見なされますa。

例2：与えられた文字列はとa='xyy'ですb='khd'。考えられる
解決策：'khd'、、'dkh'。'hkd'

例3：与えられた文字列はとa='xxxx'ですb='khhd'。
考えられる解決策：'khhd'。

Wikipedia / Permutationbで説明されているように、Narayana Panditaのアルゴリズムを使用して、一意の候補順列を生成する問題を解決できます。 2番目の部分はより硬く継ぎ目があります。私のベストショットは、2つの文字列をペアでリストに結合し、並べ替えて、ルックアップセットのキーとして使用することです。（+ join→<code>'xh'、'xd'sort→<code>'xd'、'xh'）。
'xx''hd'

私Mはしばしば非常に大きく、文字列の類似性が一般的であるため、現在b、実際にセットフィルターを通過するよりもはるかに多くの順列を生成します。正しいアルゴリズムを直接生成するアルゴリズムが欲しいです。どんな改善でも大歓迎です。

4

2 に答える 2

2

繰り返される可能性のある要素 (マルチセット) の k 個の組み合わせを生成するには、次のコードが役立ちます。

再帰的な解決策として、次のことを試してください。

各文字の出現回数を数えます。それらが x1 x2 ... xm であり、m 個の異なる文字に対応しているとします。

次に、可能なすべての順序対 (y1 y2 ... ym) を見つける必要があります。

0 <= イ <= シ

そして、Sum yi = k.

ここで、yi は文字 i の出現回数です。

アイデアは、char 1 が現れる回数 (y1) を修正することです。次に、残りから k-y1 のすべての組み合わせを再帰的に生成します。

疑似コード:

List Generate (int [] x /* array index starting at 1*/, 
               int k /* size of set */) {

    list = List.Empty;

    if (Sum(x) < k) return list;

    for (int i = 0; i <= x[1], i++) {

        // Remove first element and generate subsets of size k-i.

        remaining = x.Remove(1);

        list_i = Generate(remaining, k-i);

        if (list_i.NotEmpty()) {

            list = list + list_i;    

        } else {

            return list;
        }

    }

    return list;
}

編集前:

私がそれを正しく理解していれば、文字列 a を見て、1 回だけ出現する記号を確認する必要があります。そのようなシンボルが k 個あるとします。次に、k 個の要素を含み、対応する位置にあるそれらのシンボルにマップする b のすべての可能な順列を生成する必要があります。残りは、必要に応じて無視/入力できます。

そのための C# コードをここに投稿したことを覚えています: How to find permut of k in a given length?

xxyy は一意の文字列を 1 つだけ与え、正確に 1 回出現する文字列が「識別」ポイントであると想定しています。

例えばの場合a=xyy, b=add

見分けるポイントは×

したがって、長さ 1 の 'add' の順列を選択します。これらにより、aとが得られますd。

したがってadd、dad (or dda)必要なものは と です。

為にa=xyyz b=good

識別点は x と z

したがって、長さ 2 の b の順列を生成します。

go
og
oo
od
do
gd
dg

あなたに7つのユニークな順列を与えます。

それは役に立ちますか？私の理解は正しいですか？

于 2010-06-18T23:39:33.057 に答える
0

わかりました、問題を明確に説明できなかったことを申し訳ありませんが、ここに解決策があります。

combinationsとの 2 つの関数が必要runvector(v)です。combinations(s,k)長さ のマルチセットの一意の組み合わせを生成しkます。s='xxyy'これらは になります['xx','xy','yy']。runvector(v)ソートされたベクトルとして表されるマルチセットを、より単純な構造であるランベクトルに変換します。runvector('cddeee')=[1,2,3].

この問題を解決するために、再帰ジェネレーターを使用します。ボックス 1 に収まるすべての組み合わせと、残りのボックスのリソースを実行し、既に選択した値を禁止します。禁止を達成するcombinationsために、呼び出し全体で bitarray を維持します。

Python では、アプローチは次のようになります。

def fillrest(banned,out,rv,b,i):
    if i == len(rv):
        yield None
        return
    for comb in combinations(b,rv[i],banned):
        out[i] = comb
        for rest in fillrest(banned,out,rv,b,i+1):
            yield None

def balls(a,b):
    rv = runvector(a)
    banned = [False for _ in b]
    out = [None for _ in rv]
    for _ in fill(out,rv,0,b,banned):
        yield out[:]

>>> print list(balls('abbccc','xyyzzz'))
[['x', 'yy', 'zzz'],
 ['x', 'yz', 'yzz'],
 ['x', 'zz', 'yyz'],
 ['y', 'xy', 'zzz'],
 ['y', 'xz', 'yzz'],
 ['y', 'yz', 'xzz'],
 ['y', 'zz', 'xyz'],
 ['z', 'xy', 'yzz'],
 ['z', 'xz', 'yyz'],
 ['z', 'yy', 'xzz'],
 ['z', 'yz', 'xyz'],
 ['z', 'zz', 'xyy']]

出力は「ボックス」形式ですが、単純な文字列に簡単にマージできます: 'xyyzzzz', 'xyzyzz'...

于 2010-06-20T20:01:02.743 に答える