我得到了一個n長度字串，我需要在所有n長度字串的字母順序中找到它的排名。例如，假設我已經被給定了，
"ABC"那么n=4排序將是這樣{ABCD, ABCE, ABCF ....}的（考慮到我們從 0 開始）。同樣，因為它將是 1。現在，我如何找到 的等級？"ABCD"0"ABCE""YTZ"
uj5u.com熱心網友回復：
Craig Estey 已經想出了一個很好的答案，但我想我會添加到他的排列示例中。如果您想找到一個 n 長度的單詞按字母順序排列的位置，您不必增加以 26 為基數的數字。
這是一些代碼，可以找到 n 長度單詞所在的正確索引：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
/* Convert base 26 to base 10
* Base 26 is represented here as A (0), B (1) ... Z (25)
*/
unsigned ts_to_ten(char *buf, size_t len)
{
unsigned ret = 0;
for (size_t i = 0; i < len; i ) {
ret *= 26;
ret = (buf[i] - 'a');
}
return ret;
}
int main(int argc, char **argv)
{
if (argc != 3) {
fprintf(stderr, "fatal: requires 3 arguments.\n");
exit(EXIT_FAILURE);
}
char *start_text = argv[1];
char *end_text = argv[2];
size_t n;
assert((n = strlen(start_text)) == strlen(end_text));
unsigned start = ts_to_ten(start_text, n);
unsigned end = ts_to_ten(end_text, n);
printf("%u\n", end - start);
}
這個程式接受起始詞和結束詞。起始詞是被認為是第一次迭代的詞（或 0），或在問題的情況下為“abc”。根據問題，結束詞將是您想要獲得迭代的詞或“zxy”。
因此，如果將兩個單詞都轉換為數字并從結尾減去開頭，您將按字母順序獲得結尾單詞與開頭單詞之間的距離。
uj5u.com熱心網友回復：
好的，正如我上面提到的，這是一個“列印所有數字寬的以 26 為基數的n數字”問題。
雖然我們可以使用字串（例如ABC,DEF等），但 [IMO] 更容易轉換為以 26 為基數的數字。
您希望號碼中的數字是唯一的。也就是說，數字的組合而不是排列。
排列實際上更容易，所以讓我們從那個開始......
這是一個對所有可能的排列進行暴力生成的程式。它被[大量]注釋：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define sysfault(_fmt...) \
do { \
printf(_fmt); \
exit(1); \
} while (0)
int ndig; // number of digits in string
// the alphabet
#define ALFMAX 26
const char *alf = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
int opt_v; // verbose mode
// diginc -- increment the base 26 number (ndig digits wide)
// RETURNS: carry out
int
diginc(char *digits)
// digits -- base 26 number (ndig digits wide)
{
int cout = 0;
for (int idx = ndig - 1; idx >= 0; --idx) {
int curdig = digits[idx];
curdig = 1;
// did we overflow/wrap the digit?
cout = (curdig >= ALFMAX);
// no -- store new number and exit
if (! cout) {
digits[idx] = curdig;
break;
}
// wrap digit back to zero
digits[idx] = 0;
}
return cout;
}
// digdecode -- printable string (A-Z) to base 26 number (0-25)
void
digdecode(char *digits,const char *str)
// digits -- base 26 number (ndig digits wide)
// str -- string (A-Z)
{
for (int idx = 0; idx < ndig; idx)
digits[idx] = str[idx] - 'A';
}
// digprint -- convert base 26 number to printable form (e.g. A-Z)
// RETURNS: pointer to string
char *
digprint(const char *digits)
// digits -- base 26 number (ndig digits wide)
{
int idx;
static char str[1000];
for (idx = 0; idx < ndig; idx)
str[idx] = digits[idx] 'A';
str[idx] = 0;
return str;
}
// digmatch -- compare two base 26 numbers for equality
// RETURNS: 1=match, 0=mismatch
int
digmatch(const char *diglhs,const char *digrhs)
// diglhs -- base 26 number (ndig digits wide)
// digrhs -- base 26 number (ndig digits wide)
{
int match = 0;
for (int idx = 0; idx < ndig; idx) {
match = (diglhs[idx] == digrhs[idx]);
if (! match)
break;
}
return match;
}
int
main(int argc,char **argv)
{
--argc;
argv;
setlinebuf(stdout);
// get options
for (; argc > 0; --argc, argv) {
char *cp = *argv;
if (*cp != '-')
break;
cp = 2;
switch (cp[-1]) {
case 'v':
opt_v = ! opt_v;
break;
}
}
// candidate string (e.g. ABD or ZYX)
const char *str;
ndig = -1;
switch (argc) {
case 2:
ndig = atoi(argv[1]);
// fall through
case 1:
str = argv[0];
break;
default:
sysfault("usage: <str> [n]\n");
break;
}
// number of digits in string
if (ndig < 0)
ndig = strlen(str);
printf("ndig=%d str='%s'\n",ndig,str);
// convert string to base 26 digit vector
char expdig[ndig];
digdecode(expdig,str);
// sequence index
int seqidx = 0;
// current base 26 number
char curdig[ndig];
// initialize to all zeros
for (int idx = 0; idx < ndig; idx)
curdig[idx] = 0;
while (1) {
// does the current digit vect match the expected/desired vector?
int match = digmatch(curdig,expdig);
// yes [or verbose mode] -- print the entry
if (match || opt_v) {
printf("d: %s",seqidx,digprint(curdig));
if (match)
printf(" MATCH");
printf("\n");
}
// increment the base 26 number
if (diginc(curdig))
break;
seqidx;
}
return 0;
}
這是輸出ABD：
ndig=3 str='ABD'
29: ABD MATCH
這是輸出ZYX：
ndig=3 str='ZYX'
17547: ZYX MATCH
請注意，盡管組合學大師可能有更好/更快的演算法，但我們可以通過計算頻率表并拒絕任何具有重復數字的數字來獲得組合。因此，這是對前面示例的輕微擴展：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define sysfault(_fmt...) \
do { \
printf(_fmt); \
exit(1); \
} while (0)
int ndig; // number of digits in string
// the alphabet
#define ALFMAX 26
const char *alf = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
int opt_u; // unique (combination) mode
int opt_v; // verbose mode
// freqtab -- create frequency table
// RETURNS: 1=duplicate detected
int
freqtab(const char *digits,int *freq)
{
int dupflg = 0;
for (int idx = 0; idx < ndig; idx) {
int curdig = digits[idx];
dupflg = freq[curdig];
if (dupflg)
break;
freq[curdig] = 1;
}
return dupflg;
}
// reject -- reject number if digits are duplicated
// RETURNS: 1=reject/dup, 0=unique
int
reject(const char *digits,int *freq)
{
if (freq == NULL) {
freq = alloca(sizeof(int) * ALFMAX);
for (int idx = 0; idx < ALFMAX; idx)
freq[idx] = 0;
}
// create frequency table
int dupflg = freqtab(digits,freq);
return dupflg;
}
// diginc -- increment the base 26 number (ndig digits wide)
// RETURNS: carry out
int
diginc(char *digits)
// digits -- base 26 number (ndig digits wide)
{
int cout = 0;
for (int idx = ndig - 1; idx >= 0; --idx) {
int curdig = digits[idx];
curdig = 1;
// did we overflow/wrap the digit?
cout = (curdig >= ALFMAX);
// no -- store new number and exit
if (! cout) {
digits[idx] = curdig;
break;
}
// wrap digit back to zero
digits[idx] = 0;
}
return cout;
}
// digdecode -- printable string (A-Z) to base 26 number (0-25)
void
digdecode(char *digits,const char *str)
// digits -- base 26 number (ndig digits wide)
// str -- string (A-Z)
{
for (int idx = 0; idx < ndig; idx)
digits[idx] = str[idx] - 'A';
}
// digprint -- convert base 26 number to printable form (e.g. A-Z)
// RETURNS: pointer to string
char *
digprint(const char *digits)
// digits -- base 26 number (ndig digits wide)
{
int idx;
static char str[1000];
for (idx = 0; idx < ndig; idx)
str[idx] = digits[idx] 'A';
str[idx] = 0;
return str;
}
// digmatch -- compare two base 26 numbers for equality
// RETURNS: 1=match, 0=mismatch
int
digmatch(const char *diglhs,const char *digrhs)
// diglhs -- base 26 number (ndig digits wide)
// digrhs -- base 26 number (ndig digits wide)
{
int match = 0;
for (int idx = 0; idx < ndig; idx) {
match = (diglhs[idx] == digrhs[idx]);
if (! match)
break;
}
return match;
}
int
main(int argc,char **argv)
{
--argc;
argv;
setlinebuf(stdout);
// get options
for (; argc > 0; --argc, argv) {
char *cp = *argv;
if (*cp != '-')
break;
cp = 2;
switch (cp[-1]) {
case 'u':
opt_u = (*cp != 0) ? atoi(cp) : 1;
break;
case 'v':
opt_v = (*cp != 0) ? atoi(cp) : 1;
break;
}
}
// candidate string (e.g. ABD or ZYX)
const char *str;
ndig = -1;
switch (argc) {
case 2:
ndig = atoi(argv[1]);
// fall through
case 1:
str = argv[0];
break;
default:
sysfault("usage: <str> [n]\n");
break;
}
// number of digits in string
if (ndig < 0)
ndig = strlen(str);
printf("ndig=%d str='%s'\n",ndig,str);
// convert string to base 26 digit vector
char expdig[ndig];
digdecode(expdig,str);
// sequence index
int seqidx = 0;
// current base 26 number
char curdig[ndig];
// initialize to all zeros
for (int idx = 0; idx < ndig; idx)
curdig[idx] = 0;
int rejflg = 0;
int match = 0;
while (1) {
if (opt_u)
rejflg = reject(curdig,NULL);
// does the current digit vect match the expected/desired vector?
if (rejflg)
match = 0;
else
match = digmatch(curdig,expdig);
// yes [or verbose mode] -- print the entry
do {
// don't print rejections
if (opt_v < 2) {
if (rejflg)
break;
}
// don't print unless we have a match or using verbose mode
if (! (match || opt_v))
break;
printf("d: %s",seqidx,digprint(curdig));
if (match)
printf(" MATCH");
if (rejflg)
printf(" REJECT");
printf("\n");
} while (0);
// increment the base 26 number
if (diginc(curdig))
break;
// increment sequence index if (unique)
seqidx = (! rejflg) || (opt_v >= 2);
}
return 0;
}
這是輸出-u ABD：
ndig=3 str='ABD'
1: ABD MATCH
這是輸出-u ZYX：
ndig=3 str='ZYX'
15599: ZYX MATCH
請注意，上面的效率有點低。這是因為頻率表在每次迭代時都會從頭開始重新計算。
請注意，freqtab并reject采取額外的freq論點。那是對未來的規劃。
如果我們傳遞一個實際的陣列，對函式進行一些修改并添加兩個額外的函式，我們可以快速調整頻率表，而無需每次都從頭開始創建它。
更新：
這看起來很整潔！只是幾個問題，所以正如你所說，它有點低效但是，如果 ndig 超過 5，該程式似乎可以作業。
是的，它會起作用，但 [正如我所說的] 它會很慢。我在下面撰寫了更快的版本。
現在，我知道一些 C，但不能完全理解你是如何實作它的，如果這是預期的行為，我的錯 - only_ranch
這里有很多東西要解開。我已經對來源進行了大量注釋[評論]。但是，仍然可能需要一些時間來消化。
如果一個人不熟悉 C 編碼，則尤其如此。語法和含義的一些基本結構（例如if, while,for等）可能 [尚未] 清楚 [一目了然]。
這可能需要一些額外的研究。if（例如）您可能需要更長的時間（例如一兩分鐘）才能得到它，而不是查看一個宣告并“立即”理解它。您可能需要檢查幾次。
然后是演算法本身。同樣，可能需要反復幾次才能理解事物。
有時鉛筆和紙在這里可以成為你最好的朋友......
這在剛開始時很正常。
在您擁有“啊哈！”之前，這似乎很困難/難以處理。片刻。然后，理解將“涌入”。
這就是我剛學習編碼時的感覺。
這就是為什么我從更簡單的排列版本（具有重復字符）開始。然后，執行組合的第二個版本（其中數字是唯一的）。
有一句古老的編程格言 [來自 https://en.wikipedia.org/wiki/The_Elements_of_Programming_Style]：在讓它變得更快之前先做好它。
以下是具有“更智能”頻率表計算的版本。我不得不：
struct為頻率表創建一個- 更改表創建函式（從 重命名
freqtab為ftabnew）。 - 添加兩個功能：
ftabadd和ftabsub進行增量更改。 - 根據需要修改
diginc呼叫ftabadd/ftabsub
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#define sysfault(_fmt...) \
do { \
printf(_fmt); \
exit(1); \
} while (0)
int ndig; // number of digits in string
// the alphabet
#define ALFMAX 26
int opt_u; // unique (combination) mode
int opt_v; // verbose mode
// frequency table
typedef struct {
char ftab_duptot; // total number of dup _cells_ in ftab_freq
char ftab_freq[ALFMAX]; // frequency counts
} ftab_t;
// ftabadd -- add to frequency table
// RETURNS: 1=duplicate detected
int
ftabadd(int curdig,ftab_t *ftab)
// curdig -- digit to add/remove from table
// ftab -- pointer to frequency table
// inc -- 1=increment, -1=decrement
{
int cntold = ftab->ftab_freq[curdig];
// bump up the bucket count
ftab->ftab_freq[curdig] = cntold 1;
// this bucket just became a dup
if (cntold == 1)
ftab->ftab_duptot = 1;
return ftab->ftab_duptot;
}
// ftabsub -- subtract from frequency table
// RETURNS: 1=duplicate detected
int
ftabsub(int curdig,ftab_t *ftab)
// curdig -- digit to add/remove from table
// ftab -- pointer to frequency table
// inc -- 1=increment, -1=decrement
{
int cntold = ftab->ftab_freq[curdig];
// bump up the bucket count
ftab->ftab_freq[curdig] = cntold - 1;
// this bucket just became unique [again]
if (cntold == 2)
ftab->ftab_duptot -= 1;
return ftab->ftab_duptot;
}
// ftabnew -- create frequency table
// RETURNS: 1=duplicate detected
int
ftabnew(const char *digits,ftab_t *ftab)
{
if (ftab == NULL)
ftab = alloca(sizeof(*ftab));
// zero out the counts
ftab->ftab_duptot = 0;
for (int idx = 0; idx < ALFMAX; idx)
ftab->ftab_freq[idx] = 0;
for (int idx = 0; idx < ndig; idx) {
int curdig = digits[idx];
ftabadd(curdig,ftab);
}
return ftab->ftab_duptot;
}
// diginc -- increment the base 26 number (ndig digits wide)
// RETURNS: carry out
int
diginc(char *digits,ftab_t *ftab)
// digits -- base 26 number (ndig digits wide)
{
int cout = 0;
for (int idx = ndig - 1; idx >= 0; --idx) {
int digold = digits[idx];
// remove value from frequency table
ftabsub(digold,ftab);
// get new digit value
int dignew = digold 1;
// did we overflow/wrap the digit?
cout = (dignew >= ALFMAX);
// no -- store new number and exit
if (! cout) {
digits[idx] = dignew;
ftabadd(dignew,ftab);
break;
}
// wrap digit back to zero
dignew = 0;
digits[idx] = dignew;
ftabadd(dignew,ftab);
}
return cout;
}
// digdecode -- printable string (A-Z) to base 26 number (0-25)
void
digdecode(char *digits,const char *str)
// digits -- base 26 number (ndig digits wide)
// str -- string (A-Z)
{
for (int idx = 0; idx < ndig; idx)
digits[idx] = toupper(str[idx]) - 'A';
}
// digprint -- convert base 26 number to printable form (e.g. A-Z)
// RETURNS: pointer to string
char *
digprint(const char *digits)
// digits -- base 26 number (ndig digits wide)
{
int idx;
static char str[1000];
for (idx = 0; idx < ndig; idx)
str[idx] = digits[idx] 'A';
str[idx] = 0;
return str;
}
// digmatch -- compare two base 26 numbers for equality
// RETURNS: 1=match, 0=mismatch
int
digmatch(const char *diglhs,const char *digrhs)
// diglhs -- base 26 number (ndig digits wide)
// digrhs -- base 26 number (ndig digits wide)
{
int match = 0;
for (int idx = 0; idx < ndig; idx) {
match = (diglhs[idx] == digrhs[idx]);
if (! match)
break;
}
return match;
}
int
main(int argc,char **argv)
{
--argc;
argv;
setlinebuf(stdout);
// get options
for (; argc > 0; --argc, argv) {
char *cp = *argv;
if (*cp != '-')
break;
cp = 2;
switch (cp[-1]) {
case 'u':
opt_u = (*cp != 0) ? atoi(cp) : 1;
break;
case 'v':
opt_v = (*cp != 0) ? atoi(cp) : 1;
break;
}
}
// candidate string (e.g. ABD or ZYX)
const char *str;
ndig = -1;
switch (argc) {
case 2:
ndig = atoi(argv[1]);
// fall through
case 1:
str = argv[0];
break;
default:
sysfault("usage: <str> [n]\n");
break;
}
// number of digits in string
if (ndig < 0)
ndig = strlen(str);
printf("ndig=%d str='%s'\n",ndig,str);
// convert string to base 26 digit vector
char expdig[ndig];
digdecode(expdig,str);
// check expected string for dups
if (ftabnew(expdig,NULL))
sysfault("main: str has duplicate chars\n");
// sequence index
int seqidx = 0;
// current base 26 number
char curdig[ndig];
// initialize to all zeros
for (int idx = 0; idx < ndig; idx)
curdig[idx] = 0;
// create frequency table
// NOTE: we _will_ start with dups
ftab_t *ftab = alloca(sizeof(*ftab));
ftabnew(curdig,ftab);
int rejflg = 0;
int match = 0;
while (1) {
if (opt_u)
rejflg = ftab->ftab_duptot;
// does the current digit vect match the expected/desired vector?
if (rejflg)
match = 0;
else
match = digmatch(curdig,expdig);
// yes [or verbose mode] -- print the entry
do {
// don't print rejections
if (opt_v < 2) {
if (rejflg)
break;
}
// don't print unless we have a match or using verbose mode
if (! (match || opt_v))
break;
printf("d: %s",seqidx,digprint(curdig));
if (match)
printf(" MATCH");
if (rejflg)
printf(" REJECT");
printf("\n");
} while (0);
// increment the base 26 number
if (diginc(curdig,ftab))
break;
// increment sequence index if (unique)
seqidx = (! rejflg) || (opt_v >= 2);
}
return 0;
}
uj5u.com熱心網友回復：
組合數學問題通常最終會處理大量數字，而涉及計陣列合物件的問題的解決方案很少涉及列舉每個可能的物件并隨時計數。更不用說列舉可能物件的超集，并測驗每個物件是否符合條件。像這樣的蠻力解決方案可能更容易提出，并且它們適用于非常小的問題，但是當您將問題規模擴大一點時，您很快就會發現自己的資源不足。
例如，我用優化級別 3 編譯了這個問題的另一個答案的解決方案，并慢慢增加了要索引的字串的大小：
| n | 細繩 | 數數 | 用戶時間（版本 1） | 用戶時間（版本 2） |
|---|---|---|---|---|
| 3 | ZYX | 15599 | 0m0.003s | 0m0.003s |
| 4 | ZYXW | 358799 | 0m0.021s | 0m0.015s |
| 5 | ZYXWV | 7893599 | 0m0.188s | 0m0.068s |
| 6 | ZYXWVU | 165765599 | 0m4.973s | 0m1.630s |
| 7 | ZYXWVUT | 3315311999 | 2m13.501s | 0m41.631s |
（注意：為了避免上次呼叫中的算術溢位，我將一個變數從 更改為 。int僅保證表示最大為 32767 的整數，因此在組合數學中很少有用。）unsigned long longint
因此，如果您想解決中等規模的問題，您需要一個計算索引而不是計數的解決方案。在這種情況下，有一個相當簡單的計算，它是字串長度的二次方（即 O(n2)）。這通常不被認為是一個很大的時間復雜度，但它肯定足以擴展這個問題的解決方案范圍，至少到你需要一個 bignum 來表示計數的地步。n=15是在沒有 bignum 支持的情況下可能的最大值，下面的代碼在不到一毫秒的時間內計算出該長度的索引。
它從一個相當直接的觀察開始，如果你有一些包含t個不同字符的集合 Σ（可能是大寫字母集合的一個子集），你可以用這些字符中的n 個組成的不同字串的數量是序列t , t -1, t -2, ...中的前n項。那是因為序列中第一個字符有t種可能性，然后第二個字符有t -1 種可能性，因為選擇的第一個字符不能重復使用，然后t第三個字符的可能性為 -2，因為選擇的前兩個字符不能重復使用，依此類推，直到你有n 個字符。（如果n = t，則計算結果為t！，這是t個字符的排列數。但前n項相乘適用于n < t的任何值。（對于n=0，我們使用空序列的乘積為 1 的約定。）所以如果我們只有集合 { A, J, Q, W } 并且我們想知道兩個不同字符的序列可能有多少個，我們計算 4*3=12。很容易看出這是正確的，因為我們可以只列出可能的對：四個字符中的每個字符都有三對。
但是我們想知道某個特定字母序列的索引是什么。將該序列稱為s，我們再次假設我們有一個包含t個可用字符的集合 Σ，并且??序列s的長度為n。（我們要求s中的所有字符都存在于 Σ 中。）那么問題是，有多少可能的序列（按字典順序）小于s。我們可以通過添加：
所有以 Σ 中的一個小于s的第一個字母的字母開頭的序列，以及
如果n大于 1，則所有以s的第一個字母開頭并以從 Σ 中選擇的n -1 個不同字符繼續的序列，但不包括s的第一個字母。（如果n為 1，則沒有要添加的序列。）
請注意，該總和的第一部分只是較小字母的數量（我們必須計算）乘以來自大小為t -1的字母表中長度為n -1 的無限制序列的數量，我們已經知道如何做到這一點。此外，可以使用相同的程序計算該總和的第二部分，使用更小的字符集和更短的序列長度。所以我們可以很容易地撰寫一個遞回函式來完成這個計算，但是以動態編程風格撰寫它會更有效，從頭開始作業。也就是說，我們計算每個長度的后綴數量（按字典順序）小于s的相應后綴。對于每個后綴長度，我們使用不包括初始字符的字符集s到那個后綴。
例如，讓我們計算BED使用字母組成的序列的索引ABCDE。BED我們從（后綴）的末尾開始D，計算：
使用字母表
ACD和后綴D，長度為 1 的序列數以小于 的字母開頭D。即2，字母表中小于 的字母數D，因為單個字母是長度為 1 的序列。使用字母表
ACDE和后綴ED，長度為 2 的序列數以小于 的字母開頭E。對于三個這樣的字母（B不在字母表中）中的每一個，我們需要從大小為 3 的字母表中長度為 1 的連續序列的數量（ACDE減去我們為開始選擇的符號）。所以這是9。使用全字母表
ABCDE和全后綴BED，長度為三的序列的數量小于一個字母開頭B。有一個這樣的字母，并且有 4×3 連續序列，總共12 個。
所以我們計算的索引BED為 2 9 12 = 23。（這可以通過寫出 60 個可能的長度為 3 的序列來驗證。但如果你手頭有 Python，你也可以快速檢查一下：
>>> sum(c < tuple('BED') for c in permutations('ABCDE', 3))
23
該計算中令人討厭的部分是在每個步驟中計算出乘數：當前字母表中有多少個字符少于第一個后綴字符（即除前綴中的字符之外的整個字母表）。下面的代碼通過掃描整個前綴并計算少于第一個后綴字符的字符數來做到這一點。這就是導致二次時間復雜度的原因，因為我們反復掃描序列的初始部分。
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/* Define the alphabet, which must be a set of contiguous letters. */
#define ALPH_MIN 'A'
#define ALPH_MAX 'Z'
#define ALPH_COUNT (ALPH_MAX - ALPH_MIN 1)
/* This function is called exactly once, to verify that the
* provided string only contains letters in the alphabet, and
* that it contains no repeated letters. The repeat check depends
* on ALPH_COUNT being no greater than the number of bits in a
* long (which is at least 32); it would need to be fixed for
* larger alphabets.
*/
bool validate(const char* s) {
unsigned long seen = 0;
for (; *s; s) {
if (*s < ALPH_MIN) return false;
if (*s > ALPH_MAX) return false;
unsigned long flag = 1UL << (*s - ALPH_MIN);
if (seen & flag) return false;
seen |= flag;
}
return true;
}
/* Assumes that validate(s) returns true */
unsigned long long perm_index(const char* s) {
/* The "rising factorial" (see Wikipedia). */
unsigned long long rising_fact = 1;
unsigned long long cumulative_index = 0;
size_t len = strlen(s);
while (len > 0) {
unsigned c = s[--len];
unsigned avail = c - ALPH_MIN;
for (unsigned i = 0; i < len; i)
if (s[i] < c) --avail;
cumulative_index = avail * rising_fact;
rising_fact *= ALPH_COUNT - len;
}
return cumulative_index;
}
int main(int argc, char* argv[]) {
for (int i = 1; i < argc; i) {
const char* s = argv[i];
if (!validate(s))
printf("Invalid string: %s\n", s);
else
printf("s='%s', n=%zu, i=%llu\n", s, strlen(s), perm_index(s));
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/520660.html
標籤：C递归辞典词典字典顺序
上一篇：遞回地展平嵌套物件的地圖