白話算法(7) 生成全排列的幾種思路(一)

// 獲取 currentIndexList 的下一個排列。例如 currentIndexList = [0,1,1]，調(diào)用此函數(shù)之后，
// currentIndexList 將變?yōu)?[0,1,2]；[0,2,2] 變?yōu)?[1,0,0]
static void GetNextIndexList(IList<int> currentIndexList)
{
    int count = currentIndexList.Count;

    for (int i = count-1; i >= 0; i--)
    {
        if (currentIndexList[i] < count - 1) // 不需要進位
        {
            currentIndexList[i]++; // 當(dāng)前位加1
            return;
        }
        else
        {
            currentIndexList[i] = 0; // 進位前把當(dāng)前位置0
        }
    }
}

// 生成 source 的全排列。
static IEnumerable<IList<string>> Permutation1(IList<string> source)
{
    // 初始化 indexList，使它具有 source.Count 個值為0的元素。
    int count = source.Count;
    IList<int> indexList = new List<int>();
    for (int i = 0; i < count; i++)
    {
        indexList.Add(0);
    }

    for (int i = 0; i < Math.Pow(count, count); i++)
    {
        GetNextIndexList(indexList);
        if (indexList.Distinct().Count() == count) // 不重復(fù)
        {
            IList<string> result = new List<string>();
            foreach (int j in indexList)
            {
                result.Add(source[j]);
            }
            yield return result;
        }
    }
}

IList<string> s = new List<string> { "a", "b", "c" };
foreach (IList<string> item in Permutation1(s))
{
    Console.WriteLine(item.Montage(t => t, " "));
}

/// <summary>
/// 返回source的全排列
/// </summary>
/// <param name="source"></param>
/// <returns></returns>
public static IEnumerable<string[]> Permutation2(string[] source)
{
    if (source.Length <= 0)
        yield break;

    string[] s = new string[source.Length];
    Array.Copy(source, s, source.Length);
    do
    {
        yield return s;
    } 
    while (NextPermutation(s) == true);
}

// 將 s 變換為下一個字典序排列。當(dāng)前排列已經(jīng)是最后一個排列時，返回false
private static bool NextPermutation(string[] s)
{
    int highIndex = 0;
    int lowIndex = s.Length - 1;
    int subsHighIndex = FindSubsHighIndex(s);
    if (subsHighIndex == highIndex) // s 已經(jīng)是最后的排列
        return false;

    Swap(s, subsHighIndex - 1, LastIndex(s, t => s[subsHighIndex - 1].CompareTo(t) <= 0));
    Reverse(s, subsHighIndex, lowIndex);
    return true;
}

// 確定subs的高位index。subs是s最低n位的子數(shù)組，它已經(jīng)是此子數(shù)組的最后一個排列
private static int FindSubsHighIndex(string[] s)
{
    int highIndex = 0;
    int lowIndex = s.Length - 1;
    int result = lowIndex;
    for ( ; result > highIndex; result--)
    {
        if (s[result].CompareTo(s[result - 1]) > 0)
            return result;
    }
    return result;
}

// 交換 s[i] 和 s[j]
private static void Swap(string[] s, int i, int j)
{
    string temp = s[i];
    s[i] = s[j];
    s[j] = temp;
}

// 反轉(zhuǎn) s[startIndex]..s[endIndex]
private static void Reverse(string[] s, int startIndex, int endIndex)
{
    while (startIndex < endIndex)
    {
        Swap(s, startIndex, endIndex);
        startIndex++;
        endIndex--;
    }
}

// 從后向前搜索s，返回第一個滿足predicate()==true的元素下標；找不到時返回-1
private static int LastIndex(string[] s, Func<string, bool> predicate)
{
    for (int i = s.Length - 1; i >= 0; i--)
    {
        if (predicate(s[i]) == true)
            return i;
    }
    return -1;
}

string[] s = new string[] { "A", "B", "C", "D" };
foreach (string[] p in Permutation2(s))
{
    Console.WriteLine(p.Montage(t => t, " "));
}