计算一个字符串的所有可能的组合，扭曲

Question

我试图让用户在文本框中输入文本，并让程序生成它的所有可能的组合，除了最少3个字符和最大值6.我不需要像'as'，'a'，'i'，'to'等无用的单词，等我的数组乱成一团。我还会检查每个组合对照字典，以确保它是一个真正的单词。

我的字典完成（苦心产生，here's a link to it回报（警告：巨大的加载时间（对我来说））

不管怎么说，如果用户输入“ABCDEF”（排名不分先后），怎么可能我产生，例如：

'ABC' 
'BAC' 
'CAB' 
... 
'ABD' 
'ABE' 
'ABF' 

等......每个可能的组合，不管什么样的顺序据我所知，有这些组合中的一个荒谬的数额，但只需要计算一次，所以我？我不太在意这件事

我发现代码示例以递归方式查找固定宽度字符串（ABCDEF，ABCDFE ... ACDBFE等）的组合（不是置换，我不需要那些）。他们没有做我所需要的事情，对于甚至从哪个项目开始，我都没有丝毫的线索。

这不是家庭作业，它开始作为一个我的个人项目，成长为接管我的生活在这样一个简单的问题......我不相信我无法弄清楚这一点！

Answer 1

这听起来我像你描述的Power Set

这是我曾说谎的实现在我的个人图书馆周围：

// Helper method to count set bits in an integer 
public static int CountBits(int n) 
{ 
    int count = 0; 
    while (n != 0) 
    { 
     count++; 
     n &= (n - 1); 
    } 
    return count; 
} 


public static IEnumerable<IEnumerable<T>> PowerSet<T>(
    IEnumerable<T> src, 
    int minSetSize = 0, 
    int maxSetSize = int.MaxValue) 
{ 
    // we want fast random access to the source, so we'll 
    // need to ToArray() it 
    var cached = src.ToArray(); 
    var setSize = Math.Pow(2, cached.Length); 
    for(int i=0; i < setSize; i++) 
    { 
     var subSetSize = CountBits(i); 
     if(subSetSize < minSetSize || 
      subSetSize > maxSetSize) 
     { 
      continue; 
     } 
     T[] set = new T[subSetSize]; 

     var temp = i; 
     var srcIdx = 0; 
     var dstIdx = 0; 
     while(temp > 0) 
     { 
      if((temp & 0x01) == 1) 
      { 
       set[dstIdx++] = cached[srcIdx]; 
      } 
      temp >>= 1; 
      srcIdx++;    
     } 
     yield return set; 
    } 
    yield break; 
} 

和快速试验台：

void Main() 
{ 
    var src = "ABCDEF"; 
    var combos = PowerSet(src, 3, 6); 

    // hairy joins for great prettiness 
    Console.WriteLine(
     string.Join(" , ", 
      combos.Select(subset => 
       string.Concat("[", 
        string.Join(",", subset) , "]"))) 
    ); 
} 

输出：

[A,B,C] , [A,B,D] , [A,C,D] , [B,C,D] , [A,B,C,D] , [A,B,E] , [A,C,E] , [B,C,E] , [A,B,C,E] , 
[A,D,E] , [B,D,E] , [A,B,D,E] , [C,D,E] , [A,C,D,E] , [B,C,D,E] , [A,B,C,D,E] , [A,B,F] , 
[A,C,F] , [B,C,F] , [A,B,C,F] , [A,D,F] , [B,D,F] , [A,B,D,F] , [C,D,F] , [A,C,D,F] , 
[B,C,D,F] , [A,B,C,D,F] , [A,E,F] , [B,E,F] , [A,B,E,F] , [C,E,F] , [A,C,E,F] , [B,C,E,F] , 
[A,B,C,E,F] , [D,E,F] , [A,D,E,F] , [B,D,E,F] , [A,B,D,E,F] , [C,D,E,F] , [A,C,D,E,F] , 
[B,C,D,E,F] , [A,B,C,D,E,F] 

Answer 2

假设你还想要像“AAB”这样的字符集合的“交叉产品”。

代可以像LINQ简单：

  string myset = "ABCDE"; 
      var All = (from char l1 in myset 
        from char l2 in myset 
        from char l3 in myset 
        select new string(new char[] { l1, l2, l3})).ToList(); 

注：建筑许多字符串和字符数组是并不快。你可能想用一个自定义类来更换新的字符串和新的char []像这样：

select new MyCustomClass(l1, l2, l3).ToList(); 

如果你不想要的东西，如“AAB”（或“鳗鱼”），那么我会点你到维基百科的“组合”。

要从固定长度到“从3到6的任何长度”加入多个集合，如果限制是动态的，则使用循环。

Answer 3

要做到这一点，最好的方法是使用for循环并将每个字符从int转换为char并将它们连接在一起形成一个字符串。

例如：

for(int i = 0; i < 26; i++) 
{ 
    Console.WriteLine((char)i + 'A');   
} 

Answer 4

从这个link（MIT许可）

using System; 
using System.Collections.Generic; 
using System.Diagnostics; 

// Copyright (c) 2010 Alex Regueiro 
// Licensed under MIT license, available at <http://www.opensource.org/licenses/mit-license.php>. 
// Published originally at <http://blog.noldorin.com/2010/05/combinatorics-in-csharp/>. 
// Version 1.0, released 22nd May 2010. 
public static class CombinatoricsUtilities 
{ 
    // Error messages 
    private const string errorMessageValueLessThanZero = "Value must be greater than zero, if specified."; 
    private const string errorMessagesIndicesListInvalidSize = "List of indices must have same size as list of elements."; 

