Using std :: sort and std :: next_permutation

Question

I have the following code that I wrote and works fine. It’s just hard for me to understand why this works. In particular, why do we have to sort the array first to use std :: next_permutation, can it start with any configuration?

And the part that bothers me the most is that I don’t understand why we should write to sort (sides, sides + 3) and next_permutation (sides, sides + 3), why “+3”! because i have three elements in an array? What if I used an arbitrary number of elements?

bool valid(int sides[], ofstream &outfile) { int i = 0; for(; i < 3; i++) { if(sides[i] <= 0) { outfile << "This is not a valid triangle because it\n " << "contains negative sides or contains a\n" << "side length of 0\n\n"; return false; } } do{ std::sort(sides,sides+3); if(sides[0] + sides[1] > sides[2]) ; else{ outfile << "This is not a valid triangle because " << sides[0] << " + " << sides[1] << " is not greater than " << sides[2]; return false; } }while(std::next_permutation(sides,sides+3)); return true; } 

Answer 1

Euclidean geometry tells us that:
the sum of the two sides is always larger than the remaining side

Take triangle ABC.
AB = 3
BC = 5
AC = 4

std :: sort sorts the parties in ascending order. So first the array will contain shorter sides.

after sorting
side [0] = AB = 3
side [1] = AC = 4
side [2] = BC = 5

std :: next_permutation returns the next possible combination of sides. For instance:

AC = 3
BC = 5
AB = 4

Quick example:

 #include <iostream> // std::cout #include <algorithm> // std::next_permutation, std::sort int main () { int myints[] = {1,2,3}; std::sort (myints,myints+3); std::cout << "The 3! possible permutations with 3 elements:\n"; while ( std::next_permutation(myints,myints+3) ) { std::cout << myints[0] << ' ' << myints[1]; std::cout << ' ' << myints[2] << '\n'; } std::cout << "After loop: " << myints[0] << ' '; std::cout << myints[1] << ' ' << myints[2] << '\n'; return 0; } 

Further reading: http://www.cplusplus.com/reference/algorithm/next_permutation/

Answer 2

documentation std :: next_permutation

The conversion range until the next permutation. Reorders the elements in the range [first, last] to the next lexicographically larger permutation.

therefore, if you do not start sorting, you will not go through all the permutations

So, if you start with

1,2,3

what the last permutation will be

3,2,1

if you start with

3,1,2

only one permutation will be found, not all

Answer 3

Take a look at the results of std::next_permuntation if you don't sort it:

 #include <algorithm> #include <iostream> #include <iterator> #include <string> enum class sort { no, yes }; void show_permutations(std::string s, sort option) { if (sort::yes == option) { std::sort(std::begin(s), std::end(s)); } do { std::cout << s << '\n'; } while (std::next_permutation(std::begin(s), std::end(s))); } int main() { show_permutations("3412", sort::yes); std::cout << "Now without sorting...\n"; show_permutations("3412", sort::no); } 

Examine the output to see if you notice anything interesting:

 1234 1243 1324 1342 1423 1432 2134 2143 2314 2341 2413 2431 3124 3142 3214 3241 3412 3421 4123 4132 4213 4231 4312 4321 Now without sorting... 3412 3421 4123 4132 4213 4231 4312 4321 

A sequence created without sorting is the same as the very end of a sequence created by sorting. What does this mean about the importance of entering an order?

---

What do you think will happen if you put the sort code inside a loop?

 void show_permutations(std::string s, sort option) { do { if (sort::yes == option) { std::sort(std::begin(s), std::end(s)); } std::cout << s << '\n'; } while (std::next_permutation(std::begin(s), std::end(s))); } 

Note that your program sorts the sides of the triangle inside the next_permutation loop, similar to this code, sorting the input line inside the loop.