next_permutation called with a list of 6 items stops permuting after only 360 rearrangements are generated. 6! is 720.

Created attachment 4300 [details] small program to count permutations from next_permutation seems the permutation can't handle lists with duplicates properly. the base permutation is defined as ascending order from [first,last). this is not necessarily of unique values, however, but of all the values in that range of iterators.

I still can't see the bug. I get: 1 gives 1 permutations. 2 gives 2 permutations. 3 gives 6 permutations. 4 gives 24 permutations. 5 gives 60 permutations. 6 gives 360 permutations. 7 gives 2520 permutations. 8 gives 20160 permutations. 9 gives 181440 permutations. 10 gives 1814400 permutations. which seems correct to me. Which line is wrong? Which permutation is missing?

Subject: Re: half of permutations missing Falk et. al., On Sun, Jun 29, 2003 at 11:57:49AM -0000, falk at debian dot org wrote: > > http://gcc.gnu.org/bugzilla/show_bug.cgi?id=11364 > > falk at debian dot org changed: > > What |Removed |Added > ---------------------------------------------------------------------------- > Status|UNCONFIRMED |WAITING > > > ------- Additional Comments From falk at debian dot org 2003-06-29 11:57 ------- > I still can't see the bug. I get: > > 1 gives 1 permutations. > 2 gives 2 permutations. > 3 gives 6 permutations. > 4 gives 24 permutations. > These are fine... > 5 gives 60 permutations. > 6 gives 360 permutations. > 7 gives 2520 permutations. > 8 gives 20160 permutations. > 9 gives 181440 permutations. > 10 gives 1814400 permutations. > All these are half what they should be! The duplicate value is causing problems with the permutation algorithm. I'm trying to test all arrangements of data in a list and am only able to move through half of them due to this 'glitch'. Later, Jason -- (designed for a fixed-width font!!!) /************************************************************************** * Jason James CompSci Teacher -+ * * RPG Gamer |- but maybe not in that order * * Email: craie@acm.org Husband -+ * **************************************************************************/

Subject: Re: half of permutations missing "craie at acm dot org" <gcc-bugzilla@gcc.gnu.org> writes: > These are fine... > > > 5 gives 60 permutations. > > 6 gives 360 permutations. > > 7 gives 2520 permutations. > > 8 gives 20160 permutations. > > 9 gives 181440 permutations. > > 10 gives 1814400 permutations. > > > All these are half what they should be! The duplicate value is > causing problems with the permutation algorithm. > > I'm trying to test all arrangements of data in a list and am > only able to move through half of them due to this 'glitch'. You seem to have a wrong notion of "permutation". For example, the sequence {1, 1, 1, 1} has exactly one permutation. Additionally, what you seem to want (getting {1, 1, 1, 1} 24 times) is obvoiusly impossible to implement with the interface of next_permutation. To get what you want, you could for example use an array of pointers, and use std::next_permutation on that.

Not a bug, as per Falk's remarks.

Closed.