Check if permutations of characters are contained

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

标签： c# permutation

4条回答

时光不老，我们不散

2楼-- · 2019-09-03 14:58

Although for the valid words are as I mentioned in another answer, not possible with your current state, I've make the code pretty clear for you.

It finally the code, is separated in three parts. They are Permutable<T>, ConsoleHelper and the ConsoleApplication1.Program with an utility Permutation class.

Permutable<T> (Permutable.cs)

using System.Collections.Generic;
using System.Collections;
using System;

public partial class Permutable<T>: IEnumerable {
    public static explicit operator Permutable<T>(T[] array) {
        return new Permutable<T>(array);
    }

    static IEnumerable Permute<TElement>(IList<TElement> list, int depth, int count) {
        if(count==depth)
            yield return list;
        else {
            for(var i=depth; i<=count; ++i) {
                Swap(list, depth, i);

                foreach(var sequence in Permutable<T>.Permute(list, 1+depth, count))
                    yield return sequence;

                Swap(list, depth, i);
            }
        }
    }

    static void Swap<TElement>(IList<TElement> list, int depth, int index) {
        var local=list[depth];
        list[depth]=list[index];
        list[index]=local;
    }

    IEnumerator IEnumerable.GetEnumerator() {
        return this.GetEnumerator();
    }

    public IEnumerator<IList<T>> GetEnumerator() {
        var list=this.m_List;

        if(list.Count>0)
            foreach(IList<T> sequence in Permutable<T>.Permute(list, 0, list.Count-1))
                yield return sequence;
    }

    protected Permutable(IList<T> list) {
        this.m_List=list;
    }

    IList<T> m_List;
}

ConsoleHelper (ConsoleHelper.cs)

using System.Runtime.InteropServices;
using System.Windows.Forms;
using System.Drawing;

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

public static partial class ConsoleHelper {
    [StructLayout(LayoutKind.Sequential)]
    public struct RECT {
        public static explicit operator Rectangle(RECT rect) {
            return new Rectangle {
                X=rect.Left,
                Y=rect.Top,
                Width=rect.Right-rect.Left,
                Height=rect.Bottom-rect.Top
            };
        }

        public int Left;
        public int Top;
        public int Right;
        public int Bottom;
    }

    [DllImport("user32.dll", SetLastError=true)]
    static extern bool MoveWindow(IntPtr hWnd, int X, int Y, int Width, int Height, bool repaint);

    [DllImport("user32.dll", SetLastError=true)]
    static extern bool GetWindowRect(IntPtr hWnd, out RECT rect);

    [DllImport("kernel32.dll", SetLastError=true)]
    static extern IntPtr GetConsoleWindow();

    public static void CenterScreen() {
        RECT rect;
        var hWnn=ConsoleHelper.GetConsoleWindow();
        var workingArea=Screen.GetWorkingArea(Point.Empty);
        ConsoleHelper.GetWindowRect(hWnn, out rect);
        var rectangle=(Rectangle)rect;

        rectangle=
           new Rectangle {
               X=(workingArea.Width-rectangle.Width)/2,
               Y=(workingArea.Height-rectangle.Height)/2,
               Width=rectangle.Width,
               Height=rectangle.Height
           };

        ConsoleHelper.MoveWindow(
            hWnn,
            rectangle.Left, rectangle.Top, rectangle.Width, rectangle.Height,
            true
            );
    }
}

ConsoleApplication1.Program & Permutation (Program.cs)

using System.Collections;
using System.IO;

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

public partial class Permutation {
    public static Permutation FromFile(String path) {
        return new Permutation(path);
    }

    public static String GetSortedAlphabet(String text) {
        var array=text.ToArray();
        Array.Sort(array);
        return new String(array);
    }

    public Dictionary<String, String> Dictionary {
        private set;
        get;
    }

    public FileInfo SourceFile {
        private set;
        get;
    }

