組合造物主？

Question

我想發送一個數字列表的方法，並通過將數字彼此相鄰來獲得我從這個列表中產生的所有可能的數字組合。

例如，對於數字{1, 2, 3}我會以回報：

{1, 2, 3, 12, 13, 21, 23, 31, 32, 123, 132, 213, 231, 312, 321} 

此代碼爲例子（我還沒有完成），僅「知道」來處理包含在3號名單他們。

private static void M1() 
{ 
    var intList = new List<int>() { 1, 2, 3 }; 
    var resultList = AllPossibleCombinations(intList); 
} 

private static object AllPossibleCombinations(List<int> List) 
{ 
    var result = new List<int>(); 
    result.Add(List[0]); 
    result.Add(List[1]); 
    result.Add(List[2]); 
    result.Add(List[0] * 10 + List[1]); 
    result.Add(List[1] * 10 + List[2]); 
    result.Add(List[0] * 10 + List[2]); 
    result.Add(List[1] * 10 + List[0]); 
    result.Add(List[2] * 10 + List[1]); 
    result.Add(List[2] * 10 + List[0]); 
    return result; 
} 

我該如何寫更通用的東西？我怎樣才能得到不同數量的元素的列表，並給出所有可能的組合？

Answer 1

這未必是最有效的，但在這裏是你如何能做到這一點使用非遞歸方法返回IEnumerable<T>。像這樣的東西可能需要儘可能少的內存，因爲它不需要在內存中構建所有的排列。相反，它只是允許您逐個迭代排列。

private static void Main() 
{ 
    var input1 = new[] {"1", "2", "3"}; 
    foreach (var output in EnumeratePermutations(input1)) 
     Debug.WriteLine(String.Join(",", output)); 
} 

private static IEnumerable<T[]> EnumeratePermutations<T>(T[] input) 
{ 
    return from partCount in Enumerable.Range(1, input.Length) 
      let inputs = Enumerable.Repeat(input, partCount).ToArray() 
      from indices in EnumerateCrossjoinIndices(inputs) 
      where indices.Distinct().Count() == indices.Length 
      select indices.Select(n => input[n]).ToArray(); 
} 

private static IEnumerable<int[]> EnumerateCrossjoinIndices(params Array[] arrays) 
{ 
    var arrayCount = arrays.Length; 
    if (arrayCount == 0) 
     yield break; 

    if (arrays.Any(a => a.Length == 0)) 
     yield break; 

    var indexer = new int[arrayCount]; 

    yield return (int[]) indexer.Clone(); 

    for (var dimension = arrayCount - 1; dimension >= 0; --dimension) 
    { 
     ++indexer[dimension]; 
     if (indexer[dimension] == arrays[dimension].Length) 
      indexer[dimension] = 0; 
     else 
     { 
      yield return (int[]) indexer.Clone(); 
      dimension = arrayCount; 
     } 
    } 
} 

EnumerateCrossjoinIndices需要潛在的不同長度的Ñ陣列和產生將在一個交叉連接操作中使用的索引的枚舉。例如，給出{"1","2"}和{"A","B","C"}，它將產生6個陣列{0,0},{0,1},{0,2}, {1,0},{1,1},{1,2}。請注意，由此方法產生的陣列包含索引到輸入數組中，而不是這些索引處的元素。

EnumeratePermutations需要一個數組併產生該數組項的排列。它通過枚舉過，將被用來CROSSJOIN陣列自相X倍的索引執行此（其中X = 1至Ñ，其中Ñ是數組中的項數）。然後過濾出任何一組交叉連接索引，其中集合不是一個獨特的集合。

Answer 2

嘗試此示例代碼：

private static List<int> AllPossibleCombinations(IList<int> alphabet) 
{ 
    List<int[]> combinations = new List<int[]>(); 
    MakeCombination(combinations, alphabet.Count, new int[0]); // Start recursion 
    combinations.RemoveAt(0); // Remove empty combination 
    return combinations.ConvertAll(c => c.Aggregate(0, (sum, index) => sum * 10 + alphabet[index])); 
} 

private static void MakeCombination(List<int[]> output, int length, int[] usedIndices) 
{ 
    output.Add(usedIndices); 
    for (int i = 0; i < length; i++) 
     if (Array.IndexOf(usedIndices, i) == -1) // If the index wasn't used earlier 
     { 
      // Add element to the array of indices by creating a new one: 
      int[] indices = new int[usedIndices.Length + 1]; 
      usedIndices.CopyTo(indices, 0); 
      indices[usedIndices.Length] = i; 

      if (length + 1 != indices.Length) 
       MakeCombination(output, length, indices); // Recursion 
     } 
} 

它使用遞歸來生成期望的組合。

用法：

var t = AllPossibleCombinations(new[] { 1, 2, 3 }); 

Answer 3

溶液1種

的更通用和類型無關的方式是創建基於樹的算法，該算法返回輸入對象的組合的集合。

代碼：

public static class IEnumerableExtensions 
{ 
    private class Node<T> 
    { 
     public Node() 
     { 
      Children = new List<Node<T>>(); 
     } 

     public T Value 
     { 
      get; 
      set; 
     } 

     public bool IsRoot 
     { 
      get; 
      set; 
     } 

     public List<Node<T>> Children 
     { 
      get; 
      private set; 
     } 

     public Node<T> Parent 
     { 
      get; 
      set; 
     } 

