Une tâche courante dans les entretiens de programmation (ce n'est pas mon expérience des entretiens) consiste à prendre une chaîne de caractères ou un nombre entier et à énumérer toutes les permutations possibles.
Existe-t-il un exemple de la manière de procéder et de la logique qui sous-tend la résolution d'un tel problème ?
J'ai vu quelques extraits de code mais ils n'étaient pas bien commentés/expliqués et donc difficiles à suivre.
Voici la fonction qui va imprimer toutes les permutations. Cette fonction implémente la logique Expliqué par peter.
public class Permutation
{
//http://www.java2s.com/Tutorial/Java/0100__Class-Definition/RecursivemethodtofindallpermutationsofaString.htm
public static void permuteString(String beginningString, String endingString)
{
if (endingString.Length <= 1)
Console.WriteLine(beginningString + endingString);
else
for (int i = 0; i < endingString.Length; i++)
{
String newString = endingString.Substring(0, i) + endingString.Substring(i + 1);
permuteString(beginningString + endingString.ElementAt(i), newString);
}
}
}
static void Main(string[] args)
{
Permutation.permuteString(String.Empty, "abc");
Console.ReadLine();
}
Voici mon implémentation de la permutation. Ne faites pas attention aux noms des variables, car je l'ai fait pour le plaisir :)
class combinations
{
static void Main()
{
string choice = "y";
do
{
try
{
Console.WriteLine("Enter word :");
string abc = Console.ReadLine().ToString();
Console.WriteLine("Combinatins for word :");
List<string> final = comb(abc);
int count = 1;
foreach (string s in final)
{
Console.WriteLine("{0} --> {1}", count++, s);
}
Console.WriteLine("Do you wish to continue(y/n)?");
choice = Console.ReadLine().ToString();
}
catch (Exception exc)
{
Console.WriteLine(exc);
}
} while (choice == "y" || choice == "Y");
}
static string swap(string test)
{
return swap(0, 1, test);
}
static List<string> comb(string test)
{
List<string> sec = new List<string>();
List<string> first = new List<string>();
if (test.Length == 1) first.Add(test);
else if (test.Length == 2) { first.Add(test); first.Add(swap(test)); }
else if (test.Length > 2)
{
sec = generateWords(test);
foreach (string s in sec)
{
string init = s.Substring(0, 1);
string restOfbody = s.Substring(1, s.Length - 1);
List<string> third = comb(restOfbody);
foreach (string s1 in third)
{
if (!first.Contains(init + s1)) first.Add(init + s1);
}
}
}
return first;
}
static string ShiftBack(string abc)
{
char[] arr = abc.ToCharArray();
char temp = arr[0];
string wrd = string.Empty;
for (int i = 1; i < arr.Length; i++)
{
wrd += arr[i];
}
wrd += temp;
return wrd;
}
static List<string> generateWords(string test)
{
List<string> final = new List<string>();
if (test.Length == 1)
final.Add(test);
else
{
final.Add(test);
string holdString = test;
while (final.Count < test.Length)
{
holdString = ShiftBack(holdString);
final.Add(holdString);
}
}
return final;
}
static string swap(int currentPosition, int targetPosition, string temp)
{
char[] arr = temp.ToCharArray();
char t = arr[currentPosition];
arr[currentPosition] = arr[targetPosition];
arr[targetPosition] = t;
string word = string.Empty;
for (int i = 0; i < arr.Length; i++)
{
word += arr[i];
}
return word;
}
}
Voici un exemple de haut niveau que j'ai écrit et qui illustre l'approche de la le langage humain l'explication donnée par Pierre :
public List<string> FindPermutations(string input)
{
if (input.Length == 1)
return new List<string> { input };
var perms = new List<string>();
foreach (var c in input)
{
var others = input.Remove(input.IndexOf(c), 1);
perms.AddRange(FindPermutations(others).Select(perm => c + perm));
}
return perms;
}
Cette solution est en fait imparfaite, car si le jeu de chaînes de caractères contient des caractères répétés, elle échouera. Par exemple, pour le mot "test", la commande Except supprimera les deux occurrences de "t" au lieu de la première et de la dernière si nécessaire.
//Generic C# Method
private static List<T[]> GetPerms<T>(T[] input, int startIndex = 0)
{
var perms = new List<T[]>();
var l = input.Length - 1;
if (l == startIndex)
perms.Add(input);
else
{
for (int i = startIndex; i <= l; i++)
{
var copy = input.ToArray(); //make copy
var temp = copy[startIndex];
copy[startIndex] = copy[i];
copy[i] = temp;
perms.AddRange(GetPerms(copy, startIndex + 1));
}
}
return perms;
}
//usages
char[] charArray = new char[] { 'A', 'B', 'C' };
var charPerms = GetPerms(charArray);
string[] stringArray = new string[] { "Orange", "Mango", "Apple" };
var stringPerms = GetPerms(stringArray);
int[] intArray = new int[] { 1, 2, 3 };
var intPerms = GetPerms(intArray);
J'espère que cela suffira :
using System;
public class Program
{
public static void Main()
{
//Example using word cat
permute("cat");
}
static void permute(string word){
for(int i=0; i < word.Length; i++){
char start = word[0];
for(int j=1; j < word.Length; j++){
string left = word.Substring(1,j-1);
string right = word.Substring(j);
Console.WriteLine(start+right+left);
}
if(i+1 < word.Length){
word = wordChange(word, i + 1);
}
}
}
static string wordChange(string word, int index){
string newWord = "";
for(int i=0; i<word.Length; i++){
if(i== 0)
newWord += word[index];
else if(i== index)
newWord += word[0];
else
newWord += word[i];
}
return newWord;
}sortie :
cat
cta
act
atc
tca
tac Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.
1 votes
Voici une question sur les permutations avec quelques bonnes réponses explicatives, y compris un graphique mais pas en C#.