c# - 使用特定的算法逻辑从数组中获取数组

Question

让，长度为 N

的数组

int[]  iArrN=new int[N]{n1,n2,n3....nN};  
//where 1000>N>0 and n1,n2..nN>0(positive integer)

我想从数组中取出M个元素。

int[] iArrM=new int[M]{m1,m2...mM};  
//where N>M>0 and m1,m2..mM>0(positive integer)

条件iArraM中的数之和必须能被N

整除

这里的例子:

int[] iArrN=new int[5]{1,2,3,4,5}; 
N=5
M=3;

然后我可以得到 iArrN[1]=2+ iArr[2]=3+ iArr[4]=5=>10%5(N)

int[] iArrM=new int[3]{2,3,5};

要记住: N和M可以是任意数，所以我们需要找出N所有可能取值的逻辑算法和 M.

到目前为止我尝试了什么:我从例子开始。

 int[] i=new int[5]{1,2,3,4,5}; 

我正在考虑在这个数组 (iArrN) 中获取与 M 元素的所有可能组合

例如:

M=3

i[0],i[1],i[2]==1,2,3
i[0],i[1],i[3]==1,2,4
i[0],i[1],i[4]==1,2,5
i[0],i[2],i[3]==1,3,4
i[0],i[2],i[4]==1,3,5
i[0],i[3],i[4]==1,4,5
..
..
..
and so on.

得到这个之后我们可以用N检查sum(of the combination)和divisibility。

如何使用循环或其他方式获得此组合。如果您有任何简单且合适的解决方案，请告诉我。

Answer 1

最直接的方法(正如 juharr 在评论中提到的那样)是简单地生成输入集的所有可能子集并过滤以找到满足要求的子集。

生成给定集合 X 的所有子集是一种相当简单的递归算法:

1. 如果 X 为空，则唯一的子集是空集。结束
2. 否则，从X中删除一些元素i并递归生成结果集X'的所有子集
3. X 的子集是 X' 的子集，以及通过将 i 附加到 X' 的子集而生成的集合。结束

这里是完整的实现:

class Program
{
    static void Main(string[] args)
    {
        var input = new[] { 1, 2, 3, 4 };
        var result = GenerateSubsets(input)
            .Where(s => s.Sum() % input.Length == 0)
            .ToArray(); // {1, 3}, {4} and {1, 3, 4};
    }

    static IEnumerable<ICollection<T>> GenerateSubsets<T>(ICollection<T> set)
    {
        // Base case
        if (set.Count == 0)
        {
            yield return new T[0];
            yield break;
        }

        // Generate all subsets
        var i = set.First();
        foreach (var subset in GenerateSubsets(set.Except(new[] { i }).ToArray()))
        {
            yield return subset;
            yield return subset.Concat(new[] { i }).ToArray();
        }
    }
}