重複排列

Question

如果您可以找到更好的標題，請修改。

，我會說我已經看了幾個q &一個關於這個話題，主要是this one和this article沒有開始已經找到了一種方法來做到這一點：

鑑於單詞「鬼節」我想找到所有長度的所有排列和組合。我嘗試的第一件事是迭代下面的代碼，給它的長度爲1，開始並繼續，直到達到單詞長度（9）。

public static IEnumerable<IEnumerable<T>> 
     GetPermutations<T>(IEnumerable<T> list, int length) 
    { 
     if (length == 1) return list.Select(t => new T[] {t}); 

     return GetPermutations(list, length - 1) 
      .SelectMany(t => list.Where(e => !t.Contains(e)), 
       (t1, t2) => t1.Concat(new T[] {t2})); 
    } 

這給了我意想不到的結果爲雙「E」和「L的省略，剩下最後一組短。

一個更簡單的例子可以是 'MOM'{M，O，M}，其中最後一組結果將是：

• 中號

• ö

• MO

• OM

• MM

• MOM

• MMO

• OMM

請注意，我想看看這兩個「M的爲可用，但我不希望看到的 「MMM」 作爲結果。由於保留原始順序（1,2,3），交換位置1和3（3,2,1）會導致'M'，'O'，'M'，但是「MOM」會在結果中出現兩次此字符序列中只出現一次的結果列表（可以通過字符串比較來完成）

再次，集{1,1,2,3}我希望看到：

{1， 1}

但不是{2,2}或{3,3}

Answer 1

我建議在看一封信位置0,1,2,3,4等映射這些字母的排列，並然後消除重複。

在不更改GetPermutations函數的情況下，我添加了另一個函數來獲取字母位置的排列，將這些結果映射到字符串，然後消除重複項。

public void PermutationsTestMethod() 
{ 
    GetPermutationsOfString("MOM").ForEach(v => Debug.Print(v)); 
} 

public List<string> GetPermutationsOfString(string value) 
{ 
    var resultList = new List<string>(); 

    for (var i = 1; i <= value.Length; i++) 
    { 
     var permutations = GetPermutations(Enumerable.Range(0, value.Length), i); 

     resultList.AddRange(
      permutations 
       .Select(v => new string(v.Select(z => value[z]).ToArray())) 
       .Distinct() 
      ); 
    } 

    return resultList; 
} 

public static IEnumerable<IEnumerable<T>> GetPermutations<T>(IEnumerable<T> list, int length) 
{ 
    if (length == 1) return list.Select(t => new T[] { t }); 

    return GetPermutations(list, length - 1) 
     .SelectMany(t => list.Where(e => !t.Contains(e)), 
      (t1, t2) => t1.Concat(new T[] { t2 })); 
} 

Answer 2

這工作得很好：

Func<string, IEnumerable<string>> getAllSubsets = null; 
getAllSubsets = x => 
    (x == null || !x.Any()) 
     ? Enumerable.Empty<string>() 
     : (x.Length > 1 
      ? getAllSubsets(x.Substring(1)) 
       .SelectMany(y => new [] { y, x.Substring(0, 1) + y }) 
      : new [] { "", x.Substring(0, 1) }); 

因此，考慮getAllSubsets("ABC")我得到：

「」， 「A」， 「B」， 「AB」， 「C」，「 AC」， 「BC」， 「ABC」

而且，對於你的"MOM"例如我得到：

「」， 「M」， 「O」， 「MO」， 「M」， 「MM」， 「OM」， 「媽媽」

這將是微不足道過濾掉空字符串和重複值（如果需要的話），但按照它的規定嚴格地生成所有子集。

Answer 3

這裏的另一個解決方案應該是明確的，容易理解的：

public static IEnumerable<string> GetPermutations(string input) 
    { 
     if (string.IsNullOrEmpty(input)) 
     { 
      return new List<string>(); 
     } 

     var length = input.Length; 
     var indices = Enumerable.Range(0, length).ToList(); 
     var permutationsOfIndices = GetNumericalPermutations(indices, length); 

     var permutationsOfInput = permutationsOfIndices.Select(x => new string(x.Select(y => input[y]).ToArray())) 
                 .Distinct(); 
     return permutationsOfInput; 
    } 


    private static List<List<int>> GetNumericalPermutations(List<int> values, int maxLength) 
    { 
     if (maxLength == 1) 
     { 
      return values.Select(x => new List<int>{x}).ToList(); 
     } 
     else 
     { 
      var permutations = GetNumericalPermutations(values, maxLength - 1); 

      foreach (var index in values) 
      { 
       var newPermutations = permutations.Where(x => !x.Contains(index)) 
                .Select(x => x.Concat(new List<int> { index })) 
                .Where(x => !permutations.Any(y => y.SequenceEqual(x))) 
                .Select(x => x.ToList()) 
                .ToList(); 

       permutations.AddRange(newPermutations); 
      } 
      return permutations; 
     } 
    } 

例如，輸出爲「媽媽」是：

M 
O 
OM 
MM 
MO 
MMO 
OMM 
MOM 

Answer 4

我覺得一般都比較好儘量避免產生是並消除排列。像「aaaaaaaaaaaaaaab」這樣的文本會產生大量的重複。

public static IEnumerable<IEnumerable<T>> 
GetPermutationsInner<T>(IEnumerable<IGrouping<T, T>> groupedList, int length) 
{ 
    if (length == 1) return groupedList.Select(t => new T[] { t.Key }); 

    return GetPermutationsInner<T>(groupedList, length - 1) 
     .SelectMany(t => groupedList 
       .Where(e => t.Count(w => w.Equals(e.Key)) < e.Count()) 
       .Select(s => s.Key), 
      (t1, t2) => t1.Concat(new T[] { t2 })); 
} 

public static IEnumerable<IEnumerable<T>> 
    GetPermutations<T>(IEnumerable<T> list) 
{ 
    var resultList = new List<IEnumerable<T>>(); 
    for (int i = 1; i <= list.Count(); ++i) 
    { 
     resultList.AddRange(GetPermutationsInner<T>(list.GroupBy(g => g), i)); 
    } 
    return resultList; 
}