Генерация полиномов по порядку наибольшей степени

Question

Я не могу найти краткий способ сделать следующее (я использую C):

Учитывая число переменных n и максимальную степень d, я хочу сгенерировать соответствующийполином.

Например, если n = 4 и d = 3, я бы хотел сгенерировать следующее: x4 x3 x2 + x4 x3 x1 + x4 x2 x1 + x3 x2 x1 + x4 x3 + x4 x2+ x4 x1 + x3 x2 + x3 x1 + x2 x1 + x4 + x3 + x2 + x1

Каждый xn - это отдельная переменная.Полином начинается с наибольшей степени 3 и проходит через все эти мономы, затем проходит через все квадратичные, а затем линейные.Это должно работать для любых положительных n и d.

Я могу жестко запрограммировать это с помощью нескольких вложенных циклов while и int, отслеживающих каждую переменную, чтобы я мог заставить ее работать.Но мне нужно обобщить, и я не могу понять, как это сделать, по крайней мере, без гигантской массы циклов while или for.

Итак, мой вопрос, каков хороший способ генерировать эти циклы?переменные числа в правильном порядке, в общем смысле?Спасибо.

Answer 1

Вам, кажется, нужно отфильтрованное подмножество набора мощности (набора всех подмножеств) переменных, отфильтрованных по степени.

В Rosetta Code есть два примера C для генерации блока питания.Должно быть легко изменить его, чтобы ограничить его подмножествами данного порядка.(Я предполагаю, что вам не нужны повторяющиеся термины, такие как x2x4 ^ 2.)

Для вашего примера начальный набор равен {x1, x2, x3, x4} и сформированы члены вашего полиномаиз подмножеств порядка 3 или менее.

Этот вопрос похож на Как найти все возможные подмножества данного массива?

Answer 2

Вы можете сгенерировать полиномиальный термин рекурсивно.

Редактировать: предыдущий код имел много проблем. Этот работает и проверен. pick_more будет output всех размеров max_more комбинаций start_var переменных в указанном вами порядке. Просто назовите его один раз для каждой степени, от d до 1.

#include <stdio.h>
#include <stdlib.h>

void output(int* term, int degree){
    int i;
    for(i=0;i<degree;i++)
        putchar('0'+term[i]);
    putchar(' ');
    fflush(stdout);
}

void pick_more(int *term, int so_far, int max_more, int start_var){
    int i;
    for(i=0; start_var-i >= max_more; i++){
        term[so_far] = start_var-i;
        if(max_more > 1)
            pick_more(term, so_far+1, max_more -1, start_var - i-1);
        else
            output(term, so_far+1);
    }
}

int main(int argc, char** argv){
    int vars, degree;
    sscanf(argv[1], "%d", &vars);
    sscanf(argv[2], "%d", &degree);
    int *term = malloc(sizeof(int)*degree);
    int i;
    for(i=degree;i>0;i--){
        pick_more(term, 0, i, vars);
    }
}

Выход для n = 6, d = 3:

654 653 652 651 643 642 641 632 631 621 543 542 541 532 531 521 432 431 421 321 65 64 63 62 61 54 53 52 51 43 42 41 32 31 21 6 5 4 3 2 1

Answer 3

Если вы используете C ++, вы можете использовать STL next_permutation () для генерации всех перестановок из 3 переменных, затем 2 переменных и т. Д.

Для каждой перестановки вы можете отфильтровывать дубликаты, только выбирая канонический порядок переменных. Например: используйте только одночлены с увеличивающимся индексом переменной.