2

私は常に、アルゴリズム、ソート、暗号、バイナリ ツリー、データ圧縮、メモリ操作などに興味を持っていました。

STL 関数 next_perm() を使用した C++ の順列に関する Mark Nelson の記事を読みました。非常に興味深くて便利です。その後、Delphi で次の順列を取得するためのクラス メソッドを 1 つ作成しました。これが現在最もよく使用しているツールだからです。この関数は辞書順で機能します。スタックオーバーフローに関する別のトピックの回答からアルゴのアイデアを得ましたが、今は大きな問題があります。ベクター内の要素が繰り返される順列を使用していますが、必要のない順列がたくさんあります。たとえば、辞書順で 7 つの要素の次の最初の順列があります。

6667778 (6 = 連続 3 回、7 = 連続 3 回)

私の作品では、次のように最大 2 つの要素が連続して繰り返されるパーマのみが有効であると考えています。

6676778 (6 = 連続 2 回、7 = 連続 2 回)

要するに、受け取ったパラメーターに応じて、最大で N 回連続して繰り返される順列のみを返す関数が必要です。

すでにこれを行っているアルゴリズムがあるかどうかは誰にもわかりませんか?

テキストに誤りがあれば申し訳ありませんが、私はまだ英語をあまり上手に話せません。

どうもありがとう、カルロス

4

5 に答える 5

2

私のアプローチは、不正なシーケンスを含む分岐に従わない再帰的なジェネレータです。

Python 3 コードは次のとおりです。

def perm_maxlen(elements, prefix = "", maxlen = 2):
    if not elements: 
        yield prefix + elements
        return

    used = set()

    for i in range(len(elements)):
        element = elements[i]
        if element in used:
            #already searched this path
            continue

        used.add(element)

        suffix = prefix[-maxlen:] + element
        if len(suffix) > maxlen and len(set(suffix)) == 1:
            #would exceed maximum run length
            continue

        sub_elements = elements[:i] + elements[i+1:]
        for perm in perm_maxlen(sub_elements, prefix + element, maxlen):
            yield perm


for perm in perm_maxlen("6667778"):
    print(perm)

実装は速度ではなく読みやすさのために書かれていますが、アルゴリズムは単純にすべての順列をフィルタリングするよりもはるかに高速です。

print(len(perm_maxlen("a"*100 + "b"*100, "", 1)))

たとえば、これはミリ秒単位で実行されますが、単純なフィルタリング ソリューションでは数千年かそこらかかります。

于 2008-12-19T19:52:41.240 に答える
1

N回連続して繰り返される値をスキップする通常の順列関数のラッパーを作成しないのはなぜですか? 何かのようなもの：

(疑似コード)

funciton custom_perm(int max_rep)
  do
    p := next_perm()
  while count_max_rerps(p) < max_rep
  return p
于 2008-12-18T23:04:27.410 に答える
1

ですから、宿題の手伝いのような方法で、私は2つのアプローチを考えることができます.

3 つ以上の連続した繰り返しを含むすべての順列を計算します (これは、3 つ並んだものを 1 つの疑似数字として扱い、通常の順列生成アルゴリズムに渡すことで実行できます)。これらすべてのルックアップ テーブルを作成します。元の文字列のすべての順列を生成し、それらを結果に追加する前にルックアップ テーブルで検索します。

再帰的順列生成アルゴリズムを使用します (最初の数字の各可能性を順番に選択し、残りの数字の順列を生成するために再帰します)。次に、再帰的に呼び出された関数で、渡された 2 つの値が同じ場合、最初の桁がそれらと同じであることを許可しないでください。

于 2008-12-18T13:48:28.297 に答える
0

これは簡単に作成できますが、効率化するのはかなり困難です。

有効な出力のみを考慮し、組み合わせ空間全体をわざわざ調べない単一のコードを作成する必要がある場合は、考えなければならないことがあります。

一方、有効かどうかに関係なく、すべての組み合わせを内部的に生成するコードを使用できる場合は、単純なはずです。

next_perm メソッドを呼び出すことができる新しい列挙子を作成し、すべての組み合わせを生成する他の列挙子を内部的に使用するようにします。

次に、外側の列挙子を while ループで実行し、有効なものが見つかるまで内側の列挙子にさらに順列を要求し、それを生成します。

このための擬似コード:

generator1:
    when called, yield the next combination

generator2:
    internally keep a generator1 object
    when called, keep asking generator1 for a new combination
        check the combination
        if valid, then yield it
于 2008-12-19T18:09:38.983 に答える
0

Krusty、私はすでに関数の最後でそれを行っていますが、すべての順列を生成してそれぞれをチェックする必要があるため、問題は解決しません。

consecutive := 1;
IsValid := True;
for n := 0 to len - 2 do
begin
    if anyVector[n] = anyVector[n + 1] then
        consecutive := consecutive + 1
    else
        consecutive := 1;
    if consecutive > MaxConsecutiveRepeats then
    begin
        IsValid := False;
        Break;
    end;
end;

私は辞書順で最初から始めるので、この方法で必要になると、多くの不要なパーマが生成されます。

于 2008-12-18T23:22:00.183 に答える