从字符串中生成特定长度的所有变体

Question

我在C＃中看到了几个字符串变体的实现，但它们都没有对它们的长度有任何限制。不幸的是，我无法修改它们来实现我的目标，例如

为：

string = "ABCD" and variationLength = 2 

生成新的字符串：

AB, AC, AD, BA, BC, BD, CA, CB, CD, DA, DB, DC 

我正在寻找的正是这种Python的和itertools.permutations实现，但在C＃。 （https://docs.python.org/3/library/itertools.html#itertools.permutations）

在C＃中有类似的东西吗？如果不是，那么实现它的最简单方法是什么？

Edit_2： 到目前为止，我想出了一个主意，列出定字符串的所有独特的字符，然后让变化了出来

static void PrintAllKLengthPerm(string str, int k) 
{ 
    int n = str.Length; 
    PrintAllKLengthPermRec(str, "", n, k); 
} 

// The main recursive method to print all possible strings of length k 
static void PrintAllKLengthPermRec(string str, String prefix, int n, int k) 
{ 
    // Base case: k is 0, print prefix 
    if (k == 0) 
    { 
     Console.WriteLine(prefix); 
     return; 
    } 

    // One by one add all characters from str and recursively 
    // call for k equals to k-1 
    for (int i = 0; i < n; ++i) 
    { 
     // Next character of input added 
     String newPrefix = prefix + str[i]; 

     // k is decreased, because we have added a new character 
     PrintAllKLengthPermRec(str, newPrefix, n, k - 1); 
    } 
} 

static void Main(string[] args) 
{ 
    string str = "ABCD"; 
    int permLen = 2; 

    //get all unique characters in string 
    string uniqStr = new String(str.Distinct().ToArray()); 

    // Print all possible strings of length permLen out of uniqStr characters 
    PrintAllKLengthPerm(uniqStr, permLen);  
} 

但是我正在寻找更优化，有效地解决

Answer 1

这里是一个真正的递归排列法：

public IEnumerable<string> Permutate(string source, int count) 
{ 
    if (source.Length == 1) 
    { 
     yield return source; 
    } 
    else if (count == 1) 
    { 
     for (var n = 0; n < source.Length; n++) 
     { 
      yield return source.Substring(n, 1); 
     } 
    } 
    else 
    { 
     for (var n = 0; n < source.Length; n++) 
      foreach (var suffix in Permutate(
       source.Substring(0, n) 
        + source.Substring(n + 1, source.Length - n - 1), count -1)) 
      { 
       yield return source.Substring(n, 1) + suffix; 
      } 
    } 
} 

它可与Permutate("ABCD", 2)被调用，返回此：

Answer 2

List<string> newPermutations = new List<string>(); 
for(int a = 0; a!=inString.Count; a++) 
    for((int b = 0; b!=inString.Count; b++) 
     if(noRepetitions && a == b) continue; 
     newPermutations.Add(""+inString[a] + inString[b]); 

我认为这应该工作;我仍然试图找出一种不仅有2个字母的方法。

编辑：编辑它的工作，旧的只是没有工作...笑 编辑：感谢@Bloopy，他们帮助我发现在我的for循环

Answer 3

我做了下面的递归一些错误功能，完成你的任务：

static void Permutations(List<string> output, string str, int n, string curr) 
    { 
     if(curr.Length == n) 
     { 
      output.Add(curr); 
      return; 
     } 
     foreach(char c in str) 
      if(!curr.Contains(c.ToString())) 
       Permutations(output, str, n, curr + c.ToString()); 
    } 

然后调用它像这样：

string str = "ABCD"; 
int length = 2; 
List<string> perms = new List<string>(); 
Permutations(perms, str, length, ""); 
// now the list "perms" will contain the permutations of "str" in length "n" 

Answer 4

下面是使用模和除法的解决方案。有4个可能的长度为2的字符串，使用字母ABCD。将它们编号从0到4 2 -1，并将每个数字重复除以4.将所得的余数用作ABCD字符串上的数组索引。

这有让您保持琴弦与重复的元素（AA，BB，CC，DD）在需要时的优势 - 只是跳过丢弃步骤。

string alphabet = "ABCD"; 
int length = 2; 

int[] indexes = new int[length]; 
char[] item = new char[length]; 

// loop through all possible strings for the given alphabet and length 
for (int i = 0; i < Math.Pow(alphabet.Length, length); i++) { 

    int dividend = i; 
    for (int j = length - 1; j >= 0; j--) { 
     indexes[j] = dividend % alphabet.Length; 
     dividend /= alphabet.Length; 
    } 

    // discard any that use the same alphabet element more than once 
    if (indexes.Distinct().Count() < length) 
     continue; 

    for (int k = 0; k < length; k++) { 
     item[k] = alphabet[indexes[k]]; 
    } 

    Console.WriteLine(item); 
} 

另外，这里是一个非常简单的使用LINQ的解决方案。请注意，如果字符串中存在重复的元素，则不能正确工作（除非您想要移除对Where的呼叫并保留AA，BB等）。我需要像上面我的方法那样跟踪索引。

IEnumerable<string> prm = alphabet.Select(c => c.ToString()); 
for (int a = 1; a < length; a++) 
    prm = prm.SelectMany(s => alphabet.Where(t => !s.Contains(t)), (x, y) => x + y); 

foreach (string s in prm) 
    Console.WriteLine(s);