次の字句の「置換」アルゴリズム

Question

私は24の一般化バージョンを解決するプログラムを書いた（興味がある人はlink）。つまり、nの数値が与えられた場合、ターゲット番号を計算するようにバイナリ演算を実行する方法があります。

は、これを行うために、私は'v'値のためのプレースホルダであると'o'を操作するためのプレースホルダである'v'又は'o'、のいずれかからなるchar配列として可能な表現を見ました。 nの値がある場合、操作はn-1である必要があります。

どのようにプログラムが現在動作しているのかは、{'o','o',...,'v',v'...}のすべての順列を辞書順にチェックし、接頭辞の式が有効かどうかを調べます。たとえば、ときn = 4、以下の式が有効であると考えています
{‘o’, ‘v’, ‘o’, ‘v’, ‘o’, ‘v’, ‘v’}

次の式

{‘o’,’o’,’o’,’v’,’v’,’v’,’v’}が有効ではありません。

{‘v’,’o’,’v’,’o’,’o’,’v’,’v’}

{‘o’,’o’,’v’,’v’,’v’,’o’,’v’}

私の質問はありませんです効率的なアルゴリズムが存在します何らかの並べ替えで有効な次の順列？目的は、式がすべての置換に対して有効かどうかを確認する必要をなくすことです。

さらに、このようなアルゴリズムが存在する場合、有効な順列をkで計算する時間が存在しますか？私はこれまで

私は、唯一0<=i<2n-1（サブアレーがiから始まる各A[i:2n-1)

ため

number of operations < number of valuesかの場合は、長さ2n-1のプレフィックス表現Aが有効であると考えられるという仮説を立ててい何

終了時（非包含的）で2n-1）

さらに、tha正確に(1/n)C(2n-2,n-1)の有効な順列があり、C(n,k)がn choose kであることを意味します。

Answer 1

ovパターンを生成する方法は次のとおりです。以下のコードの背後にある詳細は、Knuth Volume 4Aにあります（少なくとも、私が練習の1つをしているかもしれません）。既存の並べ替え機構を使用して、パターンを変更する前に値を並べ替えることができます。

コード

#include <cstdio> 

namespace { 
void FirstTree(int f[], int n) { 
    for (int i = n; i >= 0; i--) f[i] = 2 * i + 1; 
} 

bool NextTree(int f[], int n) { 
    int i = 0; 
    while (f[i] + 1 == f[i + 1]) i++; 
    f[i]++; 
    FirstTree(f, i - 1); 
    return i + 1 < n; 
} 

void PrintTree(int f[], int n) { 
    int i = 0; 
    for (int j = 0; j < 2 * n; j++) { 
    if (j == f[i]) { 
     std::putchar('v'); 
     i++; 
    } else { 
     std::putchar('o'); 
    } 
    } 
    std::putchar('v'); 
    std::putchar('\n'); 
} 
} 

int main() { 
    constexpr int kN = 4; 
    int f[1 + kN]; 
    FirstTree(f, kN); 
    do { 
    PrintTree(f, kN); 
    } while (NextTree(f, kN)); 
} 

があり、k番目の木を取得する方法がありますが、時間はO（n）ではなくO（1）よりも出力

ovovovovv 
oovvovovv 
ovoovvovv 
oovovvovv 
ooovvvovv 
ovovoovvv 
oovvoovvv 
ovoovovvv 
oovovovvv 
ooovvovvv 
ovooovvvv 
oovoovvvv 
ooovovvvv 
oooovvvvv 

を生成します。魔法の言葉は​​です。