2

入力には、順列のサイズである「n」の数があり、n個の数（1からnまで）を含むすべての可能な順列を出力する必要がありますが、「231スキーム」の数を拒否する必要があります

「231スキーム」は、順列で、不等式z（1 <2 <3）に適用されるそのような3つの連続した数（x、y、z）を見つけることができることを意味します。

したがって、たとえばn = 4の場合、4になります。=24の順列。そのうちの9つを拒否します...

  • 4231、2431、2341、2314-231があるため
  • 2413、3241-241があるため
  • 3412、3421-341（および342）があるため
  • 1342-342があるため

...そして他の15の可能性を印刷します。

わかりました、それが問題です。私はすでにこのタスクについて考えることに多くの時間を費やしました。そして、私はこのようなものを見つけました：

n = 3の順列を生成し、231を拒否してから、（n = 4の場合）以前に生成されたものに基づいてすべての可能性を生成できます。

だから私は132の順列を選びます。ここで、4をすべての可能な方法で「挿入」します：4132、1432、1342、1324。最初と最後の順列は問題ないので、他の2つを詳しく調べる必要があります。そして、私の考えは、「4」の左側に立っている数字から最大の数字を見つけ、「4」の右側に立っている数字から最小の数字を見つけることです。そして、left_max> right_minの場合、「231スキーム」があります。

たとえば、順列1342：left_max = 3、right_min = 2なので、正しい「231」であり、最終的な回答からそれを拒否します。

コメント、アイデア、ヒントをいただければ幸いです。私の考えは役に立たないかもしれないと思いますが、それは私が持っている最高のものです。それで、他の（おそらくより賢いおよび/またはより複雑な）方法はありますか？

4

2 に答える 2

1

あなたは正しい考えを持っています。1を合計して、順列を繰り返し作成しnます。を追加するときはi、回避したいパターンがに存在しiないことを確認するだけで済みます。

たとえば、パターンが231、の場合、左側の何もが。iの右側の何よりも大きいことを確認しiます。

結果を生成する代わりにすべての結果を印刷したい場合（これによりストレージの問題が回避されます）、辞書式順序で順列を調べることができます。プレフィックスをスキャンし、パターンが存在する場合、たとえば最初のk文字にある場合は、次のプレフィックスに移動します。これにより、反復が少しスピードアップします。

于 2012-05-06T20:32:42.637 に答える
0

古い帽子かもしれませんが、これを追加するだけです。231を回避する順列の数はカタラン数であり、O（2 ^（2n））と見積もることができます（閉じた式もあります）。正確には、n = 15の場合、9,694,845個の数値があります。

カタラン数の漸化式を使用する ここに画像の説明を入力してください

231も回避して、順列の再帰を作成できます。

all_perms(n):
    if (n=0) return [1];
    out = [];
    for i=1,...,n:
        for perm1, perm2 in all_perms(i-1), all_perms(n-i):
            increase all elements in perm2 by i-1;
            append n to perm1 (from the right), then append perm2 to that (from the right);
        add the result of appending into out;

動的計画法/メモ化を使用して、このアルゴリズムをさらに改良できます。

于 2019-06-07T04:32:49.373 に答える