JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
<< PREV    [ 1 2 ]
Re: Iterating Over All Permutations of an Array (response to post by Ferlon) | Reply
I think the discussion should have more emphasis in the best practice of using this kind of tool; Just like it is mentioned and used in the MatrixGame & TheLuckyString problems, we need to generate certain rules/filters to optimize the search. To look for all n! possibilities probably never will be a feasible solution. This is also called Combinatorial Explosion which verbatim refers to a growth almost impossible to sustain for the time of this type of TC problems.

So more important than the implementation ( which is assumed know -next_permutation()- that this is called Algorithm L in Knuth's TAOCP 4: 7.2.1.2) it is the good use some criteria for pruning combinations (permutations) and at the end we obtain a reasonable running time.

Many problems use this kind of booby-trap to let the programmer to try to solve with a plenty quick solution which runs over all permutations (or combinations) that finish with a timeout or an unnecessary overhead as resources used (such us memory).
Re: Iterating Over All Permutations of an Array (response to post by devwebcl) | Reply
That's right and that's because I mention that this algorithm fits only for small values of n. But, first, the recipe is named as it is named, and going to be the one for beginners; second, I don't know any general method of making cutting off in iterating over combinatorial objects - it's should be individual for every such problem; and third, problems where we need to do this are relatively rare in SRMs.
Re: Iterating Over All Permutations of an Array (response to post by devwebcl) | Reply
I don't think this recipe needs this. There are SRM problems which need just what the recipe says - iterating over all permutations. More advanced techniques are not universal, and we'll have recipes about them (namely "Constructing Combinatorial Objects" and "Finding the lexicographically K-th combinatorial object"), but this recipe is hardly a place for them.
Re: Iterating Over All Permutations of an Array (response to post by Ferlon) | Reply
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 NKolotey) | Reply
Thanks for the notice, I really forgot to mention the simplest algorithm for generating permutations. I've added it in the Discussion part of the recipe.
<< PREV    [ 1 2 ]

RSS