std::next_permutation

std 中有一个 next_permutation 的算法,见这里,http://en.cppreference.com/w/c…,这个页面上面有一个实现

template<class BidirIt>
bool next_permutation(BidirIt first, BidirIt last)
{
    if (first == last) return false;
    BidirIt i = last;
    if (first == --i) return false;
 
    while (1) {
        BidirIt i1, i2;
 
        i1 = i;
        if (*--i < *i1) {
            i2 = last;
            while (!(*i < *--i2))
                ;
            std::iter_swap(i, i2);
            std::reverse(i1, last);
            return true;
        }
        if (i == first) {
            std::reverse(first, last);
            return false;
        }
    }
}

相关说明在这里,http://fisherlei.blogspot.com/…,但是对着上面的实现看的老费劲,大师写的东西果然晦涩难懂,表达力是强,但是奈何吾辈愚钝啊

遂改写了一个等价的,长这样

template<class BidiIterator>
bool next_permutation(BidiIterator first, BidiIterator last) {	
	if (std::distance(first, last) <= 1) {
		return false;
	}
	BidiIterator pivot = last-1;
	while (1) {
		pivot--;
		if (*pivot < *(pivot+1)) {	
			BidiIterator change = last-1;
			while (*change < *pivot) {
				change--;
			}
			std::iter_swap(pivot, change);
			std::reverse(pivot+1, last);
			return true;
		}
		if (pivot == first) {
			std::reverse(first, last);
			return false;
		}
	}
}

Leave a Reply

Your email address will not be published. Required fields are marked *