     public List<Node<T>> Path 
     { 
      get 
      { 
       List<Node<T>> Result = new List<Node<T>>(); 

       Result.Add(this); 

       if (this.Parent.IsRoot == false) 
       { 
        Result.AddRange(this.Parent.Path); 
       } 

       return Result; 
      } 
     } 
    } 

    public static IEnumerable<IEnumerable<T>> Combinations<T>(this IEnumerable<T> enumerable) 
    { 
     List<Node<T>> AllNodes = new List<Node<T>>(); 

     // Create tree. 
     Node<T> Root = new Node<T>() { IsRoot = true }; 
     Queue<Node<T>> Queue = new Queue<Node<T>>(); 
     Queue.Enqueue(Root); 

     int CurrentLevel = 0; 
     int LevelsToCreate = enumerable.Count(); 
     while (Queue.Count > 0) 
     { 
      var CurrentLevelNodes = Queue.ToList(); 
      Queue.Clear(); 

      foreach (var LoopNode in CurrentLevelNodes) 
      { 
       if (LoopNode.Children.Count == 0) 
       { 
        foreach (var LoopValue in enumerable) 
        { 
         var NewNode = new Node<T>() { Value = LoopValue, Parent = LoopNode }; 
         AllNodes.Add(NewNode); 
         LoopNode.Children.Add(NewNode); 
         Queue.Enqueue(NewNode); 
        } 
       } 
      } 

      CurrentLevel++; 
      if (CurrentLevel >= LevelsToCreate) 
      { 
       break; 
      } 
     } 

     // Return list of all paths (which are combinations). 
     List<List<T>> Result = new List<List<T>>(); 
     foreach (var LoopNode in AllNodes) 
     { 
      if (!LoopNode.IsRoot) 
      { 
       List<T> Combination = LoopNode.Path.Select(Item => Item.Value).ToList(); 
       Result.Add(Combination); 
      } 
     } 

     return Result; 
    } 
} 

實施例用數字：

class Program 
{ 
    static void Main(string[] args) 
    { 
     List<int> Input = new List<int>() { 1, 2, 3 }; 
     var Combinations = Input.Combinations(); 
    } 
} 

實施例與字符串：

static void Main(string[] args) 
    { 
     var Input = new List<string>() { "a", "b" }; 
     var Combinations = Input.Combinations(); 


     foreach (var LoopCombination in Combinations) 
     { 
      string Combination = string.Join(String.Empty, LoopCombination); 
      Console.WriteLine(Combination); 
     } 

     Console.ReadKey(); 
    } 

溶液2

第二個想法是不要使用基於樹的算法並逐步創建組合 - 它可能會更快。

代碼：

public class Combinator<T> 
{ 
    private readonly Dictionary<int, T> _Pattern; 
    private readonly int _Min = 0; 
    private readonly int _Max; 

    private List<int> _CurrentCombination; 

    public Combinator(IEnumerable<T> pattern) 
    { 
     _Pattern = new Dictionary<int, T>(); 
     for (int i = 0; i < pattern.Count(); i++) 
     { 
      _Pattern.Add(i, pattern.ElementAt(i)); 
     } 

     _CurrentCombination = new List<int>(); 
     _Max = pattern.Count() - 1; 
    } 

    public bool HasFinised 
    { 
     get; 
     private set; 
    } 

    public IEnumerable<T> Next() 
    { 
     // Initialize or increase. 
     if (_CurrentCombination.Count == 0) 
     { 
      _CurrentCombination.Add(_Min); 
     } 
     else 
     { 
      MyIncrease(_CurrentCombination.Count - 1); 
     } 

     if (_CurrentCombination.Count - 1 == _Max && _CurrentCombination.All(Key => Key == _Max)) 
     { 
      HasFinised = true; 
     } 

     return _CurrentCombination.Select(Key => _Pattern[Key]).ToList();; 
    } 

    private void MyIncrease(int index) 
    { 
     if (index >= 0) 
     { 
      _CurrentCombination[index] = _CurrentCombination[index] + 1; 

      if (_CurrentCombination[index] > _Max) 
      { 
       _CurrentCombination[index] = _Min; 

       if (index - 1 < 0) 
       { 
        _CurrentCombination.Insert(0, -1); 
        index++; 
       } 

       MyIncrease(index - 1); 
      } 
     } 
    } 
} 

例子：

class Program 
{ 
    static void Main(string[] args) 
    { 
     var Pattern = new List<string>() { "a", "b", "c" }; 
     Combinator<string> Combinator = new Combinator<string>(Pattern); 

     while (Combinator.HasFinised == false) 
     { 
      var Combined = Combinator.Next(); 
      var Joined = string.Join("-", Combined); 
      Console.WriteLine(Joined); 
     } 

     Console.ReadKey(); 
    } 
} 

如果你想要的物品，只有別人相結合：

static void Main(string[] args) 
    { 
     Combinator<int> Combinator = new Combinator<int>(new List<int>() { 1, 2, 3 }); 

     while (Combinator.HasFinised == false) 
     { 
      var NextCombination = Combinator.Next(); 
      var DistinctCheck = NextCombination.ToList().Distinct(); 
      if (DistinctCheck.Count() == NextCombination.Count()) 
      { 
       Console.WriteLine(string.Join(String.Empty, NextCombination.Select(Item => Item.ToString()))); 
      }     
     } 

     Console.ReadKey(); 
    }