    public Permutation(String path) {
        this.Dictionary=(
            from line in File.ReadAllLines(path)
            where false==String.IsNullOrEmpty(line)
            group line by Permutation.GetSortedAlphabet(line) into g
            select
                new {
                    Value=String.Join(", ", g.Distinct().ToArray()),
                    Key=g.Key
                }
            ).ToDictionary(x => x.Key, x => x.Value);

        this.SourceFile=new FileInfo(path);
    }
}

namespace ConsoleApplication1 {
    partial class Program {
        static void ProcessLine(IList<char> input) {
            Console.WriteLine();

            if(input.Count>0) {
                var inputArray=input.ToArray();
                var key=Permutation.GetSortedAlphabet(new String(inputArray));
                var dict=Program.Permutation.Dictionary;
                var hasKey=dict.ContainsKey(key);
                var source=Permutation.SourceFile;

                Console.WriteLine("Possible permutations are: ");

                foreach(var sequence in (Permutable<char>)inputArray)
                    Console.WriteLine("{0}", new String(sequence.ToArray()));

                Console.WriteLine("Acceptable in file '{0}' are: ", source.FullName);
                Console.WriteLine("{0}", hasKey?dict[key]:"<none>");
                Console.WriteLine();

                input.Clear();
            }

            Console.Write(Prompt);
        }

        static void ProcessChar(IList<char> input, char keyChar) {
            Console.Write(keyChar);
            input.Add(keyChar);
        }

        static void ProcessExit(IList<char> input, char keyChar) {
            Console.WriteLine();
            Console.Write("Are you sure to exit? (Press Esc again to exit)");
            input.Add(keyChar);
        }

        static bool ProcessLast(IList<char> input, char keyChar) {
            var last=input.Count-1;

            if(0>last||input[last]!=(char)ConsoleKey.Escape)
                return false;

            input.Clear();
            return true;
        }

        public static Permutation Permutation {
            private set;
            get;
        }

        public static String Prompt {
            private set;
            get;
        }
    }

    partial class Program {
        static void Main(String[] args) {
            Console.BufferHeight=short.MaxValue-1;
            Console.SetWindowSize(120, 40);
            ConsoleHelper.CenterScreen();

            var input=new List<char>(char.MaxValue);
            Program.Permutation=Permutation.FromFile(@"c:\dictionary.txt");
            Program.Prompt="User>\x20";
            Program.ProcessLine(input);

            for(; ; ) {
                var keyInfo=Console.ReadKey(true);
                var keyChar=keyInfo.KeyChar;
                var keyCode=keyInfo.Key;

                if(ConsoleKey.Escape==keyCode) {
                    if(Program.ProcessLast(input, keyChar))
                        break;

                    Program.ProcessExit(input, keyChar);
                    continue;
                }

                if(ConsoleKey.Enter==keyCode) {
                    Program.ProcessLine(input);
                    continue;
                }

                if(default(ConsoleModifiers)!=keyInfo.Modifiers)
                    continue;

                if(0x1f>keyChar||keyChar>0x7f)
                    continue;

                if(Program.ProcessLast(input, keyChar))
                    Console.WriteLine();

                Program.ProcessChar(input, keyChar);
            }
        }
    }
}

The ConsoleHelper class is only use for ceteral your resized console window, that you can test the program more comfortable. The Permutable class is what I fully re-designed from your original class; it now come with IEnumerable to permute, and also a generic class.

The Permutation class, is like a utility class, itself provide a FromFile method as your original Read, and stores the Dictionary<String, String> as a property. The original method Alphabet is renamed GetSortedAlphabet for more semantical.

The Program class has four main static ProcessXXX methods, they are

ProcessChar: processes for a char of the range from 0x20 to 0x7f
ProcessLine: processes for Enter pressed
ProcessExit: processes for Excape pressed
ProcessLast: additional processing for ProcessLine and ProcessExit

Yes, I meant to make them have the same length of name. For more, Program class have two static properties; Permutation for storing a instance of class Permutation, and Prompt is a string for prompting user.

When your input is not defined in "c:\dictionary.txt", the prompt of "Acceptable in file .." will get you "<none>".

The exit command is twice-Escape key press, you would see

Are you sure to exit? (Press Esc again to exit)

