「bca」という配列が与えられた場合、与えられた順列より辞書的に大きい順列の数を見つける必要があります。
したがって、この例では、cab、cba はより大きな順列です。したがって、答えは 2 になります。
配列の辞書式ランキングを見つけることで問題にアプローチしようとしましたが、発言のための効率的なアルゴリズムを考案することはできません。
正しい方向へのヘルプ/ポインタは大歓迎です!
7872 次
4 に答える
17
順列を見てみましょうdacb。これは、4つの中で辞書式の順序でどこに来るのですか! abcd= ?の 24 個の順列
- 最初の文字を考えてみましょう
d。残りの文字 (acb) の中には、 より小さい文字が 3 つとd、3! = それぞれから始まる 6 つの順列、合計 18 の順列。 - 最初の 2 文字を考えてみましょう
da。残りの文字 ( ) の中には(あるとすれば 2! = 2 の順列があり、各文字にプラスして始まる)cbよりも小さい文字はなく、合計 0 の順列になります。ad - 最初の 3 文字を考えてみましょう
dac。残りの文字 (b) の中に、 よりも小さい文字が 1 つありc、1! = で始まる 1 つの順列dab、合計 1 つの順列。
したがって、合計で よりも小さい順列は 19 個ありdacbます。それを確認しましょう。
>>> from itertools import permutations
>>> list(enumerate(''.join(p) for p in permutations('abcd')))
[(0, 'abcd'), (1, 'abdc'), (2, 'acbd'), (3, 'acdb'),
(4, 'adbc'), (5, 'adcb'), (6, 'bacd'), (7, 'badc'),
(8, 'bcad'), (9, 'bcda'), (10, 'bdac'), (11, 'bdca'),
(12, 'cabd'), (13, 'cadb'), (14, 'cbad'), (15, 'cbda'),
(16, 'cdab'), (17, 'cdba'), (18, 'dabc'), (19, 'dacb'),
(20, 'dbac'), (21, 'dbca'), (22, 'dcab'), (23, 'dcba')]
いいね。だから4つある！− 19 − 1 = より大きい 4 つの順列dacb。
これで、アルゴリズムを作成する方法を一般化する方法が明らかになったはずです。Python での実装は次のとおりです。
from math import factorial
def lexicographic_index(p):
"""
Return the lexicographic index of the permutation `p` among all
permutations of its elements. `p` must be a sequence and all elements
of `p` must be distinct.
>>> lexicographic_index('dacb')
19
>>> from itertools import permutations
>>> all(lexicographic_index(p) == i
... for i, p in enumerate(permutations('abcde')))
True
"""
result = 0
for j in range(len(p)):
k = sum(1 for i in p[j + 1:] if i < p[j])
result += k * factorial(len(p) - j - 1)
return result
def lexicographic_followers(p):
"""
Return the number of permutations of `p` that are greater than `p`
in lexicographic order. `p` must be a sequence and all elements
of `p` must be distinct.
"""
return factorial(len(p)) - lexicographic_index(p) - 1
于 2012-08-27T18:22:06.110 に答える
15
階乗数システムとレーマー コードに基づいてこれを行う非常にクリーンな方法があります。アイデアは、値が発生する順序をエンコードする各可能な順列に数値コードを割り当てることです (レーマー コード)。次に、レーマー コードを、すべての順列のリスト内の順列のインデックスを決定する数値に変換できます (これは、階乗数システムを使用します)。順列のインデックスが与えられると、(n! - 1) を計算し、インデックスを減算して、あと何個の順列があるかを判断できます。
これを行う方法に興味がある場合は、順列からインデックスに、またはその逆にマップできるこのアルゴリズムの実装があります。また、これを行う方法についての講演も行いました。詳細はスライドの後半にあります。
お役に立てれば！
于 2012-08-27T18:21:13.457 に答える
0
バックトラッキング ソリューションは次のとおりです。
プログラムは、指定された文字列のすべてのソリューションを並べ替え、ソリューションのリストと、ここにあるソリューションの数を返します。
例：acbそれが返すため：
c a b
c b a
b a c
b c a
4
コード：
#include <iostream>
#include <stdio>
using namespace std;
int v[100], n, cnt;
char *str;
void init(int k)
{
v[k] = -1;
}
bool solutionReached( int k )
{
if (k == n + 1)
return true;
return false;
}
void printSolution( int k )
{
for (int i = 1; i < k; i++)
{
printf("%c ", str[v[i]]);
}
printf("\n");
cnt++;
}
bool hasSuccesor( int k )
{
if(v[k] < n - 1)
{
v[k]++;
return true;
}
return false;
}
bool isValid( int k )
{
for (int i = 1; i < k; i++)
{
if (v[i] == v[k])
{
return false;
}
}
if (k == n)
{
char *cuv = (char *) malloc(n * sizeof(char));
for (i = 0; i < n; i++)
cuv[i] = str[v[i + 1]];
if (strcmp(cuv, str) > 0)
{
return true;
}
else
return false;
}
return true;
}
void bkt(int k)
{
if(solutionReached(k))
printSolution(k);
else
{
init(k);
while(hasSuccesor(k))
if(isValid(k))
bkt(k + 1);
}
}
int main(int argc, char* argv[])
{
str = "bca";
n = strlen(str);
bkt(1);
printf("%i \n", --cnt);
return 0;
}
于 2012-08-27T18:27:52.343 に答える
-3
単純な python ソリューションは、Python の順列ジェネレーターが、最初に並べ替えられた文字列から辞書順に生成されるという事実に依存しています。
In [68]: from itertools import permutations
In [69]: from math import factorial
In [70]: def lexigreaterperms(perm):
...: return factorial(len(perm)) - 1 - list(permutations(sorted(perm))).index(tuple(perm))
In [71]: lexigreaterperms('bca')
Out[71]: 2
In [72]: lexigreaterperms('dacb')
Out[72]: 4
于 2012-08-27T19:02:41.517 に答える