Generating polynomials in order of largest degree

I can't figure out a concise way of doing the following (I am using C):

Given a number of variables, n, and a maximum degree, d, I want to generate the corresponding polynomial.

For example, if n = 4, and d = 3, I would want to generate the following: 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

Each xn is a different variable. The polynomial starts with the largest degree of 3, and goes through al开发者_StackOverflowl of those monomials, then goes through all quadratics, then linears. This should work for any positive n and d.

I can hard code this with a few nested while loops and ints keeping track of each variable, so I can make it work. But I need to generalize, and I can't figure out how to do that, at least not without a gigantic mass of while or for loops.

So, my question is, what's a good way to generate those variable numbers in the proper order, in a very general way? Thanks.

You seem to need a filtered subset of the power set (set of all subsets) of variables, filtered by the degree.

At Rosetta Code there are two C examples to generate the power set. It should be easy to modify it to limit it to subsets of a given order. (I'm assuming that you don't want repeated terms such as x2x4^2.)

For your example the starting set is {x1, x2, x3, x4} and the terms of your polynomial are formed from the subsets of order 3 or less.

This question is similar to How to find all possible subsets of a given array?

You could generate a polynomial term recursively.

Edit: Previous code had many problems. This one works and is tested. pick_more will output all size max_more combinations of start_var variables, in the order you asked. Just call it once for each degree, from d down to 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);
    }
}

Output for 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

If you use C++, you can use STL's next_permutation() to generate all permutations of 3 variables, then 2 variables, and so on.

For each permutation, you can filter out duplciates by only choosing a canonical order of variables. For example: only use monomials with increasing variable index.