Следующий лексический алгоритм «перестановки»

Question

Я написал программу, которая решает обобщенную версию 24 (link для любопытных). То есть, учитывая набор номеров n, существует ли способ выполнять на них двоичные операции так, что они вычисляют целевой номер.

Чтобы сделать это, я рассматривал возможные выражения как массив символов, состоящий из любой 'v' или 'o', где 'v' является заполнителем для значения и 'o' является заполнителем для операции. Обратите внимание, что если есть значения n, то должны быть операции n-1.

Как работает программа, она проверяет каждую перестановку {'o','o',...,'v',v'...} в лексикографическом порядке и видит, действительно ли префиксное выражение. Например, когда n = 4 следующие выражения считаются действительными:

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

следующие выражения являются недопустимыми:

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

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

Мой вопрос делает существует эффективный алгоритм для получения следующая перестановка, которая действительна в каком-то порядке? Цель состоит в том, чтобы исключить необходимость проверки правильности выражения для каждой перестановки.

Кроме того, если такой алгоритм существует, существует ли время O(1) для вычисления k-й допустимой перестановки?

То, что я до сих пор

Я предполагаю, что выражение префикс A длины 2n-1 считается действительным, если и только если

number of operations < number of values для каждого A[i:2n-1)

где 0<=i<2n-1 (Подмассив начиная с i и окончание (не включительно) в 2n-1)

Кроме того, tha t означает, что есть точно (1/n)C(2n-2,n-1) действительные перестановки, где C(n,k) is n choose k.

Answer 1

Вот как создать ov-шаблоны. Детали, лежащие в основе кода ниже, находятся в Knuth Volume 4A (или, по крайней мере, упомянуты, я мог бы выполнить одно из упражнений). Вы можете использовать существующую систему перестановок, чтобы переставлять значения каждый раз, прежде чем менять шаблоны.

Код

#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)); 
} 

формирует выходного сигнал

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

Там способ, чтобы получить дерево его, но во время O (N), а не O (1). Волшебные слова: unranking binary trees.