Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
Re: ::std::next_permutation( a, b )
51 views
Skip to first unread message
Alf P. Steinbach
Dec 15, 2016, 8:00:43 PM12/15/16
to
On 16.12.2016 00:49, Stefan Ram wrote:
> One can repeatedly call
>
> ::std::next_permutation( a, b )
>
> and eventually it will return »false« when there is no more
> permutation possible.
>
> But how can it now this? Doesn't it have to store a state
> between the calls somewhere to recognize that it now has
> done all possible permutations and the next permutation
> would return to the initial state before the first call?
a and b are iterators; as a pair they identify a range of items.
You can view each permutation as a number specification.
When you pass it the maximum number, e.g. think of "9876", the function
returns false, and produces the permutation that correspond to minimum
number for these items, "6789".
Cheers & hth.,
- Alf
> One can repeatedly call
>
> ::std::next_permutation( a, b )
>
> and eventually it will return »false« when there is no more
> permutation possible.
>
> But how can it now this? Doesn't it have to store a state
> between the calls somewhere to recognize that it now has
> done all possible permutations and the next permutation
> would return to the initial state before the first call?
a and b are iterators; as a pair they identify a range of items.
You can view each permutation as a number specification.
When you pass it the maximum number, e.g. think of "9876", the function
returns false, and produces the permutation that correspond to minimum
number for these items, "6789".
Cheers & hth.,
- Alf
Gareth Owen
Dec 16, 2016, 1:58:28 AM12/16/16
to
r...@zedat.fu-berlin.de (Stefan Ram) writes:
> One can repeatedly call
>
> ::std::next_permutation( a, b )
>
> and eventually it will return »false« when there is no more
> permutation possible.
>
> But how can it now this? Doesn't it have to store a state
> between the calls somewhere to recognize that it now has
> done all possible permutations and the next permutation
> would return to the initial state before the first call?
It doesn't return false before returning to the first permutation, but
> One can repeatedly call
>
> ::std::next_permutation( a, b )
>
> and eventually it will return »false« when there is no more
> permutation possible.
>
> But how can it now this? Doesn't it have to store a state
> between the calls somewhere to recognize that it now has
> done all possible permutations and the next permutation
> would return to the initial state before the first call?
the last (greatest) permutation lexicographically. So if you want all
the permutations, its best to start with the items sorted.
asetof...@gmail.com
Apr 28, 2017, 3:51:14 PM4/28/17
to
Seems to me, to understand next_permutation
has not to need initialization,
the only initialization it is in the array when start ordered as {1,2,3,...}
If I stop the iteration with one array and begin with one other array
it is only important that that array be as {1,2,3,4...n} ordered
0 new messages