生成给定 n 次系数为 0 或 1 的所有多项式

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]

对于 n=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
}

生成给定 n 次系数为 0 或 1 的所有多项式

Generate all polynomials with coefficients 0 or 1 given degree n

c#

cryptography

algebra

polynomials

abstract-algebra