bidirectionaliterator.java

一些Java的小的应用程序

public class BidirectionalIterator {
	/**由上述分析可知，解决组合问题的通用算法不外乎递归和回溯两种。在针对具体
	 * 问题的时候，因为递归程序在递归层数上的限制，对于大型组合问
	 * 题而言，递归不是一个好的选择，这种情况下只能采取回溯的方法来解决。

    n个数的全排列问题相对简单，可以通过交换位置按序枚举来实现。STL提供了求某个序列
    下一个排列的算法next_permutation，其算法原理如下：
1. 从当前序列最尾端开始往前寻找两个相邻元素，令前面一个元素为*i，后一个元素为*ii，且满足*i<*ii；
2. 再次从当前序列末端开始向前扫描，找出第一个大于*i的元素，令为*j（j可能等于ii），将i，j元素对调；
3. 将ii之后（含ii）的所有元素颠倒次序，这样所得的排列即为当前序列的下一个排列。
其实现代码如下：*/
//template <class BidirectionalIterator>
bool next_permutation(BidirectionalIterator first, BidirectionalIterator last) 
{
  if (first == last) return false;   // 空範圍
  BidirectionalIterator i = first;
  ++i;
  if (i == last) return false;       // 只有一個元素
  i = last;                          // i 指向尾端
  --i;

 for(;;) 
 {
  BidirectionalIterator ii = i;
  --i;
  // 以上，鎖定一組（兩個）相鄰元素
  if (*i < *ii)                     // 如果前一個元素小於後一個元素
  { 
   BidirectionalIterator j = last;  // 令 j指向尾端
   while (!(*i < *--j));            // 由尾端往前找，直到遇上比 *i 大的元素
   iter_swap(i, j);                 // 交換 i, j
   reverse(ii, last);               // 將 ii 之後的元素全部逆向重排
   return true;
  }
  if (i == first)                   // 進行至最前面了
  { 
   reverse(first, last);            // 全部逆向重排
   return false;
  }
 }
} 

//下面程序演示了利用next_permutation来求取某个序列全排列的方法：
int main()
{
 int ia[] = {1,2,3,4};
 vector<int> iv(ia,ia+sizeof(ia)/sizeof(int));

 copy(iv.begin(),iv.end(),ostream_iterator<int>(cout," "));
 cout << endl;
 while(next_permutation(iv.begin(),iv.end()))
 {
  copy(iv.begin(),iv.end(),ostream_iterator<int>(cout," "));
  cout << endl;
 }

 return 0;
}
/**注意：上面程序中初始序列是按数值的从小到大的顺序排列的，如果初始序列无序的话，
上面程序只能求出从当前序列开始的后续部分排列，也就是说next_permutation求
出的排列是按排列从小到大的顺序进行的。*/

}