检查文件中是否包含排列 [英] Check if permutations are contained in a file
本文介绍了检查文件中是否包含排列的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
快速提问。
我正在编写一个程序来查找我在应用程序中输入的一组字符的所有排列。
此部分完美的工作。
我的问题是我需要检查字符的所有排列与我用作字典的文本文件。
Ex。如果我输入字符TSTE，输出givin是tset，ttse，ttes，tets，test，stte，stet，sett ...
我只想打印有效的单词，如tset，sett，stet ，测试，毒鼠强。其中ttse，ttes，stte没有打印。
我到目前为止的代码如下。
我一直在过去几天我的双桨的边缘似乎无法找到办法。
如果有什么可以看到我错过了吗？
谢谢
静态 < span class =code-keyword> void Main（ string [] args）
{
Console.BufferHeight = Int16 .MaxValue - 1 ;
Console.WindowHeight = 40 ;
Console.WindowWidth = 120 ;
Permute p = new Permute（）;
var d = Read（）;
string 行;
string str = System.IO.File.ReadAllText（ Dictionary.txt）;
while （（line = Console.ReadLine（））！= null ）
{
char [] c2 = line.ToArray（）;
p.setper（c2）;
}
}
静态字典<字符串，字符串> Read（）
{
var d = new Dictionary< string，string> （）;
使用（StreamReader sr = new StreamReader（ Dictionary.txt））
{
string 行;
while （（line = sr.ReadLine（））！= null ）
{
string a = Alphabet（line）;
string v;
if （d.TryGetValue（a， out v））
{
d [a] = v + ， + line;
}
else
{
d.Add（a，line）;
}
}
}
返回 d;
}
静态 字符串字母（ string s）
{
char [] a = s.ToCharArray（）;
Array.Sort（a）;
return new string （一个）;
}
静态 void 显示（字典<字符串，字符串> d，< span class =code-keyword> string w）
{
string v;
if （d.TryGetValue（Alphabet（w）， out v））
{
Console.WriteLine（v）;
}
else
{
Console.WriteLine（ -----------）;
}
}
}
class 置换
{
private void swap（ ref char a， ref char b）
{
< span class =code-keyword> if （a == b） return ;
a ^ = b;
b ^ = a;
a ^ = b;
}
public void setper（ char [] list）
{
int x = list.Length - 1 ;
go（list， 0 ，x）;
}
public void go（ char [] list1， int k， int m）
{
if （k == m）
{
Console.WriteLine（list1）;
Console.WriteLine（ ）;
}
else
{
for （ int i = k; i < = m; i ++）
{
swap（ ref list1 [k]， ref list1 [i]）;
go（list1，k + 1 ，m）;
swap（ ref list1 [k]， ref list1 [i]）;
}
}
}
解决方案
正如我所看到的，你正在采取最艰难的方式。如果两个字符串包含相同数量的相同字符，则字符串是另一个字符串的排列。由于p（x）= x！，它可能会变得疯狂：10个字符长的字符串有3.628.800个排列。有了20，你得到2.432.902.008.176.640.000！你有足够的记忆和时间吗？考虑一下递归...我想文件本身会相当短......
所以一般来说检查一个单词是否是另一个单词的排列比制作所有单词更便宜排列，存储它们，并尝试匹配所有这些。看看上面的数字！
查看以下代码：
使用系统;
使用 System.Linq;
使用 System.Collections.Specialized;
使用 System.IO;
命名空间 MyNetstat
{
class Program
{
static bool isPermutation（ string s1， string s2）
{
var _s2 = s2.ToCharArray（）;
Array.Sort（_s2）;
foreach （ var c in s1）
{
int i = Array.IndexOf（_s2，c）;
if （i < 0 ）
{
return false ;
}
_s2 [i] =（ char ） 0 ;
}
return ！_s2.Any（x = > x！=（ char ） 0 ）;
}
static StringCollection ParseFile（ string filename， string test）
{
var result = new StringCollection（）;
string 行;
StreamReader file = new StreamReader（ @ d：\temp\dictionary.txt）;
while （（line = file.ReadLine（））！= null ）
{
if （isPermutation（line，test））
{
result.Add（line）;
}
}
file.Close（）;
返回结果;
}
public static void Main（）
{
string test;
Console.Write（ 输入要测试的单词：）;
test = Console.ReadLine（）;
if （！string.IsNullOrWhiteSpace（test））
{
foreach （ string s in ParseFile（ Dictionary.txt，test））
{
Console.WriteLine（s）;
}
}
else
{
Console.WriteLine（ 无法测试空字符串！）;
}
}
}
}
BTW：你为什么需要从文件中创建字典，以及为什么< string，string>？
如果你喜欢密码，这里有咀嚼的东西;-)
static IEnumerable< string> Perm（ int n， char [] items）
{
return （++ n < items.Length）
？ 来自 c 项来自 s 中的class =code-keyword> Perm（n，items）选择 c + s
：来自 c 项选择 c.ToString（）;
}
静态 void Main（ string [] args）
{
// dict ：一行中的每个单词（前导空格和尾随空格都被删除）
string dictFile = @ c：\ temp \ dict.txt;
var dict = new HashSet< string>（File.ReadAllLines（dictFile）.Select（ S => s.ToLower（）修剪（）））。
var input = Console.ReadLine（）。ToLower（）。ToCharArray（）;
var words = Perm（ 0 ，输入）。其中（p = > dict.Contains（p））。Distinct（）;
Console.WriteLine（ string .Join（ \ n，words））;
}
不要使用上述内容，这是正确的，但速度很慢。对于新的解决方案，请参阅下面的EDIT2。
一种更明智的方法是为了避免排列和以下（再次密集;-)）：
静态 < span class =code-keyword> void Main（ string [] args）
{
string dictFile = @ c：\ temp\dict.txt;
var dict = new HashSet< string>（File.ReadAllLines（dictFile）.Select（ S => s.ToLower（）修剪（）））。
var input = Console.ReadLine（）。ToLower（）。ToCharArray（）;
var words = dict.Where（d = > d.Length = = input.Length&& d.All（c = > input.Contains（c）））;
Console.WriteLine（ string .Join（ \ n，words））;
}
[/编辑]
不要用那个因为它计算每个字符位置的排列而不是字符串，例如eeee不是tste的排列。对于新的解决方案，请参阅下面的EDIT2。
这需要适当的排列。
static void Main（ string [] args）
{
var input = new string （Console.ReadLine（）。ToLower（）。OrderBy（c => c）。ToArray（））;
string dictFile = @ C：\temp\dict.txt;
var dict = new HashSet< string>（File.ReadAllLines（dictFile）.Where（ s => s.Length == input.Length）.Select（s => s.ToLower（）））;
var words = 来自 d dict 其中 d.Length == input.Length&& new string （d.OrderBy（c => c）.ToArray（））== input < span class =code-sdkkeyword>选择 d;
Console.WriteLine（ string .Join（ \ n，words））;
}
[/ EDIT2]
干杯
Andi
您好，
目前您只计算置换值，但您没有将它们与字典中的值进行比较。
在你的行中说
Console.WriteLine（list1）;
你需要将它们保存在某个地方，一旦完成所有排列，将列表与你的字典进行比较并打印出来。
问候
Jegan
Hey guys.
Quick question.
I am writing a program to find all the permutations of a set of characters I input into the application.
This part works perfectly.
My problem is that I need to check all the permutations of the characters against a text file I use as a dictionary.
Ex. If I input the characters TSTE the outputs givin are tset,ttse,ttes,tets,test,stte,stet,sett...
I only want to print the valid words like tset,sett,stet,test,tets. where ttse,ttes,stte is not printed.
The code I have so far is as follows.
I have been scracthing at the edges of my scull for the past few days and just cant seem to find a way to do it.
Please if there is anything you can see that I have missed?
Thank you
static void Main(string[] args)
{
Console.BufferHeight = Int16.MaxValue - 1;
Console.WindowHeight = 40;
Console.WindowWidth = 120;
Permute p = new Permute();
var d = Read();
string line;
string str = System.IO.File.ReadAllText("Dictionary.txt");
while ((line = Console.ReadLine()) != null)
{
char[] c2 = line.ToArray();
p.setper(c2);
}
}
static Dictionary<string, string> Read()
{
var d = new Dictionary<string, string>();
using (StreamReader sr = new StreamReader("Dictionary.txt"))
{
string line;
while ((line = sr.ReadLine()) != null)
{
string a = Alphabet(line);
string v;
if (d.TryGetValue(a, out v))
{
d[a] = v + "," + line;
}
else
{
d.Add(a, line);
}
}
}
return d;
}
static string Alphabet(string s)
{
char[] a = s.ToCharArray();
Array.Sort(a);
return new string(a);
}
static void Show(Dictionary<string, string> d, string w)
{
string v;
if (d.TryGetValue(Alphabet(w), out v))
{
Console.WriteLine(v);
}
else
{
Console.WriteLine("-----------");
}
}
}
class Permute
{
private void swap(ref char a, ref char b)
{
if (a == b) return;
a ^= b;
b ^= a;
a ^= b;
}
public void setper(char[] list)
{
int x = list.Length - 1;
go(list, 0, x);
}
public void go(char[] list1, int k, int m)
{
if (k == m)
{
Console.WriteLine(list1);
Console.WriteLine(" ");
}
else
{
for (int i = k; i <= m; i++)
{
swap(ref list1[k], ref list1[i]);
go(list1, k + 1, m);
swap(ref list1[k], ref list1[i]);
}
}
} 解决方案
As I see, you are taking the hardest way. A string is the permutation of an other if both contain the same characters in the same amount. Asp(x)=x!, it can go wild: there are 3.628.800 permutations of a 10 character long string. With 20 you get 2.432.902.008.176.640.000! Do you have enough memory and time? Think about the recursion too... I suppose the file itself will be considerably shorter...
So in general it is cheaper to check if a word is a permutation of an other, than to generate all permutations, store them, and try to match all of them. Look at the figures above!
Look at following code:
using System; using System.Linq; using System.Collections.Specialized; using System.IO; namespace MyNetstat { class Program { static bool isPermutation(string s1, string s2) { var _s2 = s2.ToCharArray(); Array.Sort(_s2); foreach(var c in s1) { int i = Array.IndexOf(_s2,c); if(i < 0) { return false; } _s2[i] = (char)0; } return !_s2.Any(x => x != (char)0); } static StringCollection ParseFile(string filename, string test) { var result = new StringCollection(); string line; StreamReader file = new StreamReader(@"d:\temp\dictionary.txt"); while((line = file.ReadLine()) != null) { if(isPermutation(line, test)) { result.Add(line); } } file.Close(); return result; } public static void Main() { string test; Console.Write("Enter word to test for: "); test = Console.ReadLine(); if(!string.IsNullOrWhiteSpace(test)) { foreach(string s in ParseFile("Dictionary.txt", test)) { Console.WriteLine(s); } } else { Console.WriteLine("Can not test for empty string!"); } } } }
BTW: why do you need to make dictionary from the file, and why <string,string>?
If you like dense code, here is something to chew ;-)
static IEnumerable<string> Perm(int n, char[] items) { return (++n < items.Length) ? from c in items from s in Perm(n, items) select c + s : from c in items select c.ToString(); } static void Main(string[] args) { // dict: each word in one line (leading and trailing spaces get removed) string dictFile = @"c:\temp\dict.txt"; var dict = new HashSet<string>(File.ReadAllLines(dictFile).Select(s=>s.ToLower().Trim())); var input = Console.ReadLine().ToLower().ToCharArray(); var words = Perm(0, input).Where(p => dict.Contains(p)).Distinct(); Console.WriteLine(string.Join("\n", words)); }
Don''t use the above, it''s correct but dedly slow. For the new solution see EDIT2 below.
[EDIT]
A more sensible approach was to avoid permutations at all and to the following (dense again ;-)):
static void Main(string[] args) { string dictFile = @"c:\temp\dict.txt"; var dict = new HashSet<string>(File.ReadAllLines(dictFile).Select(s=>s.ToLower().Trim())); var input = Console.ReadLine().ToLower().ToCharArray(); var words = dict.Where(d => d.Length == input.Length && d.All(c => input.Contains(c))); Console.WriteLine(string.Join("\n", words)); }
[/EDIT]
Don''t use that above since it calculates permutation per character position rather than by string, e.g.eeeeis not a permutation oftste. For the new solution see EDIT2 below.
[EDIT2]
This takes care of proper permutations.
static void Main(string[] args) { var input = new string(Console.ReadLine().ToLower().OrderBy(c=>c).ToArray()); string dictFile = @"c:\temp\dict.txt"; var dict = new HashSet<string>(File.ReadAllLines(dictFile).Where(s=>s.Length == input.Length).Select(s=>s.ToLower())); var words = from d in dict where d.Length==input.Length && new string(d.OrderBy(c=>c).ToArray())==input select d; Console.WriteLine(string.Join("\n", words)); }
[/EDIT2]
Cheers
Andi
Hi,
At the moment you are only calculating the permuted values, but you are not comparing them with the values in your dictionary.
In your line where it says
Console.WriteLine(list1);
you need to keep them saved somewhere, once all the permutation finished, compare the list with your dictionary and print them out.
Regards
Jegan
这篇关于检查文件中是否包含排列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
