! Copyright (C) 2009 Jon Harper. ! See http://factorcode.org/license.txt for BSD license. USING: kernel math sequences sorting ; IN: permutations ! Begining from the end, find the smallest subsequence that's not increasing monotonic. ! Call a the first element of this sequence. ! swap a and the smallest number greater than a in the rest of the sequence. ! Natural sort the rest of the sequence. ! Append this new sequence to the begining sequence = [ deep-1+ (index-of-not-ascending) ] [ 2drop ] if ] if ; : index-of-not-ascending ( seq -- i ) dup empty? [ drop f ] [ [ 1 ] dip dup last (index-of-not-ascending) ] if ; : get-non-monotonic-endsequence ( seq -- beginseq endseq ) dup index-of-not-ascending dup [ cut* ] [ 2drop f f ] if ; : get-smallest-greater-than ( seq i -- seq ) [ > ] curry filter infimum ; : handle-endseq ( endseq -- newendseq ) dup unclip get-smallest-greater-than [ remove-one natural-sort ] keep prefix ; PRIVATE> : next ( seq -- seq ) get-non-monotonic-endsequence dup [ handle-endseq append ] [ drop ] if ;