and if you press Enter or other keys, it back to the initial state.

That's all. Now it's time to discover the finally problem you've encountered. After you test with this program, you might describe you questions and issues more clearly.

Good luck!

0人赞添加讨论(0) 举报

仙女界的扛把子

3楼-- · 2019-09-03 15:09

Not possible with current state.

It's possible because

If the "dictionary.txt" was your input, then you did not define what are the valid words. You at leaset need another dictionary to define those valid words or an algorithm to decide what those are and what those are not.
If the input is from UI and "dictionary.txt" is the defined valid words, you don't need to the permute the input, just search the input from "dictionary.txt".

However, your Read method is improvable, like

static Dictionary<String, String> Read(String path) {
    return (
        from line in File.ReadAllLines(path)
        where false==String.IsNullOrEmpty(line)
        group line by Alphabet(line) into g
        select
            new {
                Value=String.Join(",", g.ToArray()),
                Key=g.Key
            }
        ).ToDictionary(x => x.Key, x => x.Value);
}

0人赞添加讨论(0) 举报

欢心

4楼-- · 2019-09-03 15:13

Thank you for all your feedback. I have finally figured it out and found a solution to the problem I was having. static void Main(string[] args) { Console.BufferHeight = Int16.MaxValue - 1;

        Console.WindowHeight = 40;
        Console.WindowWidth = 120;
        Console.WriteLine("Enter your caracters for the anagram: ");
        //var d = Read();
        string line;
        //string DictionaryInput = System.IO.File.ReadAllText("Dictionary.txt");
        while ((line = Console.ReadLine()) != null)
        {
            Console.WriteLine("Your results are: ");
            char[] charArray = line.ToArray();
            //Show(d, line);                    //Using this to check that words found are the correct words in the dictionary.
            setper(charArray);
            Console.WriteLine("-----------------------------------------DONE-----------------------------------------");
            Console.WriteLine("Enter your caracters for the anagram: ");
            File.Delete("Permutations.txt");
        }

    }



    static void swap(ref char a, ref char b)
    {
        if (a == b) return;
        a ^= b;
        b ^= a;
        a ^= b;
    }
    static void setper(char[] list)
    {
        int x = list.Length - 1;
        permuteWords(list, 0, x);
    }
    static void permuteWords(char[] list1, int k, int m)
    {

        if (k == m)
        {
            StreamWriter sw = new StreamWriter("Permutations.txt", true);
            sw.WriteLine(list1);
            sw.Close();
            Regex permutationPattern = new Regex(new string(list1));
            string[] permutations = File.ReadAllLines("Permutations.txt");
            Regex pattern = new Regex(new string(list1));
            string[] lines = File.ReadAllLines("Dictionary.txt");

            foreach (string line in lines)
            {
                var matches = pattern.Matches(line);
                if (pattern.ToString() == line)
                {
                    Console.WriteLine(line);
                }
            }
        }
        else
        {
            for (int i = k; i <= m; i++)
            {
                swap(ref list1[k], ref list1[i]);
                permuteWords(list1, k + 1, m);
                swap(ref list1[k], ref list1[i]);
            }
        }


    }

0人赞添加讨论(0) 举报

仙女界的扛把子

5楼-- · 2019-09-03 15:20

you just missed Show(d, line); i loop.

change like this.

while ((line = Console.ReadLine()) != null)
        {
            char[] c2 = line.ToArray();
            p.setper(c2);
            Console.WriteLine(" combinations which are in Dictionary are:");
            Show(d, line);

        }

then .. you didn't required dictionary

  use List<string> Dic=new List<string>();// declare it in globally

  Dic.add(line); //each line in dictionary

before printing each word

 if(Dic.contains(word))
   print it; 
 else{ //no printing }

0人赞添加讨论(0) 举报

Check if permutations of characters are contained

采纳回答

编辑标签

举报内容

检举类型

检举原因

检举说明(必填)

打开微信“扫一扫”，打开网页后点击屏幕右上角分享按钮

付费偷看金额在0.1-10元之间