将其制作成递归算法的可能方法？

Question

我试图让一个包含 n 个元素的数组像这样排列：

permute(x,y,z)
permute(-x,y,z)
permute(x,-y,z)
permute(-x,-y,z)

这就像二进制递增（如果 - 符号代表 1）。 我试图在代码中做到这一点，并且注意到了这一点：

    list[1] = -list[1];
        perm(list, k, m);
        list[1] = -list[1];
        list[2] = -list[2];
        perm(list, k, m);
        list[1] = -list[1];
        perm(list, k, m);
        list[1] = -list[1];
        list[2] = -list[2];
        list[3] = -list[3];
        perm(list, k, m);
        list[1] = -list[1];
        perm(list, k, m);
        list[1] = -list[1];
        list[2] = -list[2];
        perm(list, k, m);
        list[1] = -list[1];
        perm(list, k, m);
        list[1] = -list[1];
        list[2] = -list[2];
        list[3] = -list[3];
        list[4] = -list[4];
        perm(list, k, m);

我注意到有些部分是重复的。有没有办法将其写入循环？谢谢。

Answer 1

这将根据您的方案返回第 k 个排列：

IEnumerable<int> Perm(IEnumerable<int> source, int k)
{
    return source.Select((x, i) => ((k >> i) & 1) == 1 ? -x : x);
}

示例：

var data = new[] { 1, 2, 3, 4 };

for (int k = 0; k < (1 << data.Length); k++)
{
    Console.WriteLine(string.Join(", ", Perm(data, k)));
}

输出：

1, 2, 3, 4
-1, 2, 3, 4
1, -2, 3, 4
-1, -2, 3, 4
1, 2, -3, 4
-1, 2, -3, 4
1, -2, -3, 4
-1, -2, -3, 4
1, 2, 3, -4
-1, 2, 3, -4
1, -2, 3, -4
-1, -2, 3, -4
1, 2, -3, -4
-1, 2, -3, -4
1, -2, -3, -4
-1, -2, -3, -4