Bug 11364 - half of permutations missing
Summary: half of permutations missing
Status: CLOSED FIXED
Alias: None
Product: gcc
Classification: Unclassified
Component: libstdc++ (show other bugs)
Version: 3.0.1
: P2 normal
Target Milestone: 3.4.0
Assignee: Not yet assigned to anyone
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2003-06-29 01:30 UTC by Jason James
Modified: 2005-07-23 22:49 UTC (History)
1 user (show)

See Also:
Host:
Target:
Build:
Known to work:
Known to fail:
Last reconfirmed:


Attachments
small program to count permutations from next_permutation (286 bytes, text/plain)
2003-06-29 02:46 UTC, Jason James
Details

Note You need to log in before you can comment on or make changes to this bug.
Description Jason James 2003-06-29 01:30:49 UTC
next_permutation called with a list of 6 items stops permuting after
only 360 rearrangements are generated.  6! is 720.
Comment 1 Jason James 2003-06-29 02:46:14 UTC
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.
Comment 2 Falk Hueffner 2003-06-29 11:57:48 UTC
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?
Comment 3 Jason James 2003-06-29 16:19:39 UTC
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         -+                              *
 **************************************************************************/
Comment 4 falk.hueffner 2003-06-29 16:31:11 UTC
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.

Comment 5 Paolo Carlini 2003-06-30 13:42:58 UTC
Not a bug, as per Falk's remarks.
Comment 6 Paolo Carlini 2003-06-30 13:43:36 UTC
Closed.