locked
Generating all possible combinations of a list of numbers.

    Question

  • I have a list of numbers that can have a lenght between 4 to 20 numbers.  I would like to generate every possible combination of these numbers.  (They will always be of equal length of the original list length and never smaller)  I would prefer not to use recursion...I am a bit worried about using up too much memory.  However I haven't completely made up my mind about that.

    Just to go into a bit more detail....after I generate a new list of numbers I will do a quick calculation and then I will no longer need that generated list.  Speed is of the essence too.

    Thanks!

    Wednesday, February 03, 2010 10:50 PM

Answers

  • Questions about permutations are popular lately. :)

    A recursive solution will be fine; its depth is limited to the number of items you are permuting so you'll die waiting for all the permutations long before you run out of stack space. ;)

    Here's a generic solution that uses recursion. It doesn't create a new collection for each permutation; instead, it creates one collection at the start and fills that with each permutation before calling an Output() method that you supply:

    using System;
    
    namespace ConsoleApplication1
    {
        static class Program
        {
            static void Main()
            {
                int[] numbers = new[]
                {
                    0, 1, 2, 3, 4
                };
    
                Permute(numbers, Output);
                Console.WriteLine();
    
                string[] strings = new[]
                {
                    "Red", "Orange", "Yellow", "Green", "Blue"
                };
    
                Permute(strings, Output);
                Console.WriteLine();
    
                Console.ReadLine();
            }
    
            private static void Output<T>(T[] permutation)
            {
                foreach (T item in permutation)
                {
                    Console.Write(item);
                    Console.Write(" ");
                }
    
                Console.WriteLine();
            }
    
            public static void Permute<T>(T[] items, Action<T[]> output)
            {
                Permute(items, 0, new T[items.Length], new bool[items.Length], output);
            }
    
            private static void Permute<T>(T[] items, int item, T[] permutation, bool[] used, Action<T[]> output)
            {
                for (int i = 0; i < items.Length; ++i)
                {
                    if (!used[i])
                    {
                        used[i] = true;
                        permutation[item] = items[i];
    
                        if (item < (items.Length - 1))
                        {
                            Permute(items, item + 1, permutation, used, output);
                        }
                        else
                        {
                            output(permutation);
                        }
    
                        used[i] = false;
                    }
                }
            }
        }
    }
    
    • Marked as answer by Lavagin Saturday, February 06, 2010 2:01 AM
    Thursday, February 04, 2010 9:49 AM
  • All the data used is passed into the method, and any additional data is created on the stack. Therefore multithreading should cause no problems as long as the array passed to the method is not changed by a different thread while the permutations are being generated.
    • Marked as answer by Lavagin Saturday, February 06, 2010 2:01 AM
    Thursday, February 04, 2010 1:47 PM

All replies

  • A few comments first:

    1) Are your numbers guaranteed to be different or can there be repetitions?

    2) Recursion is not an issue considering that you would go at most 20 levels deep. What you must be careful about instead is not creating new objects.

    3) Are you sure about your specs? Unless there are repetitions, the possible permutations of 20 numbers are exactly 20!, or 2,432,902,008,176,640,000. Even analyzing 1,000,000 permutations per second, your code would run for more than 77146 years.

    Thanks
    --mc
    Thursday, February 04, 2010 1:00 AM
  • Hello,

    1) Each number will be unique integer in list.  So if the original list is 10 integers in length, all of those integers will be unique.
    2) OK...I wouldn't need to create any new objects.
    3) Hmm ok.  Lets say the biggest number will be a list of 13 unique integers then.
    • Marked as answer by Lavagin Saturday, February 06, 2010 2:01 AM
    • Unmarked as answer by Lavagin Saturday, February 06, 2010 2:01 AM
    Thursday, February 04, 2010 1:04 AM
  • Questions about permutations are popular lately. :)

    A recursive solution will be fine; its depth is limited to the number of items you are permuting so you'll die waiting for all the permutations long before you run out of stack space. ;)

    Here's a generic solution that uses recursion. It doesn't create a new collection for each permutation; instead, it creates one collection at the start and fills that with each permutation before calling an Output() method that you supply:

    using System;
    
    namespace ConsoleApplication1
    {
        static class Program
        {
            static void Main()
            {
                int[] numbers = new[]
                {
                    0, 1, 2, 3, 4
                };
    
                Permute(numbers, Output);
                Console.WriteLine();
    
                string[] strings = new[]
                {
                    "Red", "Orange", "Yellow", "Green", "Blue"
                };
    
                Permute(strings, Output);
                Console.WriteLine();
    
                Console.ReadLine();
            }
    
            private static void Output<T>(T[] permutation)
            {
                foreach (T item in permutation)
                {
                    Console.Write(item);
                    Console.Write(" ");
                }
    
                Console.WriteLine();
            }
    
            public static void Permute<T>(T[] items, Action<T[]> output)
            {
                Permute(items, 0, new T[items.Length], new bool[items.Length], output);
            }
    
            private static void Permute<T>(T[] items, int item, T[] permutation, bool[] used, Action<T[]> output)
            {
                for (int i = 0; i < items.Length; ++i)
                {
                    if (!used[i])
                    {
                        used[i] = true;
                        permutation[item] = items[i];
    
                        if (item < (items.Length - 1))
                        {
                            Permute(items, item + 1, permutation, used, output);
                        }
                        else
                        {
                            output(permutation);
                        }
    
                        used[i] = false;
                    }
                }
            }
        }
    }
    
    • Marked as answer by Lavagin Saturday, February 06, 2010 2:01 AM
    Thursday, February 04, 2010 9:49 AM
  • Thanks for the response.  I will have to try this out shortly.  I should have mentioned this before....but I will be running these methods on various threads at the same time with different lists.  Will this cause any problems doing this?   (Would these have to be not static methods since different threads would be running them at the same time....I am unclear as to how static methods works with threads.



    Thursday, February 04, 2010 1:08 PM
  • All the data used is passed into the method, and any additional data is created on the stack. Therefore multithreading should cause no problems as long as the array passed to the method is not changed by a different thread while the permutations are being generated.
    • Marked as answer by Lavagin Saturday, February 06, 2010 2:01 AM
    Thursday, February 04, 2010 1:47 PM
  • Wow!  Works great!  Thank You!
    Saturday, February 06, 2010 2:00 AM
  • A few comments first:

    1) Are your numbers guaranteed to be different or can there be repetitions?

    2) Recursion is not an issue considering that you would go at most 20 levels deep. What you must be careful about instead is not creating new objects.

    3) Are you sure about your specs? Unless there are repetitions, the possible permutations of 20 numbers are exactly 20!, or 2,432,902,008,176,640,000. Even analyzing 1,000,000 permutations per second, your code would run for more than 77146 years.

    Thanks
    --mc

    I'm just curious regarding what he mentioned, did your program/code successfully complete?

    How long you took for such huge numbers?


    Extendable Dining Table Bedroom Carpet
    Tuesday, April 06, 2010 7:44 AM