 |
C++Talk.NET
C++ language newsgroups
|
| View previous topic :: View next topic |
| Author |
Message |
Usenet Poster
Guest
|
 Posted: Sun Dec 28, 2003 10:47 pm Post subject: prev_permutation & duplicates |
 |
|
Does the standard say anything about prev_permutation/next_permutation &
duplicates in the input sequence.
for eg.
char a[] = "acbcdc";
.... // sort the array
while(std::prev/next_permutation(a,a+6))
{
std::cout<
}
Also is the input sequence supposed to be sorted
or not ?
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
 |
P.J. Plauger
Guest
|
| Posted: Mon Dec 29, 2003 11:02 am Post subject: Re: prev_permutation & duplicates |
|
|
"Usenet Poster" <cpp_poster (AT) mailinator (DOT) com> wrote
| Quote: | Does the standard say anything about prev_permutation/next_permutation &
duplicates in the input sequence.
for eg.
char a[] = "acbcdc";
... // sort the array
while(std::prev/next_permutation(a,a+6))
{
std::cout<
}
|
The C++ Standard is silent on this topic, but it should
say something. Elements with equivalent ordering cause
problems -- sometimes infinite loops.
| Quote: | Also is the input sequence supposed to be sorted
or not ?
|
No. It can be permuted in any order. next_permutation
then generates the "next" permutation, by its own
internal standards.
P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.com
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Ben Hutchings
Guest
|
| Posted: Tue Dec 30, 2003 5:11 am Post subject: Re: prev_permutation & duplicates |
|
|
Usenet Poster wrote:
| Quote: | Does the standard say anything about prev_permutation/next_permutation &
duplicates in the input sequence.
|
No, it doesn't. It is unusual to generate permutations of a sequence
with duplicates but there is a simple algorithm for doing so. See the
public draft of section 7.2.1.2 of The Art of Computer Programming if
you are curious: <http://www-cs-faculty.stanford.edu/~knuth/fasc2b.ps.gz>.
| Quote: | for eg.
char a[] = "acbcdc";
... // sort the array
while(std::prev/next_permutation(a,a+6))
{
std::cout<
}
Also is the input sequence supposed to be sorted
or not ?
|
That depends on which permutations you want to see. If you want to
iterate over all permutations, it must be sorted.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
John Potter
Guest
|
| Posted: Tue Dec 30, 2003 5:12 am Post subject: Re: prev_permutation & duplicates |
|
|
On 29 Dec 2003 06:02:14 -0500, "P.J. Plauger" <pjp (AT) dinkumware (DOT) com>
wrote:
| Quote: | "Usenet Poster" <cpp_poster (AT) mailinator (DOT) com> wrote in message
news:689e93bc.0312281313.1928243d (AT) posting (DOT) google.com...
Does the standard say anything about prev_permutation/next_permutation &
duplicates in the input sequence.
char a[] = "acbcdc";
while(std::prev/next_permutation(a,a+6))
{
std::cout<
}
The C++ Standard is silent on this topic, but it should
say something. Elements with equivalent ordering cause
problems -- sometimes infinite loops.
|
Do you have an example implementation and a problem case?
I have never seen it fail. I guess that the difference
between < and <= could make an implementation fail with
duplicates when the other would not.
John
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
P.J. Plauger
Guest
|
| Posted: Tue Dec 30, 2003 8:26 pm Post subject: Re: prev_permutation & duplicates |
|
|
"John Potter" <jpotter (AT) falcon (DOT) lhup.edu> wrote
| Quote: | On 29 Dec 2003 06:02:14 -0500, "P.J. Plauger" <pjp (AT) dinkumware (DOT) com
wrote:
"Usenet Poster"
news:689e93bc.0312281313.1928243d (AT) posting (DOT) google.com...
Does the standard say anything about
prev_permutation/next_permutation &
duplicates in the input sequence.
char a[] = "acbcdc";
while(std::prev/next_permutation(a,a+6))
{
std::cout<
}
The C++ Standard is silent on this topic, but it should
say something. Elements with equivalent ordering cause
problems -- sometimes infinite loops.
Do you have an example implementation and a problem case?
I have never seen it fail.
|
This stuff gives me a headache. I worked through it about
eight years ago and convinced myself that the method used
in the original H-P STL can't handle a sequence with two
elements that have equivalent ordering. I'll chase down the
Knuth reference (cited separately by Ben Hutchings) and see
if I can get further educated.
| Quote: | I guess that the difference
between < and <= could make an implementation fail with
duplicates when the other would not.
|
<= is not a strict weak ordering, so it is unacceptable as an
ordering rule under any circumstances.
P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.com
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
John Potter
Guest
|
| Posted: Wed Dec 31, 2003 1:40 am Post subject: Re: prev_permutation & duplicates |
|
|
On 30 Dec 2003 15:26:10 -0500, "P.J. Plauger" <pjp (AT) dinkumware (DOT) com>
wrote:
| Quote: | "John Potter" <jpotter (AT) falcon (DOT) lhup.edu> wrote in message
news:6j01vv8635fpkfjqb8hgjbvat7pbvhe5sg (AT) 4ax (DOT) com...
I guess that the difference
between < and <= could make an implementation fail with
duplicates when the other would not.
= is not a strict weak ordering, so it is unacceptable as an
ordering rule under any circumstances.
|
I meant how it was used in the algorithm. I slapped together
a next_permutation and used cmp(a, b) when I should have used
!cmp(b, a). Worked fine until I added duplicates and got the
infinite loop in my caller. Changed it to what was needed
and everything works fine.
John
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Carsten Hansen
Guest
|
| Posted: Sun Jan 04, 2004 2:16 am Post subject: Re: prev_permutation & duplicates |
|
|
"P.J. Plauger" <pjp (AT) dinkumware (DOT) com> wrote
| Quote: | "Usenet Poster" <cpp_poster (AT) mailinator (DOT) com> wrote in message
news:689e93bc.0312281313.1928243d (AT) posting (DOT) google.com...
Does the standard say anything about prev_permutation/next_permutation
&
duplicates in the input sequence.
for eg.
char a[] = "acbcdc";
... // sort the array
while(std::prev/next_permutation(a,a+6))
{
std::cout<
}
The C++ Standard is silent on this topic, but it should
say something. Elements with equivalent ordering cause
problems -- sometimes infinite loops.
Also is the input sequence supposed to be sorted
or not ?
No. It can be permuted in any order. next_permutation
then generates the "next" permutation, by its own
internal standards.
P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.com
|
I don't understand your answer.
Clearly lexicographical comparison is defined for sequences with elements of
equivalent ordering.
The Standard does not need to say anything about the subject.
For the OP's sequence we have
abcccd
abccdc
abcdcc
abdccc
acbccd
acbcdc
acbdcc
accbcd
accbdc
etc.
There is a simple algorithm for generating this sequence. If an
implementation causes an infinite loop, it is a quality of implementation
issue.
Carsten Hansen
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Allan W
Guest
|
| Posted: Mon Jan 12, 2004 7:53 pm Post subject: Re: prev_permutation & duplicates |
|
|
Ben Hutchings <do-not-spam-benh (AT) bwsint (DOT) com> wrote
| Quote: | Usenet Poster wrote:
Does the standard say anything about prev_permutation/next_permutation &
duplicates in the input sequence.
No, it doesn't. It is unusual to generate permutations of a sequence
with duplicates but there is a simple algorithm for doing so. See the
public draft of section 7.2.1.2 of The Art of Computer Programming if
you are curious: <http://www-cs-faculty.stanford.edu/~knuth/fasc2b.ps.gz>.
for eg.
char a[] = "acbcdc";
... // sort the array
while(std::prev/next_permutation(a,a+6))
{
std::cout<
}
Also is the input sequence supposed to be sorted
or not ?
That depends on which permutations you want to see. If you want to
iterate over all permutations, it must be sorted.
|
That's not necessarily true.
The function is designed so that you could easily generate all
permutations in lexical order using logic like the above. But note
that when the return value is false, the array is guaranteed to
have been restored to the "initial" configuration -- meaning that
you could call next_permutation again.
So another way to generate all permutations is to NOT start out sorted,
but make a copy of the array. Then call next_permutation repeatedly,
ignoring the return value, until the contents of the array once again
match the copy.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Allan W
Guest
|
| Posted: Tue Jan 13, 2004 10:10 am Post subject: Re: prev_permutation & duplicates |
|
|
"Carsten Hansen" <hansen.c (AT) worldnet (DOT) att.net> wrote
| Quote: | "P.J. Plauger" <pjp (AT) dinkumware (DOT) com> wrote
"Usenet Poster" <cpp_poster (AT) mailinator (DOT) com> wrote
Does the standard say anything about prev_permutation/next_permutation
& duplicates in the input sequence.
for eg.
char a[] = "acbcdc";
The C++ Standard is silent on this topic, but it should
say something. Elements with equivalent ordering cause
problems -- sometimes infinite loops.
|
Does the standard really permit this? (I don't have access to my
copy right now, so I can't look it up.)
| Quote: | Also is the input sequence supposed to be sorted
or not ?
No. It can be permuted in any order. next_permutation
then generates the "next" permutation, by its own
internal standards.
I don't understand your answer.
|
I think he was saying that next_permutation doesn't neccesarily have to
use lexical ordering. (I don't have a copy with me today, so I'm not
sure if that's true -- but I think we can classify Mr. Plauger as an
"expert," whatever that is, and assume he knows what he's talking about.)
The Knuth article (Ben Hutchings posted a link to this) gives an
algorithm for next_permutation which makes at most one swap per iteration
(and the elements swapped are always adjacent). I'm sure you can see
the advantages in this! But it doesn't work if elements can be repeated --
and the result is not necesarily in lexographic order.
| Quote: | Clearly lexicographical comparison is defined for sequences with
elements of equivalent ordering.
The Standard does not need to say anything about the subject.
|
I would agree with this. If the standard doesn't say that having duplicates
in the original sequence causes UB, then duplicates better not trigger an
infinite loop.
| Quote: | For the OP's sequence we have
abcccd
abccdc
abcdcc
abdccc
acbccd
acbcdc
acbdcc
accbcd
accbdc
etc.
There is a simple algorithm for generating this sequence. If an
implementation causes an infinite loop, it is a quality of implementation
issue.
|
I'd agree with this. The Knuth article starts with a simpler example:
For example, the permutations of {1,2,2,3} are
1223, 1232, 1322, 2123, 2132, 2213, 2231, 2312, 2321, 3122, 3212, 3221
ordered lexographically.
(Bottom of page 1.)
There can be up to N! (factorial) permutations, but only if there are
no repeating elements. The actual number can be as small as 1 (if all
elements are equivalent).
Thanks to Ben Hutchings for posting a link to the Knuth article -- I
hadn't seen it before, but I find it extremely interesting.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Rob Mayoff
Guest
|
| Posted: Wed Jan 14, 2004 10:18 am Post subject: Re: prev_permutation & duplicates |
|
|
[email]allan_w (AT) my-dejanews (DOT) com[/email] (Allan W) wrote in message news:<7f2735a5.0401121140.1c225d51 (AT) posting (DOT) google.com>...
| Quote: | Does the standard really permit this? (I don't have access to my
copy right now, so I can't look it up.)
|
No, the standard doesn't permit it. The standard says that
next_permutation returns true if the next permutation exists, and
false otherwise. Whether the next permutation exists is independent
of the presence of duplicates in the sequence. An infinite loop has
no return value, so it cannot conform to the standard.
| Quote: | I think he was saying that next_permutation doesn't neccesarily have to
use lexical ordering. (I don't have a copy with me today, so I'm not
sure if that's true -- but I think we can classify Mr. Plauger as an
"expert," whatever that is, and assume he knows what he's talking about.)
|
The standard says "The next permutation is found by assuming that the
set of all permutations is lexicographically sorted with respect to
operator< or comp." It also says "the smallest permutation, that is,
the ascendingly sorted one". I think Plauger was mistaken.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Carsten Hansen
Guest
|
| Posted: Wed Jan 14, 2004 11:00 pm Post subject: Re: prev_permutation & duplicates |
|
|
"Allan W" <allan_w (AT) my-dejanews (DOT) com> wrote
| Quote: | "Carsten Hansen" <hansen.c (AT) worldnet (DOT) att.net> wrote
"P.J. Plauger" <pjp (AT) dinkumware (DOT) com> wrote
"Usenet Poster" <cpp_poster (AT) mailinator (DOT) com> wrote
Does the standard say anything about
prev_permutation/next_permutation
& duplicates in the input sequence.
for eg.
char a[] = "acbcdc";
The C++ Standard is silent on this topic, but it should
say something. Elements with equivalent ordering cause
problems -- sometimes infinite loops.
Does the standard really permit this? (I don't have access to my
copy right now, so I can't look it up.)
Also is the input sequence supposed to be sorted
or not ?
No. It can be permuted in any order. next_permutation
then generates the "next" permutation, by its own
internal standards.
I don't understand your answer.
I think he was saying that next_permutation doesn't neccesarily have to
use lexical ordering. (I don't have a copy with me today, so I'm not
sure if that's true -- but I think we can classify Mr. Plauger as an
"expert," whatever that is, and assume he knows what he's talking about.)
The Knuth article (Ben Hutchings posted a link to this) gives an
algorithm for next_permutation which makes at most one swap per iteration
(and the elements swapped are always adjacent). I'm sure you can see
the advantages in this! But it doesn't work if elements can be repeated --
and the result is not necesarily in lexographic order.
|
Here is the text from the Standard:
"25.3.9 Permutation generators
template<class BidirectionalIterator>
bool next_permutation(BidirectionalIterator first,
BidirectionalIterator last);
template<class BidirectionalIterator, class Compare>
bool next_permutation(BidirectionalIterator first,
BidirectionalIterator last, Compare comp);
Effects: Takes a sequence defined by the range [ first, last) and transforms
it into the next permutation.
The next permutation is found by assuming that the set of all permutations
is lexicographically
sorted with respect to operator< or comp. If such a permutation exists, it
returns true. Otherwise,
it transforms the sequence into the smallest permutation, that is, the
ascendingly sorted one, and returns
false."
The Standard is clear about this, the permutations must be in
lexicographical order. Hence the algorithm in the Knuth article does not
apply.
Carsten Hansen
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Ben Hutchings
Guest
|
| Posted: Fri Jan 16, 2004 3:01 am Post subject: Re: prev_permutation & duplicates |
|
|
Carsten Hansen wrote:
<snip>
| Quote: | The Standard is clear about this, the permutations must be in
lexicographical order. Hence the algorithm in the Knuth article
does not apply.
|
The Knuth "article" (actually it's a draft of part of his next
book) presents several algorithms, the first of which does provide
lexicographical ordering.
<http://www-cs-faculty.stanford.edu/~knuth/fasc2b.ps.gz>
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
