Contents

1. 1. 去重全排列

去重全排列

• 由于全排列就是从第一个数字起每个数分别与它后面的数字交换。我们先尝试加个这样
  的判断——如果一个数与后面的数字相同那么这二个数就不交换了。如122，第一个数与
  后面交换得212、221。然后122中第二数就不用与第三个数交换了，但对212，它第二个数
  与第三个数是不相同的，交换之后得到221。与由122中第一个数与第三个数交换所得的
  221重复了。所以这个方法不行。

• 换种思维，对122，第一个数1与第二个数2交换得到212，然后考虑第一个数1与第三个数
  2交换，此时由于第三个数等于第二个数，所以第一个数不再与第三个数交换。再考虑212
  ，它的第二个数与第三个数交换可以得到解决221。此时全排列生成完毕。

• 这样我们也得到了在全排列中去掉重复的规则——去重的全排列就是从第一个数字起每个
  数分别与它后面非重复出现的数字交换。

• 重点：用编程的话描述就是第i个数与第j个数交换时，
  要求[i,j)中没有与第j个数相等的数。
• 补:N个元素（不同的）的全排列总数为n！个。
  如果有相同的元素就把那个元素个数的阶乘给除掉，具体看hdu5651

  #include <iostream>
  #include <cstdio>
  
  using namespace std;
  
  bool can_swap(int a[], int nbegin, int nend)//[nBegin,nEnd)中是否有数字与下标为nEnd的数字相等 {//第i个数与第j个数交换时，要求[i,j)中没有与第j个数相等的数
  
      for(int i = nbegin; i < nend; i++)
      {
          if(a[i] == a[nend])
              return false;
      }
      return true;
  }
  
  void func(int a[], int m_begin, int m_end)	//m_begin表示当前选到第几个了,m_end表示总共多少个数{
  
      int i;
      if(m_begin + 1 == m_end)
      {
          for(i = 0; i < m_end; i++)
              printf("%d ", a[i]);
          printf("\n");
          return ;
      }
      else
      {
          for(i = m_begin; i < m_end; i++)	//for循环遍历该排列中第一个位置的所有可能情况
          {
              if(can_swap(a, m_begin, i))
              {
                  swap(a[i], a[m_begin]);		//第一次交换是和自己交换
                  func(a, m_begin + 1, m_end);//递归求后面的全排列
                  swap(a[i], a[m_begin]);		//复原
              }
          }
      }
  }
  
  int main(){
  
      /*int a[] = {1,2,3,4};    func(a, 0, 4);*/
      func(a, 0, 4);*/
      int a[] = {1,2,2};
      func(a, 0, sizeof(a) / sizeof(a[0]));
      return 0;
  }