それは、組み合わせと順列の技術によって解決することができます。
F(N)=ランク
最初に、Nを表すために必要なビット数を見つけます。2進表現では、数値は次のように構成できます。
N = cn 2^n + .... + c3 2^2 + c2 2^1 + c1 2^0
さて、n
上記の方程式で(または数値の2進表現のビット数)を見つけるために、それがであると仮定することができますfloor(log2(N)) + 1
。たとえば、任意の数を考えてみましょう。たとえば、118
floor(log2(118))+ 1=7ビットで表すことができます。
n = floor(log2(118)) + 1;
上記の式はのみO(1)
です。ここで、数値の2進表現に1がいくつあるかを見つける必要があります。この仕事をするための擬似コードを考えてみましょう:
function count1(int N) {
int c = 0;
int N' = N;
while(N' > 0) {
N' -= 2^(floor(log2(N')));
c++;
}
}
上記の擬似コードはO(logN)
です。上記の擬似コードをテストするためにMATLABで小さなスクリプトを作成しました。結果は次のとおりです。
count1(6) = 2
count1(3) = 2
count1(118) = 5
これで、ビット数とそれらのビットの1の数がわかりました。これで、単純な組み合わせと順列を適用して、数のランクを見つけることができます。n
まず、は、数値を表すために必要なビット数であり、数値のビット表現では1の数であると仮定しますc
。したがって、ランクは次のように与えられます。
r = n ! / c ! * (n - c) !
編集:DSMによって提案されたように、正しいランクを見つけるためにロジックを修正しました。アイデアは、順列からすべての不要な数を削除することです。したがって、このコードを追加しました:
for i = N + 1 : 2^n - 1
if count(i) == c
r = r - 1;
end
end
上記の方法を使用して数値のランクを見つけるMATLAbスクリプトを作成しました。
function r = rankN(N)
n = floor(log2(N)) + 1;
c = count(N);
r = factorial(n) / (factorial(c) * factorial(n - c));
% rejecting all the numbers may have included in the permutations
% but are unnecessary.
for i = N + 1 : 2^n - 1
if count(i) == c
r = r - 1;
end
end
function c = count(n)
c = 0;
N = n;
while N > 0
N = N - 2^(floor(log2(N)));
c = c + 1;
end
そして、上記のalogrithmはO(1) + O(logN) + O(1) = O(logN)
です。出力は次のとおりです。
>> rankN(3)
ans =
1
>> rankN(4)
ans =
3
>> rankN(7)
ans =
1
>> rankN(118)
ans =
18
>> rankN(6)
ans =
3
注:のランクは、上記のメソッドが未定義であるため失敗するため、0
常にです。1
0
log2(0)