{"id":29,"date":"2010-08-26T01:58:00","date_gmt":"2010-08-26T01:58:00","guid":{"rendered":"http:\/\/ratneshneema.com\/tech\/?p=29"},"modified":"2015-08-14T11:45:24","modified_gmt":"2015-08-14T11:45:24","slug":"algorithms-next_permutation","status":"publish","type":"post","link":"http:\/\/ratneshneema.com\/tech\/development\/algorithms-next_permutation\/","title":{"rendered":"Algorithms: next_permutation()"},"content":{"rendered":"<p>C++:<\/p>\n<div style=\"font-family: &quot;Courier New&quot;,Courier,monospace;\">template &lt;class BidirectionalIterator&gt;<br \/>bool next_permutation(BidirectionalIterator first,<br \/>&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp; BidirectionalIterator last) {<br \/>&nbsp;&nbsp;&nbsp; if (first == last) return false;<br \/>&nbsp;&nbsp;&nbsp; BidirectionalIterator i = first;<br \/>&nbsp;&nbsp;&nbsp; ++i;<br \/>&nbsp;&nbsp;&nbsp; if (i == last) return false;<br \/>&nbsp;&nbsp;&nbsp; i = last;<br \/>&nbsp;&nbsp;&nbsp; &#8211;i;<br \/>&nbsp;&nbsp;&nbsp; for(;;) {<br \/>&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; BidirectionalIterator ii = i&#8211;;<br \/>&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; if (*i &lt;*ii) {<br \/>&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; BidirectionalIterator j = last;<br \/>&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; while (!(*i &lt;*&#8211;j));<br \/>&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; iter_swap(i, j);<br \/>&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; reverse(ii, last);<br \/>&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; return true;<br \/>&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; }<br \/>&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; if (i == first) {<br \/>&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; reverse(first, last);<br \/>&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; return false;<br \/>&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; }<br \/>&nbsp;&nbsp;&nbsp; }<br \/>}<\/div>\n<p>An amazing piece of code! This is the next_permutation() function in the Standard C++ Library, defined in &lt;algorithm&gt;. And the best part&#8230; it&#8217;s O(n) complexity.<\/p>\n<p>Iterators are a generalization of pointers. That should make it much easier to understand \ud83d\ude00<br \/>It checks for the initial conditions of 0 length and 1 character strings, and then iterates through the given string from the last character to find the next largest permutation.&nbsp;<\/p>\n<p>What I wonder is it&#8217;s response when we enter Alphanumeric data, or even Mixed Alphabets (Smalls and Caps). That should break it. \ud83d\ude42<\/p>\n","protected":false},"excerpt":{"rendered":"<p>C++:<\/p>\n<p>template &lt;class BidirectionalIterator&gt;bool next_permutation(BidirectionalIterator first,&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp; BidirectionalIterator last) {&nbsp;&nbsp;&nbsp; if (first == last) return false;&nbsp;&nbsp;&nbsp; BidirectionalIterator i = first;&nbsp;&nbsp;&nbsp; ++i;&nbsp;&nbsp;&nbsp; if (i == last) return false;&nbsp;&nbsp;&nbsp; i = last;&nbsp;&nbsp;&nbsp; &#8211;i;&nbsp;&nbsp;&nbsp; for(;;) {&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; BidirectionalIterator ii = i&#8211;;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; if (*i &lt;*ii) {&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; BidirectionalIterator j = last;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; while (!(*i &lt;*&#8211;j));&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; iter_swap(i, j);&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; reverse(ii, last);&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; return true;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; }&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; if (i == first) {&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; reverse(first, [&#8230;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[69],"tags":[46,17],"_links":{"self":[{"href":"http:\/\/ratneshneema.com\/tech\/wp-json\/wp\/v2\/posts\/29"}],"collection":[{"href":"http:\/\/ratneshneema.com\/tech\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/ratneshneema.com\/tech\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/ratneshneema.com\/tech\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/ratneshneema.com\/tech\/wp-json\/wp\/v2\/comments?post=29"}],"version-history":[{"count":1,"href":"http:\/\/ratneshneema.com\/tech\/wp-json\/wp\/v2\/posts\/29\/revisions"}],"predecessor-version":[{"id":105,"href":"http:\/\/ratneshneema.com\/tech\/wp-json\/wp\/v2\/posts\/29\/revisions\/105"}],"wp:attachment":[{"href":"http:\/\/ratneshneema.com\/tech\/wp-json\/wp\/v2\/media?parent=29"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/ratneshneema.com\/tech\/wp-json\/wp\/v2\/categories?post=29"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/ratneshneema.com\/tech\/wp-json\/wp\/v2\/tags?post=29"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}