How do i make a slide with last element and some of firsts. You might dont get my question, so i better give u an example: In this array, if i try to find the min sum of 3 numbers {1, 2, 5, 4, 3} it checking this slides: {1, 2, 5}, {2, 5, 1}, {5, 4, 3} and gives me 8 as result. But how do i also check {3, 1, 2},{4, 3 ,1} ? Like if we imagine the array as circle of numbers.
The code that I have now is:
#include <iostream>
#include <algorithm>
int minsum(int arr[], int n, int k)
{
if (n < k)
{
return -1;
}
int sum = 0;
for (int i = 0; i < k; i )
sum = arr[i];
int windowsum = sum;
for (int i = k; i < n; i )
{
windowsum = arr[i] - arr[i - k];
sum = std::min(sum, windowsum);
}
return sum;
}
int main()
{
int arr[] = {1, 2, 5,4, 3};
int k = 3;
int n = sizeof(arr) / sizeof(arr[0]);
std::cout << minsum(arr, n, k) << std::endl;
return 0;
}
CodePudding user response：
Ranges come very handy here. The problem is that many of them, like repeat(n), won't be available in the standard library until C 23. Meanwhile, you can use Eric Niebler's range-v3 library:
- You start from
arr. - The pipe operator,
|, will get one range (e.g. the initialarr, or the view resulting from operating on a range), and pass it as an input to the next algorithm. cycletakes a range and forms an "infinite" view of that range by repeating its elements time and again.sliding(n)takes a range and forms a view that is a range of subranges ofnelements, each starting in consecutive positions of the original range.take(n)takes exactlynelements from a given range.transformtakes a range, applies an operation on each element, and generates a view with the result of each operation.
#include <fmt/core.h>
#include <fmt/ranges.h>
#include <range/v3/all.hpp>
namespace rv3 = ranges::views;
int main() {
int arr[] = { 1, 2, 5, 4, 3 };
int n{ std::size(arr) };
fmt::print("size of arr: {}\n", n);
auto&& threes{ arr
| rv3::cycle // [1, 2, 5, 4, 3, 1, 2, 5...]
| rv3::sliding(3) // [[1, 2, 5], [2, 5, 4], [5, 4, 3], [4, 3, 1], [3, 1, 2]...]
| rv3::take(n) // [[1, 2, 5], [2, 5, 4], [5, 4, 3], [4, 3, 1], [3, 1, 2]]
};
fmt::print("threes: {}\n", threes);
auto&& sums_of_threes{ threes
| rv3::transform([](auto&& v) { return ranges::accumulate(v, 0); })
};
fmt::print("sums of threes: {}\n", sums_of_threes);
auto min_of_sums_of_threes{ *ranges::min_element(sums_of_threes) };
fmt::print("min of sums of threes: {}\n", min_of_sums_of_threes);
}
// Output:
//
// size of arr: 5
// threes: [[1, 2, 5], [2, 5, 4], [5, 4, 3], [4, 3, 1], [3, 1, 2]]
// sums of threes: [8, 11, 12, 8, 6]
// min of sums of threes: 6
I've separated the creation of the threes and the sums_of_threes view just for demoing purposes, but you could create sums_of_threes directly.
CodePudding user response：
Such kind of "flip overs" or "overflows" can be easily handled with modulo division.
If you have for example 5 elements in your array, then allowed indices are 0,1,2,3,4. So, never greater than 4. And this we can achieve with modulo division, in C with the % operator. Please see the following example:
Modulo division
0 % 5 = 0
1 % 5 = 1
2 % 5 = 2
3 % 5 = 3
4 % 5 = 4
5 % 5 = 0
6 % 5 = 1
7 % 5 = 2
8 % 5 = 3
9 % 5 = 4
. . .
With that approach, we can "limit" your indices or make them "flip around". The limited index in below table is simply calculated by using the %operator.
Please see:
Runnning Limited
Index Index
0 1 2 --> 0 1 2
1 2 3 --> 1 2 3
2 3 4 --> 2 3 4
3 4 5 --> 3 4 0
4 5 6 --> 4 0 1
Now it is clear how to calculate indices. We start a normal for loop. The beginning index is 0,1,2,3,4, the end index is 2,3,4,5,6 and corrected with % --> 2,3,4,0,1. Good. This problem is solved.
Next, if we want to find the minimum of something, we define the variable "minimumWindowSum" and compare it with the resulting sum of the current window "sumOfCurrentWindow". If the current value is smaller then the minimum, we will use it for the new minium. The problem is the initial value of "minimumWindowSum". We must initialize it with something very big, so that even the first "sumOfCurrentWindow" is always and guarnateed lower. For this we simply use the maximum possible data type for this variable.
C will help us here with the limits library. And here, especially with the std::numeric_limits. If we need for example the maximum integer value, we can write:
std::numeric_limits<int>::max()
So, now we know the 2 major building blocks for our program.
We can write now:
#include <iostream>
#include <limits>
int minsum(int arr[], int n, int k) {
int minimumWindowSum = std::numeric_limits<int>::max();
if (k < n) {
for (int i = 0; i < n; i) {
int sum = 0;
for (int w = i; w < (i k); w)
sum = arr[w % n];
if (sum < minimumWindowSum)
minimumWindowSum = sum;
}
}
return minimumWindowSum;
}
int main()
{
int arr[] = { 1, 2, 5, 4, 3 };
int k = 3;
int n = sizeof(arr) / sizeof(arr[0]);
std::cout << minsum(arr, n, k) << std::endl;
return 0;
}
But this is still rater "C-Style". In C we do usually not use C-Style arrays for such tasks. A std::array or a std::vector is nearly always the better choice. It has the additional advantage that those containers "know" their size. And with that, you can write a better program.
One example could be:
#include <iostream>
#include <limits>
#include <vector>
// Calculate the minimum sum of a sliding window over a vector
int minSum(const std::vector<int>& data, std::size_t windowLength) {
// Initialize with maximum possible value. Return this in case of error
int minimumWindowSum{ std::numeric_limits<int>::max() };
// Sanity check. Basically not necessary
if (windowLength <= data.size())
// Calculate the sum for each possible sliding window
for (std::size_t index{}; index < data.size(); index) {
// This will hold the sum of the current window
int sumOfCurrentWindow{};
// Sum up vector elements at sliding window indices
for (std::size_t slidingWindowIndex{}; slidingWindowIndex < (index windowLength); slidingWindowIndex)
sumOfCurrentWindow = data[slidingWindowIndex % data.size()];
// Check for a new minimum
if (sumOfCurrentWindow < minimumWindowSum)
minimumWindowSum = sumOfCurrentWindow;
}
// And show result
return minimumWindowSum;
}
int main() {
std::vector data{ 1, 2, 5, 4, 3 };
std::cout << minSum(data, 5) << '\n';
}