Hai bisogno di un algoritmo per realizzare un programma semplice (permutazioni della frase)

Non riesco davvero a capire come creare un semplice algoritmo su C # per risolvere il mio problema. Quindi, abbiamo una frase:

{Hello|Hi|Hi-Hi} my {mate|m8|friend|friends}. 

Quindi, il mio programma dovrebbe fare un sacco di frasi come:

 Hello my mate. Hello my m8. Hello my friend. Hello my friends. Hi my mate. ... Hi-Hi my friends. 

Lo so, ci sono molti programmi che potrebbero farlo, ma mi piacerebbe farlo da solo. Ovviamente, dovrebbe funzionare anche con questo:

 {Hello|Hi|Hi-Hi} my {mate|m8|friend|friends}, {i|we} want to {tell|say} you {hello|hi|hi-hi}. 

Update I non era troppo contento di usare la regexen per analizzare un input così semplice; tuttavia non mi piaceva la giungla di manipolazione dell’indice manuale trovata in altre risposte.

Così ho sostituito la tokenizzazione con uno scanner basato su enumeratore con due stati token alternati . Ciò è più giustificato dalla complessità dell’input e ha un aspetto ‘Linqy’ (anche se in realtà non è Linq). Ho mantenuto il parser originale basato su Regex alla fine del mio post per i lettori interessati.


Questo doveva essere risolto utilizzando il metodo di estensione Linq CartesianProduct di Eric Lippert / IanG , in cui il nucleo del programma diventa:

 public static void Main(string[] args) { const string data = @"{Hello|Hi|Hi-Hi} my {mate|m8|friend|friends}, {i|we} want to {tell|say} you {hello|hi|hi-hi}."; var pockets = Tokenize(data.GetEnumerator()); foreach (var result in CartesianProduct(pockets)) Console.WriteLine(string.Join("", result.ToArray())); } 

