給定整數n(0<n<10)，求全排列。比如n=3, 輸出123 132 213 231 312 321

目錄

• 目錄
  • • 思想
    • 主函數main
    • Permuint n
    • next_permuvector num n

思想

假設給定6，那麼輸出的順序應該是 ： 123546，123564，123645 ，123654，124356 …..654321

主函數main

int main(int argc, char const *argv[])
{
  cout << "Input an number..." << endl ;
  int n;
  cin >> n;
  Permu(n);
  return ;
}
           

Permu(int n)

void Permu(int n){
  std::vector<int> v;
  for (int i = ; i < n; ++i)
  {
    v.push_back(i+);
    cout << i+;
  }
  if (n==) return;
  while(next_permu(v, n));
}
           

将1,2,3…n壓入一個vector，每次調用next_permu()來産生并輸出一個一個排列。

next_permu(vector& num, n)

bool next_permu(vector<int>& num, int n){
  int i = n - ; int ii = n - ;
  while(num[i] > num[ii])
  {
    --i;
    --ii;
  }
  if (i < ) return false;
  ii = n -;
  while(num[i] > num[ii])
  {
    --ii;
  }
  swap(num[i], num[ii]);
  ii=n-; i=i+;
  while(i < ii)
  {
    swap(num[i], num[ii]);
    ++i; --ii;
  }
  for(auto c : num )
    cout << c;
  cout << endl ;
  return true ;
}
           

比如某次num裡面的元素為123456，那麼調用一次next_permu函數後，變為123465，然後再調用next_permu，變為123546，123564，123645 ，123654，124356 …..注意第一個while循環和第二個while循環的語句塊不同，實作的功能也不同：第一個while循環的作用是确定i，找到将用于交換的第一個元素; 經過第一個循環體後，重新定位ii，而對i不重新定位，第二個循環體的作用是找出比num[i]大的最小整數，同時這個整數也是小于等于第一次while循環ii所指向的num[ii]，用于完成兩者的交換。這樣交換之後，num[i]之後的元素都是降序排列，然後再重新定位i和ii(ii=n-1; i=i+1;), 當i