Генерация всех полиномов с коэффициентами 0 или 1 заданной степени n

Question

Я пытаюсь перечислить в "C#" все возможные полиномы с учетом степени. Есть ли алгоритм для перечисления всех возможных многочленов заданной степени n? Может быть, я не знаю, как точно задать этот вопрос, но это примеры

например:

для n=1

x+1    return [1 1]
x      return [1 0]

для n=2

x^2+x+1  return [1 1 1]
x^2+x    return [1 1 0] 
x^2      return [1 0 0]
x^2+1    return [1 0 1] 

для х =3

x^3           return [1 0 0 0]
x^3+x^2       return [1 1 0 0]
x^3+x         return [1 0 1 0]
x^3+x^2+x     return [1 1 1 0]
x^3+1         return [1 0 0 1]
x^3+x^2+1     return [1 1 0 1]
x^3+x+1       return [1 0 1 1]
x^3+x^2+x+1   return [1 1 1 1]

Любой псевдокод или алгоритм помогут.

Answer 1

Установите самый левый бит, затем сделайте двоичный счетчик на правильных n битах. На самом деле вам нужно n+1 бит, чтобы учесть x^0 (в моей первой попытке я был выключен на 1).

Вы можете создать перечисление следующим образом:

IEnumerable<int[]> GenPolys(int n)
{
    int[] a = new int[n + 1];
    a[0] = 1;
    bool ok = true;
    while (ok)
    {
        yield return a;
        ok = false;
        for (int i = 1; i < a.Length; i++)
        {
            a[i] = 1 - a[i]; // flip the ith bit
            if (a[i] == 1)
            {
                ok = true;
                break;
            }
        }
    }
}

Использование:

foreach (int[] poly in GenPolys(4))
{
    // your code here
}