Usando solo due regexen ( chunks e legs ) per fare l’analisi in ” pockets “, diventa una questione di scrivere il CartesianProduct alla console 🙂 Ecco il codice completo funzionante (.NET 3.5+):

 using System; using System.Text; using System.Text.RegularExpressions; using System.Linq; using System.Collections.Generic; namespace X { static class Y { private static bool ReadTill(this IEnumerator input, string stopChars, Action action) { var sb = new StringBuilder(); try { while (input.MoveNext()) if (stopChars.Contains(input.Current)) return true; else sb.Append(input.Current); } finally { action(sb); } return false; } private static IEnumerable> Tokenize(IEnumerator input) { var result = new List>(); while(input.ReadTill("{", sb => result.Add(new [] { sb.ToString() })) && input.ReadTill("}", sb => result.Add(sb.ToString().Split('|')))) { // Console.WriteLine("Expected cumulative results: " + result.Select(a => a.Count()).Aggregate(1, (i,j) => i*j)); } return result; } public static void Main(string[] args) { const string data = @"{Hello|Hi|Hi-Hi} my {mate|m8|friend|friends}, {i|we} want to {tell|say} you {hello|hi|hi-hi}."; var pockets = Tokenize(data.GetEnumerator()); foreach (var result in CartesianProduct(pockets)) Console.WriteLine(string.Join("", result.ToArray())); } static IEnumerable> CartesianProduct(this IEnumerable> sequences) { IEnumerable> emptyProduct = new[] { Enumerable.Empty() }; return sequences.Aggregate( emptyProduct, (accumulator, sequence) => from accseq in accumulator from item in sequence select accseq.Concat(new[] {item})); } } } 

Analisi basata su vecchio Regex:

 static readonly Regex chunks = new Regex(@"^(?{.*?}|.*?(?={|$))+$", RegexOptions.Compiled); static readonly Regex legs = new Regex(@"^{((?.*?)[\|}])+(?<=})$", RegexOptions.Compiled); private static IEnumerable All(this Regex regex, string text, string group) { return !regex.IsMatch(text) ? new [] { text } : regex.Match(text).Groups[group].Captures.Cast().Select(c => c.Value); } public static void Main(string[] args) { const string data = @"{Hello|Hi|Hi-Hi} my {mate|m8|friend|friends}, {i|we} want to {tell|say} you {hello|hi|hi-hi}."; var pockets = chunks.All(data, "chunk").Select(v => legs.All(v, "alternative")); 

Il resto è invariato

Non sei sicuro di cosa hai bisogno Linq (@ user568262) o ricorsione “semplice” (@Azad Salahli) per. Ecco la mia opinione su questo:

 using System; using System.Text; class Program { static Random rng = new Random(); static string GetChoiceTemplatingResult(string t) { StringBuilder res = new StringBuilder(); for (int i = 0; i < t.Length; ++i) if (t[i] == '{') { int j; for (j = i + 1; j < t.Length; ++j) if (t[j] == '}') { if (j - i < 1) continue; var choices = t.Substring(i + 1, j - i - 1).Split('|'); res.Append(choices[rng.Next(choices.Length)]); i = j; break; } if (j == t.Length) throw new InvalidOperationException("No matching } found."); } else res.Append(t[i]); return res.ToString(); } static void Main(string[] args) { Console.WriteLine(GetChoiceTemplatingResult( "{Hello|Hi|Hi-Hi} my {mate|m8|friend|friends}, {i|we} want to {tell|say} you {hello|hi|hi-hi}.")); } } 

Come altri hanno notato, puoi risolvere il tuo problema suddividendo la stringa in una sequenza di insiemi e poi prendendo il prodotto cartesiano di tutti questi set. Ho scritto un po ‘su come generare prodotti cartesiani arbitrari qui:

http://blogs.msdn.com/b/ericlippert/archive/2010/06/28/computing-a-cartesian-product-with-linq.aspx

Un approccio alternativo, più potente di quello, è quello di dichiarare una grammatica per la tua lingua e quindi scrivere un programma che generi ogni stringa in quella lingua. Ho scritto una lunga serie di articoli su come farlo. Inizia qui:

http://blogs.msdn.com/b/ericlippert/archive/2010/04/26/every-program-there-is-part-one.aspx

È ansible utilizzare una tupla per contenere i valori dell’indice di ogni raccolta.

Ad esempio, avresti qualcosa come:

 List Greetings = new List() { "Hello", "Hi", "Hallo" }; List Targets = new List() { "Mate", "m8", "friend", "friends" }; 

Quindi ora hai i tuoi saluti, creiamo numeri casuali e recuperiamo gli oggetti.

 static void Main(string[] args) { List Greetings = new List() { "Hello", "Hi", "Hallo" }; List Targets = new List() { "Mate", "m8", "friend", "friends" }; var combinations = new List>(); Random random = new Random(); //Say you want 5 unique combinations. while (combinations.Count < 6) { Tuple tmpCombination = new Tuple(random.Next(Greetings.Count), random.Next(Targets.Count)); if (!combinations.Contains(tmpCombination)) { combinations.Add(tmpCombination); } } foreach (var item in combinations) { Console.WriteLine("{0} my {1}", Greetings[item.Item1], Targets[item.Item2]); } Console.ReadKey(); } 

Questo non sembra banale. Devi
1. fai un po ‘di analisi, per estrarre tutti gli elenchi di parole che vuoi combinare,
2. ottenere tutte le combinazioni effettive di queste parole (il che è reso più difficile dal fatto che il numero di liste che si desidera combinare non è fisso)
3. ribuild la frase originale mettendo tutte le combinazioni nel luogo del gruppo da cui provengono

la parte 1 (la parte di parsing) è probabilmente la più semplice: potrebbe essere fatta con un Regex come questo

  // get all the text within {} pairs var pattern = @"\{(.*?)\}"; var query = "{Hello|Hi|Hi-Hi} my {mate|m8|friend|friends}."; var matches = Regex.Matches(query, pattern); // create a List of Lists for(int i=0; i< matches.Count; i++) { var nl = matches[i].Groups[1].ToString().Split('|').ToList(); lists.Add(nl); // build a "template" string like "{0} my {1}" query = query.Replace(matches[i].Groups[1].ToString(), i.ToString()); } 

per la parte 2 (prendendo una lista di liste e ottenendo tutte le combinazioni risultanti) è ansible fare riferimento a questa risposta

per la parte 3 (ricostruendo la frase originale) ora puoi prendere la stringa "template" che hai nella query e usare String.Format per sostituire tutti i {0}, {1} .... con i valori combinati dalla parte 2

 // just one example, // you will need to loop through all the combinations obtained from part 2 var OneResultingCombination = new List() {"hi", "mate"}; var oneResult = string.Format(query, OneResultingCombination.ToArray());