Generating polynomials in order of largest degree

Question

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 all 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.

see http://stackoverflow.com/questions/127704/algorithm-to-return-all-combinations-of-k-elements-from-n — Alexander Malakhov, Jan 28 '11 at 02:20

score 2 · Answer 1 · edited May 23 '17 at 12:01

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?

Null Set · Answer 2 · 2011-01-28T03:50:32.887

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

Thanks, this was very helpful. I used a similar idea for my version, but i'm having some trouble storing the data. Similar to you outputting the terms, I want to store each term in another array, so I want a double array containing all terms, each term being another array containing each variable. I'm having alot of trouble doing this because of C's pointers, as i'm reusing the same array, yet the function is recursive, so I have to reuse. Can't figure out a simple way around this. — john, Jan 28 '11 at 18:51
@john Just copy the current contents of the array into an element of an int** instead of calling output. If you don't like global variables, have pick_more return the number of times it has outputted so far, and pass around the int**. — Null Set, Jan 28 '11 at 19:02

score 0 · Answer 3 · answered Jan 28 '11 at 02:17

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.

Generating polynomials in order of largest degree

3 Answers3