把它变成递归算法的可能方法

本文关键字：方法 递归算法 | 更新日期: 2023-09-27 18:16:34

我试图有一个数组与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);

我注意到有些部分重复。有没有办法把这个写进循环?谢谢。

把它变成递归算法的可能方法

这将根据您的方案返回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,41 -2 3 4- 1,2,3,41 2 -3 4-1 2 -3 41 -2 -3 4-1 -2 -3 41 2 3 -4- 1,2,3， -41 -2 3 -4- 1,2,3， -41 2 -3 -4- 1,2,3， -41 -2 -3 -4- 1,2,3， -4
相关文章：