問題タブ [inversion]

P = [a1, a2, ... , aN]最初のN自然数の順列は反転 I = [i1, i2, ... , iN]のリストで表すことができます。ここで、順列で以前に見つかったiKよりも大きい数がいくつあるかがわかります。KKP

例: の場合P = [3, 1, 4, 2]、I = [1, 2, 0, 0](3 は 1 に配置され、3 と 4 は 2 の前に配置されますが、3 と 4 の前にはそれ以上の数字はありません)。

順列を標準形式から反転形式に変換して実行する明らかなアルゴリズムがありますO(N^2)(定義に従ってカウントするだけです)。同じことが逆変換にも当てはまります (これはやや単純ではありません)。

時間の複雑度が低いアルゴリズムはありますか?

それぞれが N 区間 (数直線のサブセット) を含む 2 つのリストが与えられ、各区間は始点と終点の形式を持ちます。あるリストからのこれらの間隔の何組が、別のリストからの間隔を含んでいますか?

例えば：

リストAが{(1,7), (2,9)}あり、リストBが{(3,6), (5,8)}

次に、A が B の間隔を含む間隔を持つペアの数は 3 ペアになります。

目標は、O(n log n) を撃つことです。

現在、私のアルゴリズムは、最初に x 座標で並べ替え、それを 1 つのリストとして取得することです。次に、リストを y 座標で並べ替え、2 つのリスト間の反転を数えます。しかし、私の質問は、なぜこれが機能するのですか? 任意の洞察をいただければ幸いです。

私が現在視覚化している方法は、次の幾何学的な方法です(線の各交点は数値反転のカウントです):

注：リストのリストで反転をチェックする方法がわかりません。O（n log n）を与えるアプローチを取得しようとしています。提案を聞いて喜んで他のアプローチがある場合。

サブセット反転に基づくソート アルゴリズムを探しています。これはパンケーキの並べ替えのようなものですが、へらの上にすべてのパンケーキを取る代わりに、必要なサブセットを反転させることができます. サブセットの長さは問題ではありません。このように: http://www.yourgenome.org/sites/default/files/illustrations/diagram/dna_mutations_inversion_yourgenome.png したがって、すべてを反転させずに単純に数値を交換することはできません。

これは、ショウジョウバエの 1 つの亜種が他の亜種にどのように変異するかを判断するために行っています。どちらも同じ遺伝子を持っていますが、順序が異なります。2 番目の亜種のゲノムは「ソート」されています。つまり、遺伝子番号は 1 ～ 25 です。最初の亜種ゲノムはソートされていません。したがって、ソートアルゴリズムを探しています。

これは、私たちが見ている「ゲノム」です (ただし、すべての数字のリストでこれを機能させることができるはずです):

2 つの別々の問題を検討しています。

1) 反転の少ない 25 個の数字のリストを並べ替えるには

2) 25 個の数字のリストを並べ替えるには、移動する数字の数が最も少なくなるようにします。

左から右に移動し、次に低い値を検索し、その間のすべてを反転させることで、このように並べ替える方法を既に見つけましたが、これをより高速に実行できるはずであることは間違いありません。しかし、まだ他の方法が見つからないので、あなたの助けを求めています!

現在、私たちは Python で作業していますが、これは Python での経験が最も多いためですが、より効率的にこれに取り組む方法についての疑似コードのアイデアがあれば喜んで提供します。別の言語の方が適していると思われる場合は、お知らせください。疑似コード、アイデア、考え、実際のコードはすべて大歓迎です!

前もって感謝します！

数値の配列で反転を見つけるコードを作成しようとしています。Merge Sort を使用して正しく行うアルゴリズムを見てきましたが、ロジックに関して質問があります。

左と右の部分配列の反転、および 2 つの間の反転をカウントする必要があるのはなぜですか? 明らかにそれは正しいのですが、マージ ステップですべての反転を数えることができないのはなぜですか? マージを実行するすべてのレベルで、反転の数を直接数えることができ、2 倍のサイズの部分配列が生成された後、その 2 つの要素の相対的な順序は、後続のマージ ステップで決して変化しないことがわかります。つまり、最終的に反転にならない反転はカウントされません。では、ロジックの何が問題なのか、正しい答えが得られないからです。

必要に応じて、例やコードで詳しく説明できます。意図的にコードを含めなかったので、誰もこれが宿題だとは思わない.

編集：これまでのところ、ロジックに問題はありませんが、代わりに間違った答えにつながるコードのバグが見つかりました。

したがって、配列内の反転を見つける方法は次のとおりです。

mergeAndCount()メソッドは明らかな方法で機能します。

そして、 count をゼロに設定してメソッドを呼び出します: findInversions(0, numbers.length - 1, 0)。

明らかに問題は、countさまざまな再帰間でその値を保持しないことです。これは Java であるため、アンパサンドを付けて渡す必要はなく、その値を で返しますmergeAndCount()。ここで何が問題なのですか？

ここに問題があります: 3x3 行列の逆行列を計算したいのです。solve(J) を使用しようとしましたが、エラー メッセージが表示されます。

solve.default(J) のエラー: 'a' は数値行列でなければなりません。

行列 J とコードは次のとおりです。

どうしたの？？？どうもありがとうございました。Obs: T2、T3、および T4 の値を変更してこれを複数回再計算する必要があるため、T2、T3、および T4 を 50 で置き換えることはできません。

これは、このウェブサイトでの私の最初の質問です。私は（必死に）自分のプログラムで大きな行列を反転しようとしています。これを行うためにlapackを使用したいと思います。非常に有望に見えるこのスレッドを見つけましたが、C++言語だと思います。手伝ってくれませんか？

C で lapack を使用して逆行列を計算する

ありがとうございました。

更新: そうです、答えは少し不明確です。投稿したプログラムを私のものに組み込んだ後、次のエラーが発生します。

問題は、llapack ライブラリを適切にインストールしていないか、コンパイル中にそれを含めていることだと思います。

これは私がライブラリをインストールした方法です（ターミナルから、私はUbuntuを持っています）：

そして、これが私がコンパイルする方法です：

私は何を間違っていますか？

MergeSort を使用してファイルから反転をカウントしようとしています。私のコードは小さなファイルでは機能するようですが、大きなファイルでは間違った出力が生成されます。私のコード:

InversionCount.py:

アプリケーション.py:

答えは 2407905288 ですが、最終的に表示されるカウントは 22945388587258 です。自分でアルゴリズムを学ぼうとしているので、これについて何か助けていただければ幸いです。また、私の問題は大きなファイルで発生するので、非常に大きな入力でのみ発生するように見える問題をデバッグするにはどうすればよいですか (これを小さな入力でテストしてみましたが、正しい答えが得られます)。ありがとうございました！