package array

import (
   "sort"
   "testing"
)

// 題目：輸入一個字符串，打印出該字符串中字符的所有排列。
// 要求：不能重復(fù)，比如：字符串中可能為abcb，但結(jié)果中不能有兩個abbc

//直接運(yùn)行此測試方法即可
func TestPermutation(t *testing.T) {
   //這里演示一下切片截取，【大可略過】
   perm := "12345"
   //perm = perm[:len(perm)-1]
   //切片截取原則：左閉右開（左臂有鎧）
   t.Logf(perm[1:5]) //2345
   t.Logf(perm[1:4]) //234
   t.Logf(perm[0:1]) //1
   
   //以abc為例，分別調(diào)用兩種解法
   s := "abc"
   t.Log(permutation1(s)) //回溯法
   t.Log(permutation2(s)) //下一個排列

}


// 解法1：回溯法【即深度優(yōu)先搜索】
// 我們將這個問題看作有 n 個排列成一行的空位，我們需要從左往右依次填入題目給定的 n 個字符，每個字符只能使用一次
// 大白話就是：我們先對第一個空位進(jìn)行插入元素，如果決定第一個空位插入a，則要把接下來的第二個一直到第n個空位全部填入【一路填到底：深度優(yōu)先】，然后再決定第一個空位插入b，，，以此類推
func permutation1(s string) (ans []string) {
   //字符串進(jìn)來后，先轉(zhuǎn)成byte切片
   t := []byte(s)
   //排序【從小到大】sort.slice(t, func(i,j int ) bool{return t[i] < t[j]})
   sort.Slice(t, func(i, j int) bool { return t[i] < t[j] })
   n := len(t)

   //當(dāng)前排列，正向使用時append，回溯時，逐個清除
   perm := make([]byte, 0, n)

   //標(biāo)記狀態(tài)切片，正向使用時設(shè)置為true，回溯時設(shè)置為false
   vis := make([]bool, n)

   //定義遞歸函數(shù)【回溯】
   var backtrack func(int)
   // i代表第幾個空位，從0開始
   backtrack = func(i int) {
      if i == n {
         //如果n個空位都排滿了，塞入結(jié)果集中，并返回
         ans = append(ans, string(perm))
         return
      }
      //對當(dāng)前的第i個空位，進(jìn)行選擇使用哪個字符填入
      for j, b := range vis {
         //加入有兩個B，sort排序后，兩個B一定緊鄰，如果B1未使用，則不允許使用B2，這樣就不會出現(xiàn)ABBC，ABBC重復(fù)的情況
         if b || j > 0 && !vis[j-1] && t[j-1] == t[j] {
            continue
         }
         //遞歸標(biāo)記當(dāng)前的元素
         vis[j] = true
         //遞歸使用當(dāng)前的元素
         perm = append(perm, t[j])
         backtrack(i + 1)
         //遞歸清除perm，已使用的當(dāng)前元素
         perm = perm[:len(perm)-1]
         //遞歸取消標(biāo)記當(dāng)前的元素
         vis[j] = false
      }
   }
   //從0開始啟動
   backtrack(0)
   return

}

//復(fù)雜度分析
//
//時間復(fù)雜度：O(n \times n!)O(n×n!)，其中 nn 為給定字符串的長度。這些字符的全部排列有 O(n!)O(n!) 個，每個排列平均需要 O(n)O(n) 的時間來生成。
//
//空間復(fù)雜度：O(n)O(n)。我們需要 O(n)O(n) 的棧空間進(jìn)行回溯，注意返回值不計(jì)入空間復(fù)雜度。



//解法2：下一個(更大的)排列，我先先把整個字符串按有小到大進(jìn)行排列，然后搜索緊鄰的下一個更大的排列，一直到找到最大的排列為止
//如：字符串123，下一個緊鄰的更大的排列，一定是132，然后是213，再是231，312最后到321，
//因?yàn)槭遣檎揖o鄰的下一個最大排列，所以即使給的字符為abbc這種帶重復(fù)字符的，也會自動判斷，無需額外去重。

func permutation2(s string) (ans []string) {
   t := []byte(s)
   // 按照有小到大進(jìn)行排列，此時處于最小的排列
   sort.Slice(t, func(i, j int) bool { return t[i] < t[j] })
   for {
      //把當(dāng)前的排列塞入結(jié)果集
      ans = append(ans, string(t))
      //查找下一個最大的排列，如果找不下一個更大的排列，說明已經(jīng)搜索結(jié)束了
      if !nextPermutation(t) {
         break
      }
   }
   return
}

// 緊鄰的下一個更大的排列
func nextPermutation(nums []byte) bool {
   n := len(nums)
   i := n - 2
   //先自己檢查(從最后開始檢查)，是否是由大到小排列，直到找到第一個不是由大到小的字符，記住此時的位置i（i之后都是由大到小排列的）
   for i >= 0 && nums[i] >= nums[i+1] {
      i--
   }
   if i < 0 {
      //如果已經(jīng)全部都是由大到小排列了，則返回false
      return false
   }
   j := n - 1
   // 借助另一個指針j，逐個判斷位置i的字符與j字符，是否符合由大到小排列，如果是，j向前移動
   for j >= 0 && nums[i] >= nums[j] {
      j--
   }
   // 直到找到不是由大到小排列的字符j以及當(dāng)前的i，對i、j進(jìn)行位置交換，
   nums[i], nums[j] = nums[j], nums[i]
   // 由于i之后的元素可以確定是由大到小排列的，但我們要的是下一個最大的配列，所以要把i之后的排列進(jìn)行一個倒排（即反轉(zhuǎn)），
   // 比如之前是321，現(xiàn)在我們要123，這樣才是緊鄰的下一個最大排列
   reverse(nums[i+1:])
   return true
}

// 反轉(zhuǎn)字符串
func reverse(a []byte) {
   for i, n := 0, len(a); i < n/2; i++ {
      a[i], a[n-1-i] = a[n-1-i], a[i]
   }
}

//復(fù)雜度分析
//
//時間復(fù)雜度：O(n \times n!)O(n×n!)，其中 nn 為給定字符串的長度。我們需要 O(n \log n)O(nlogn) 的時間得到第一個排列，\texttt{nextPermutation}nextPermutation 函數(shù)的時間復(fù)雜度為 O(n)O(n)，我們至多執(zhí)行該函數(shù) O(n!)O(n!) 次，因此總時間復(fù)雜度為 O(n \times n! + n \log n) = O(n \times n!)O(n×n!+nlogn)=O(n×n!)。
//
//空間復(fù)雜度：O(1)O(1)。注意返回值不計(jì)入空間復(fù)雜度。