JOIN
Get Time
forums  Revision History
Search My Post History  |  My Watches  |  User Settings
Forums TopCoder Cookbook Algorithm Competitions - Rewriting Phase Re: Iterating Over All Permutations of an Array Revision History (2 edits)
Re: Iterating Over All Permutations of an Array (response to post by Ferlon)
My five cents...


If items of array are from very small set, for example chars 'A'..'Z' of digits '0'..'9', there is seem to be more simple to understand algorithm: first group all same items and then recursively populate resulting array from first index to last. Sample code below

        static void sub(int[] counters, char[] word, int p)
        {
            if (p == word.Length)
                Console.WriteLine(word);
            else
 
            for (int i = 0; i < 26; i++)
                if (counters[i] > 0)
                {
                    counters[i]--;
                    word[p] = (char)(i + (int)'A');
                    sub(counters, word, p + 1);
                    counters[i]++;
                }
        }
 
        public static void generate(string s)
        {
            int[] counters = new int[26];
            for (int i = 0; i < s.Length; i++)
                counters[s[i] - 'A']++;
 
            char[] word = new char[s.Length];
            sub(counters, word, 0);
        }
 
        static void Main(string[] args)
        {
            generate("HELLO");
        }



Point of harvesting our generated resuts is Console.WriteLine(word); it is somewrere deep inside recursion. If it is required to bring it to top just to make code more readable, c# users can use IEnumerable yield technique:


        static IEnumerable<string> sub(int[] counters, char[] word, int p)
        {
            if (p == word.Length)
                yield return new string(word);
            else
 
            for (int i = 0; i < 26; i++)
                if (counters[i] > 0)
                {
                    counters[i]--;
                    word[p] = (char)(i + (int)'A');
                    foreach (string w in sub(counters, word, p + 1))
                        yield return w;
                    counters[i]++;
                }
        }
 
        public static IEnumerable<string> generate(string s)
        {
            int[] counters = new int[26];
            for (int i = 0; i < s.Length; i++)
                counters[s[i] - 'A']++;
 
            char[] word = new char[s.Length];
            foreach(string w in sub(counters, word, 0))
                yield return w;
        }
 
        static void Main(string[] args)
        {
            foreach(string w in generate("HELLO"))
                Console.WriteLine(w);
        }
Re: Iterating Over All Permutations of an Array (response to post by Ferlon)
My five cents...


If items of array are from very small set, for example chars 'A'..'Z' of digits '0'..'9', there is seem to be more simple to understand algorithm: first group all same items and then recursively populate resulting array from first index to last. Sample code below

        static void sub(int[] counters, char[] word, int p)
        {
            if (p == word.Length)
                Console.WriteLine(word);
            else
 
            for (int i = 0; i < 26; i++)
                if (counters[i] > 0)
                {
                    counters[i]--;
                    word[p] = (char)(i + (int)'A');
                    sub(counters, word, p + 1);
                    counters[i]++;
                }
        }
 
        public static void generate(string s)
        {
            int[] counters = new int[26];
            for (int i = 0; i < s.Length; i++)
                counters[s[i] - 'A']++;
 
            char[] word = new char[s.Length];
            sub(counters, word, 0);
        }
 
        static void Main(string[] args)
        {
            generate("HELLO");
        }



Point of harvesting our generated resuts is Console.WriteLine(word); it is somewrere deep inside recursion. If it is required to bring it into top just to make code more readable, c# users can use IEnumerable yield technique:


        static IEnumerable<string> sub(int[] counters, char[] word, int p)
        {
            if (p == word.Length)
                yield return new string(word);
            else
 
            for (int i = 0; i < 26; i++)
                if (counters[i] > 0)
                {
                    counters[i]--;
                    word[p] = (char)(i + (int)'A');
                    foreach (string w in sub(counters, word, p + 1))
                        yield return w;
                    counters[i]++;
                }
        }
 
        public static IEnumerable<string> generate(string s)
        {
            int[] counters = new int[26];
            for (int i = 0; i < s.Length; i++)
                counters[s[i] - 'A']++;
 
            char[] word = new char[s.Length];
            foreach(string w in sub(counters, word, 0))
                yield return w;
        }
 
        static void Main(string[] args)
        {
            foreach(string w in generate("HELLO"))
                Console.WriteLine(w);
        }
Re: Iterating Over All Permutations of an Array (response to post by Ferlon)
My five cents...


If items of array are from very small set, for example chars 'A'..'Z' of digits '0'..'9', there is seem to be more simple to understand algorithm: first group all same items and then recursively populate resulting array from first index to last. Sample code below

        static void sub(int[] counters, char[] word, int p)
        {
            if (p == word.Length)
                Console.WriteLine(word);
            else
 
            for (int i = 0; i < 26; i++)
                if (counters[i] > 0)
                {
                    counters[i]--;
                    word[p] = (char)(i + (int)'A');
                    sub(counters, word, p + 1);
                    counters[i]++;
                }
        }
 
        public static void generate(string s)
        {
            int[] counters = new int[26];
            for (int i = 0; i < s.Length; i++)
                counters[s[i] - 'A']++;
 
            char[] word = new char[s.Length];
            sub(counters, word, 0);
        }
 
        static void Main(string[] args)
        {
            generate("HELLO");
        }



Point of harvesting our generated resuts is Console.WriteLine(word); it is somewrere deep inside recursion. If it is required to bring it into top just to make code more readable, c# users can use IEnumerable yield technique:


        static IEnumerable<char[]> sub(int[] counters, char[] word, int p)
        {
            if (p == word.Length)
                yield return word;
            else
 
            for (int i = 0; i < 26; i++)
                if (counters[i] > 0)
                {
                    counters[i]--;
                    word[p] = (char)(i + (int)'A');
                    foreach (char[] w in sub(counters, word, p + 1))
                        yield return w;
                    counters[i]++;
                }
        }
 
        public static IEnumerable<char[]> generate(string s)
        {
            int[] counters = new int[26];
            for (int i = 0; i < s.Length; i++)
                counters[s[i] - 'A']++;
 
            char[] word = new char[s.Length];
            foreach(char[] w in sub(counters, word, 0))
                yield return w;
        }
 
        static void Main(string[] args)
        {
            foreach(char[] w in generate("HELLO"))
                Console.WriteLine(w);
        }