C++Talk.NET C++ language newsgroups   Archives   FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in to check your private messages   Log in  Permutations nPr          C++Talk.NET Forum Index -> C++ Language (Moderated) View previous topic :: View next topic   Author Message Ed Neukirch Guest Posted: Tue Dec 30, 2003 12:37 pm    Post subject: Permutations nPr I would like to determine nPr -- that is, the permutation of 'n' items taken 'r' at a time preferably using the prev_permutation and next_permutation functions of the STL. I 'googled' and posted on other forums but could find nothing of much help. example: nPr, n=4,r=2 string = "abcd" would produce 'ab', 'ac','ad','ba'.... and so on. I would appreciate any guidance or direction toward either algorithms or source code. Thanking you in advance. Ed [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Francis Glassborow Guest Posted: Tue Dec 30, 2003 7:28 pm    Post subject: Re: Permutations nPr In message <vv1aoo78vngtcb (AT) corp (DOT) supernews.com>, Ed Neukirch <eoneuk (AT) localnet (DOT) com> writes Quote: I would like to determine nPr -- that is, the permutation of 'n' items taken 'r' at a time preferably using the prev_permutation and next_permutation functions of the STL. I 'googled' and posted on other forums but could find nothing of much help. example: nPr, n=4,r=2 string = "abcd" would produce 'ab', 'ac','ad','ba'.... and so on. I would appreciate any guidance or direction toward either algorithms or source code. Thanking you in advance. Sort your sequence use next_permutation repeatedly until it returns true doing the following on each iteration: truncate the result to r elements push the result into a suitable std::set<> Now the std::set<> contains the solution. -- Francis Glassborow ACCU Author of 'You Can Do It!' see http://www.spellen.org/youcandoit or http://www.robinton.demon.co.uk Happy Xmas, Hanukkah, Yuletide, Winter/Summer Solstice to all. [ 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 Dec 31, 2003 1:07 am    Post subject: Re: Permutations nPr "Ed Neukirch" <eoneuk (AT) localnet (DOT) com> wrote Quote: I would like to determine nPr -- that is, the permutation of 'n' items taken 'r' at a time preferably using the prev_permutation and next_permutation functions of the STL. I 'googled' and posted on other forums but could find nothing of much help. example: nPr, n=4,r=2 string = "abcd" would produce 'ab', 'ac','ad','ba'.... and so on. I would appreciate any guidance or direction toward either algorithms or source code. Thanking you in advance. Ed [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Sort the sequence. Repeat the following: Output first r elements. Sort in reverse order the last n - r elements. Generate the next permutation. 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 John Potter Guest Posted: Fri Jan 02, 2004 12:59 pm    Post subject: Re: Permutations nPr On 30 Dec 2003 20:07:11 -0500, "Carsten Hansen" <hansen.c (AT) worldnet (DOT) att.net> wrote: Quote: "Ed Neukirch" <eoneuk (AT) localnet (DOT) com> wrote in message news:vv1aoo78vngtcb (AT) corp (DOT) supernews.com... example: nPr, n=4,r=2 string = "abcd" would produce 'ab', 'ac','ad','ba'.... and so on. Sort the sequence. Repeat the following: Output first r elements. Sort in reverse order the last n - r elements. Generate the next permutation. Very nice. You might observe that after next_permutation, the last n - r elements are sorted in forward order. It is a bit faster to reverse than to sort. John [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First         C++Talk.NET Forum Index -> C++ Language (Moderated) All times are GMT Page 1 of 1   Jump to: Select a forum C/C++----------------C LanguageC Language (Moderated)C++ Language (Moderated)C++ language (comp.lang.c++)C++ language, library and standards Non-English C/C++ Newsgroups----------------C++ (German)C++ (French)  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 Powered by phpBB © 2001, 2006 phpBB Group SEO toolkit © 2004-2006 webmedic.