これが役立つかどうかはわかりませんが、別の解決策は次のとおりです。
int lexic_ix(int* A, int n){ //n = last index = number of digits - 1
int value = 0;
int x = 0;
for(int i=0 ; i<n ; i++){
int diff = (A[i] - x); //pb1
if(diff > 0)
{
for(int j=0 ; j<i ; j++)//pb2
{
if(A[j]<A[i] && A[j] > x)
{
if(A[j]==x+1)
{
x++;
}
diff--;
}
}
value += diff;
}
else
{
x++;
}
value *= n - i;
}
return value;
}
内部ループを取り除くことができなかったため、複雑さは最悪の場合は o(n log(n)) ですが、最良の場合は o(n) であり、全体で o(n log(n)) であるソリューションに対してケース。
または、内側のループを次のように置き換えて、内側のループで別の検証を犠牲にしていくつかの最悪のケースを取り除くことができます。
int j=0;
while(diff>1 && j<i)
{
if(A[j]<A[i])
{
if(A[j]==x+1)
{
x++;
}
diff--;
}
j++;
}
説明:
（または、「そのコードでどのように終了したか」というより、あなたのものとそれほど変わらないと思いますが、おそらくアイデアを持たせることができます）（混乱を避けるために、代わりに文字を使用し、数字と4文字のみを使用しました）
abcd 0 = ((0 * 3 + 0) * 2 + 0) * 1 + 0
abdc 1 = ((0 * 3 + 0) * 2 + 1) * 1 + 0
acbd 2 = ((0 * 3 + 1) * 2 + 0) * 1 + 0
acdb 3 = ((0 * 3 + 1) * 2 + 1) * 1 + 0
adbc 4 = ((0 * 3 + 2) * 2 + 0) * 1 + 0
adcb 5 = ((0 * 3 + 2) * 2 + 1) * 1 + 0 //pb1
bacd 6 = ((1 * 3 + 0) * 2 + 0) * 1 + 0
badc 7 = ((1 * 3 + 0) * 2 + 1) * 1 + 0
bcad 8 = ((1 * 3 + 1) * 2 + 0) * 1 + 0 //First reflexion
bcda 9 = ((1 * 3 + 1) * 2 + 1) * 1 + 0
bdac 10 = ((1 * 3 + 2) * 2 + 0) * 1 + 0
bdca 11 = ((1 * 3 + 2) * 2 + 1) * 1 + 0
cabd 12 = ((2 * 3 + 0) * 2 + 0) * 1 + 0
cadb 13 = ((2 * 3 + 0) * 2 + 1) * 1 + 0
cbad 14 = ((2 * 3 + 1) * 2 + 0) * 1 + 0
cbda 15 = ((2 * 3 + 1) * 2 + 1) * 1 + 0 //pb2
cdab 16 = ((2 * 3 + 2) * 2 + 0) * 1 + 0
cdba 17 = ((2 * 3 + 2) * 2 + 1) * 1 + 0
[...]
dcba 23 = ((3 * 3 + 2) * 2 + 1) * 1 + 0
最初の「反射」 :
エントロピーの観点。abcd は「エントロピー」が最も少ないです。キャラクターが「あるべきではない」場所にいる場合、エントロピーが作成され、エントロピーは早いほど最大になります。
たとえば、bcad の場合、辞書式インデックスは 8 = (( 1 * 3 + 1 ) * 2 + 0 ) * 1 + 0であり、次のように計算できます。
value = 0;
value += max(b - a, 0); // = 1; (a "should be" in the first place [to create the less possible entropy] but instead it is b)
value *= 3 - 0; //last index - current index
value += max(c - b, 0); // = 1; (b "should be" in the second place but instead it is c)
value *= 3 - 1;
value += max(a - c, 0); // = 0; (a "should have been" put earlier, so it does not create entropy to put it there)
value *= 3 - 2;
value += max(d - d, 0); // = 0;
最後の操作は常に何もしないことに注意してください。
最初の問題(pb1) :
たとえば、adcb の場合、最初のロジックは機能しません (((0* 3+ 2) * 2+ 0) * 1 = 4 の辞書式インデックスにつながります)。 bの前に。そのため、x を追加しました。これは、まだ配置されていない最初の数字/文字を表します。x では、diff を負にすることはできません。adcb の場合、辞書式インデックスは 5 = (( 0 * 3 + 2 ) * 2 + 1 ) * 1 + 0 であり、次のように計算できます。
value = 0; x=0;
diff = a - a; // = 0; (a is in the right place)
diff == 0 => x++; //x=b now and we don't modify value
value *= 3 - 0; //last index - current index
diff = d - b; // = 2; (b "should be" there (it's x) but instead it is d)
diff > 0 => value += diff; //we add diff to value and we don't modify x
diff = c - b; // = 1; (b "should be" there but instead it is c) This is where it differs from the first reflexion
diff > 0 => value += diff;
value *= 3 - 2;
2 番目の問題(pb2):
たとえば、cbda の場合、辞書式インデックスは 15 = ((2 * 3 + 1) * 2 + 1) * 1 + 0 ですが、最初の反射では ((2 * 3 + 0) * 2 + 1) * 1 となります。 + 0 = 13 となり、pb1 の解は ((2 * 3 + 1) * 2 + 3) * 1 + 0 = 17 になります。配置する最後の 2 文字が d と a であるため、pb1 の解は機能しません。そのため、d - 3 ではなく 1 を「意味」します。その前に配置された文字をカウントする必要がありましたが、x の後ではなく、内側のループを追加する必要がありました。
すべてをまとめると:
次に、pb1 は pb2 の特定のケースにすぎないことに気付きました。x を削除し、単純に diff = A[i] を使用すると、ソリューションのネストされていないバージョンになることに気付きました (階乗が少しずつ計算され、あなたのxに対応する私の差分）。
したがって、基本的に、私の「貢献」(私が思うに) は、変数 x を追加することです。これにより、diff が 0 または 1 に等しい場合に内部ループを実行することを回避できます。 .
また、内側のループ (if(A[j]==x+1)) で x をインクリメントする必要があるかどうかも確認しました。もう一度内側のループに入り、c に遭遇します。内側のループで x にチェックを入れると、d に遭遇したときは内側のループを行うしかありませんが、x は c に更新され、c に遭遇すると内側のループには入らなくなります。プログラムを壊さずにこのチェックを削除できます
代替バージョンと内部ループのチェックにより、4 つの異なるバージョンが作成されます。チェック付きの代替案は内側のループが少ない方が入るので、「理論的な複雑さ」という点ではベストなのですが、性能・演算数という点ではわかりません。
これがすべて役立つことを願っています（質問はかなり古く、すべての回答を詳細に読んだわけではないため）。そうでない場合でも、私はそれをやっていて楽しかったです。長い投稿で申し訳ありません。また、私は (メンバーとして) Stack Overflow の初心者であり、ネイティブ スピーカーではありません。