問題タブ [oeis]

巧妙に設計されたネットワークでさえ、どのような制限があるのか​​興味があります。特にこれは、私がいくつかの洞察を使用できるものです:

与えられた：

自明でないサイズのランダムな整数のセット (少なくとも 500 など)

専門的に作成/トレーニングされたニューラル ネットワーク。

仕事：

数値アナグラム:特定の時間枠で可能な整数の無限シーケンスの最大表現を作成します。シーケンスは、閉じた形式 (つまり - n^2、2x+5 など) で表現できるか、または OEIS に登録されています ( http: //oeis.org/ )。シーケンスの作成に使用される数値は、入力セットから任意の順序で取得できます。したがって、ネットワークに (3, 5, 1, 7...) が供給されている場合、(1, 3, 5, 7 ...) を返すことは許容できる結果になります。

ANN をトレーニングして、特定のシーケンス パターン (再び - n^2、2x+5 など) を探すことができることは、私の理解です。私が疑問に思っているのは、n^y や xy+z のようなより一般的なパターンを認識できるようにできるかどうかです。n^y は、安定した「基本パターン」を確立できないほど互いに異なって見えるシーケンスを生成する可能性があるため、それはできないだろうと私は考えています。つまり、ANN の動作 (一連の入力を取得し、検索するようにトレーニングされた静的パターンに対してファジー マッチングを行う) の本質は、検索するようにトレーニングできるものの範囲が制限されていることです。 .

私はこれを正しく理解していますか？

入力セットが与えられると、そこからすべての事前注文関係 (または、同等にすべての弱い注文) を生成する、中途半端に効率的なアルゴリズムを探しています。n 個のラベル付き要素のすべての優先配置と呼ぶこともできます。

最初にサイズ n のすべての順列を生成し、次にそれらのサブシーケンスを '~' で折りたたむことによって、これを実装しようとしましたが、これは多くの重複のために非常に非効率的であり、いくつかの結果を逃しました。サイズは、Fubini 番号 1、1、3、13、75、541、4683、47293、545835、... (OEIS 番号 A000670) で指定され、n と共に急速に成長しています。n=8 まで、最初の数個だけが必要です。

例: A={a, b, c} で n=3 の場合、結果は 13 の予約注文になります。

b>a>c、b>a~c、b>c>a、b~c>a、c>b>a、c>a~b、c>a>b、a~c>b、a> c>b、a>b~c、a>b>c、a~bc、a~b~c

私は三角形シーケンス¹を計算することに興味があります。これは、という制限で(i, j): (0, 0), (1, 0), (1, 1), (2, 0), (2, 1) ... すべてのペアを反復するペアのシーケンスです。i > j という制限を伴う同じシーケンスも興味深いものです。(i, j)i >= j

これらのシーケンスは、とりわけ、n 個の要素セット ( 2 までのシーケンス) から(n, n)^{2個の (おそらく同一の) 要素を選択するすべての方法、または行列3}の下三角要素のインデックスを表します。ialoneの値のシーケンスはOEIS ではA003056jですが、 alone はA002262です。シーケンスは、パフォーマンスが重要になる組み合わせアルゴリズムで頻繁に発生します。

シーケンス内の次の値を生成する単純だが枝分かれした方法は次のとおりです。

ただし、これは、条件をチェックするときに、シーケンスの初期要素を計算する際に多くの誤予測に悩まされます。(i == j)通常、毎回 1 つの誤予測iがインクリメントされます。シーケンスが増加するにつれて、 のiインクリメント頻度が減少するため、誤予測の数が少なくなるため、j++ブランチが支配的になり、適切に予測されます。それでも、いくつかのタイプの組み合わせ検索は、シーケンス内の小さな用語を繰り返し反復するため、分岐のないアプローチまたは予測ミスが少ない他のアプローチを探しています。

多くの用途では、シーケンスの順序はそれほど重要ではないため、上記とは異なる順序で値を生成することは、より良い解決策につながる場合に許容されます。たとえば、jカウントアップではなくカウントダウンできます: (0, 0), (1, 1), (1, 0), (2, 2), (2, 1), ....

¹また、このシーケンスの正しい名前を知りたいと思っています (おそらく、この質問により適切なタイトルを付けます)。私はちょっと「三角形のシーケンス」を作りました。

²ここで、i >= jバージョンはサブマルチセット (反復可能) をi > j表し、バリアントは通常のサブセット (反復なし) を表します。

³ここでは、i >= jバージョンにはメインの対角線が含まれていますが、i > jバリアントには含まれていません。

再帰的な定義を使用して、Hofstadter の Q シーケンスを実装しようとしています。

に対して間違った結果が得られn > 3ます。これが私がこれまでに持っているものです：

オンラインで試してみてください: http://ideone.com/PmnJRO (編集: 修正された正しい実装になりました)

Qwhere nis greater thanの各呼び出しの後にスタックに値が追加され、期待どおりに機能しないため、機能しないと思い2ます-rot。

これを機能させるための簡単な調整はありますか？それとも、おそらく変数を使用して、別のアプローチを使用する必要がありますnか?

OEIS: A005185

OEISで興味のあるシーケンスを見つけました。現在取り組んでいるプログラミング コンテストのソリューション用に、同じシーケンスを C++ で生成したいと考えています。

しかし、シーケンスページで指定されたプログラムがどのように機能するかを理解するのに障害がありました。

これがページに記載されているプログラムです-

PARI とは何かはわかりましたが、このプログラムを C++ に変換できません。C ++で同じシーケンスを生成するのに役立つ提案があれば、大歓迎です。

次のコード スニペットを使用して、C++ でシーケンスを生成しようとしました。しかし、オンライン IDE でいくつかのテストに失敗したため、その間に特定の数値が欠落していると思います。

制限として 16、15、および 12 を選択しました。