The first part of my 'task' was to find all addends (partition) of a number (in my case 365) with all possible permutations of those sequences.
For example: for number 3 we have three possible addend sequences (3) (1;2) (1;1;1) but my method gives (3) (1;2) (2;1) (1;1;1) as I needed.
IEnumerable<int[]> SplitAddends(int n) {
for (int i = 1; i < n; i ) {
var part = SplitAddends(n - i);
foreach (var array in part) {
var newArray = new int[array.Length 1];
newArray[0] = i;
Array.Copy(array, 0, newArray, 1, array.Length);
yield return newArray;
}
}
yield return new []{n};
}
This method gives a result in less than 1 ms and it's correct. The problem is the second part of this task. I need to do some calculations with each element. For example:
void ExampleMethod(int N) {
var partition = SplitAddends(N); // < 1ms execution time
foreach (var variant in partition) { // problematic line
var someResult = 0f;
foreach (var item in variant) {
someResult = SomeEquation(item);
}
SendToCompare(someResult);
}
}
It takes several seconds for numbers like 15-25 (for N=20 partition has 524288 sequences) and it takes hours for numbers like 35-50.
I've already tried things like Parallel.ForEach
, while(partition.MoveNext())
and changing the type of collection. Even partition.Count()
takes years for execution.
I know about one workaround for that. The calculations may be put inside of SplitAppends
method and be executed in a top layer of stack but this way seems tricky.
CodePudding user response:
So I found the problem. The 'yield' doesn't give me any result at the time when the method is called. Only when I'm using the yielding elements. That's why this method is finished in 1 ms and 'foreach' takes so long. And the problem has ~O(2^N) difficulty, that's why we can't use if for N=360.