    /// <summary> 
    /// Gets all permutations (of a given size) of a given list, either with or without reptitions. 
    /// </summary> 
    /// <typeparam name="T">The type of the elements in the list.</typeparam> 
    /// <param name="list">The list of which to get permutations.</param> 
    /// <param name="action">The action to perform on each permutation of the list.</param> 
    /// <param name="resultSize">The number of elements in each resulting permutation; or <see langword="null"/> to get 
    /// premutations of the same size as <paramref name="list"/>.</param> 
    /// <param name="withRepetition"><see langword="true"/> to get permutations with reptition of elements; 
    /// <see langword="false"/> to get permutations without reptition of elements.</param> 
    /// <exception cref="ArgumentNullException"><paramref name="list"/> is <see langword="null"/>. -or- 
    /// <paramref name="action"/> is <see langword="null"/>.</exception> 
    /// <exception cref="ArgumentException"><paramref name="resultSize"/> is less than zero.</exception> 
    /// <remarks> 
    /// The algorithm performs permutations in-place. <paramref name="list"/> is however not changed. 
    /// </remarks> 
    public static void GetPermutations<T>(this IList<T> list, Action<IList<T>> action, int? resultSize = null, 
     bool withRepetition = false) 
    { 
     if (list == null) 
      throw new ArgumentNullException("list"); 
     if (action == null) 
      throw new ArgumentNullException("action"); 
     if (resultSize.HasValue && resultSize.Value <= 0) 
      throw new ArgumentException(errorMessageValueLessThanZero, "resultSize"); 

     var result = new T[resultSize.HasValue ? resultSize.Value : list.Count]; 
     var indices = new int[result.Length]; 
     for (int i = 0; i < indices.Length; i++) 
      indices[i] = withRepetition ? -1 : i - 1; 

     int curIndex = 0; 
     while (curIndex != -1) 
     { 
      indices[curIndex]++; 
      if (indices[curIndex] == list.Count) 
      { 
       indices[curIndex] = withRepetition ? -1 : curIndex - 1; 
       curIndex--; 
      } 
      else 
      { 
       result[curIndex] = list[indices[curIndex]]; 
       if (curIndex < indices.Length - 1) 
        curIndex++; 
       else 
        action(result); 
      } 
     } 
    } 

    /// <summary> 
    /// Gets all combinations (of a given size) of a given list, either with or without reptitions. 
    /// </summary> 
    /// <typeparam name="T">The type of the elements in the list.</typeparam> 
    /// <param name="list">The list of which to get combinations.</param> 
    /// <param name="action">The action to perform on each combination of the list.</param> 
    /// <param name="resultSize">The number of elements in each resulting combination; or <see langword="null"/> to get 
    /// premutations of the same size as <paramref name="list"/>.</param> 
    /// <param name="withRepetition"><see langword="true"/> to get combinations with reptition of elements; 
    /// <see langword="false"/> to get combinations without reptition of elements.</param> 
    /// <exception cref="ArgumentNullException"><paramref name="list"/> is <see langword="null"/>. -or- 
    /// <paramref name="action"/> is <see langword="null"/>.</exception> 
    /// <exception cref="ArgumentException"><paramref name="resultSize"/> is less than zero.</exception> 
    /// <remarks> 
    /// The algorithm performs combinations in-place. <paramref name="list"/> is however not changed. 
    /// </remarks> 
    public static void GetCombinations<T>(this IList<T> list, Action<IList<T>> action, int? resultSize = null, 
     bool withRepetition = false) 
    { 
     if (list == null) 
      throw new ArgumentNullException("list"); 
     if (action == null) 
      throw new ArgumentNullException("action"); 
     if (resultSize.HasValue && resultSize.Value <= 0) 
      throw new ArgumentException(errorMessageValueLessThanZero, "resultSize"); 

     var result = new T[resultSize.HasValue ? resultSize.Value : list.Count]; 
     var indices = new int[result.Length]; 
     for (int i = 0; i < indices.Length; i++) 
      indices[i] = withRepetition ? -1 : indices.Length - i - 2; 

     int curIndex = 0; 
     while (curIndex != -1) 
     { 
      indices[curIndex]++; 
      if (indices[curIndex] == (curIndex == 0 ? list.Count : indices[curIndex - 1] + (withRepetition ? 1 : 0))) 
      { 
       indices[curIndex] = withRepetition ? -1 : indices.Length - curIndex - 2; 
       curIndex--; 
      } 
      else 
      { 
       result[curIndex] = list[indices[curIndex]]; 
       if (curIndex < indices.Length - 1) 
        curIndex++; 
       else 
        action(result); 
      } 
     } 
    } 

    /// <summary> 
    /// Gets a specific permutation of a given list. 
    /// </summary> 
    /// <typeparam name="T">The type of the elements in the list.</typeparam> 
    /// <param name="list">The list to permute.</param> 
    /// <param name="indices">The indices of the elements in the original list at each index in the permuted list. 
    /// </param> 
    /// <returns>The specified permutation of the given list.</returns> 
    /// <exception cref="ArgumentNullException"><paramref name="list"/> is <see langword="null"/>. -or- 
    /// <paramref name="indices"/> is <see langword="null"/>.</exception> 
    /// <exception cref="ArgumentException"><paramref name="indices"/> does not have the same size as 
    /// <paramref name="list"/>.</exception> 
    public static IList<T> Permute<T>(this IList<T> list, IList<int> indices) 
    { 
     if (list == null) 
      throw new ArgumentNullException("list"); 
     if (indices == null) 
      throw new ArgumentNullException("indices"); 
     if (list.Count != indices.Count) 
      throw new ArgumentException(errorMessagesIndicesListInvalidSize, "indices"); 

     var result = new T[list.Count]; 
     for (int i = 0; i < result.Length; i++) 
      result[i] = list[indices[i]]; 
     return result; 
    } 
}