Génération de toutes les variations d'une certaine longueur en chaîne

Question

J'ai vu peu d'implémentations de variations de chaînes en C#, mais aucune d'entre elles n'avait de limitation sur leur longueur. Malheureusement, je ne peux pas les modifier pour atteindre mon objectif qui est par ex.

pour:

string = "ABCD" and variationLength = 2 

générer de nouvelles chaînes:

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

Je cherche exactement itertools.permutations de cette Python mise en œuvre, mais en C#. (https://docs.python.org/3/library/itertools.html#itertools.permutations)

Y a-t-il quelque chose de similaire à son en C#? Si non, alors quel est le moyen le plus facile à mettre en œuvre?

Edit_2: jusqu'à présent je suis venu avec une idée de lister tous les caractères uniques de chaîne donnée, puis obtenir des variations sur les

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);  
} 

Cependant, je suis à la recherche d'une solution plus optimale et efficace

Answer 1

est ici une méthode de permutation vraiment récursive:

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; 
      } 
    } 
} 

Il peut être appelé avec Permutate("ABCD", 2), et renvoie ceci:

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]); 

Je pense que cela devrait fonctionner; J'essaie toujours de trouver un moyen d'avoir non seulement 2 lettres.

Edit: Sous la direction à travailler, l'ancien n'a pas marché ... lol Edit: Merci à @Bloopy, ils me ont aidé apercevoir quelques erreurs dans mon boucles pour

Answer 3

J'ai fait la récursive suivante fonction qui accomplit votre tâche:

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()); 
    } 

puis vous l'appelez comme ceci:

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

Voici une solution en utilisant modulo et la division. Il y a 4² chaînes possibles de longueur 2 utilisant les lettres ABCD. Numérotez-les de 0 à 4²-1 et divisez chaque nombre de façon répétée par 4. Utilisez les restants obtenus comme index de tableau sur la chaîne ABCD. Ceci a l'avantage de vous permettre de conserver les cordes avec des éléments répétés (AA, BB, CC, DD) si nécessaire - il vous suffit d'ignorer l'étape de rejet.

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); 
} 

Alternativement, voici une solution très brève utilisant LINQ. Notez que celui-ci ne fonctionne pas correctement s'il y a des éléments en double dans la chaîne (sauf si vous voulez supprimer l'appel à Where et conserver l'AA, le BB, etc.). Je devrais suivre les index comme je l'ai fait dans ma méthode ci-dessus.

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);