CODEWITHSUNDEEP
c#algorithm
Free Bird
Free Bird

Reputation: 33

Permuting items in list

I have been trying to permute items that I have in a simple list and I have used the below code from this question but it is very slow when the size of sequence gets very large.

static IEnumerable<IEnumerable<T>>
GetPermutations<T>(IEnumerable<T> list, int length)
{
if (length == 1) return list.Select(t => new T[] { t });

return GetPermutations(list, length - 1)
    .SelectMany(t => list.Where(e => !t.Contains(e)),
        (t1, t2) => t1.Concat(new T[] { t2 }));
}

For example when the length of output needs to be large, then this method takes a long time to be execute.

An example of the problem would be, we have 25 alphabets and we want to know all possible 5-charterer long words that can we generate with them.

Is there any other method that can run faster than this?

Upvotes: 3

Views: 96

Answers (1)

Transcendent
Transcendent

Reputation: 5745

Assuming that you have 25 alphabets and you wanna find out how many words you can generate with them which are exactly 5 characters, there will mathematically be 25^5 possibilities. To simplify this, we can draw the problem as: 

[25] [25] [25] [25] [25]

This will be similar to an exotic base (in this case it is base 25). What you can do which I believe would be the fastest way, is to take advantage of base conversion for this. Lets shorten the size of alphabet array to 5 and the length of your words to 2 characters only to make the problems simpler. You must calculate how many possibilities there are which in this case would be [5] [5] -> 25. Now that you know this, you can use write something similar to the following method: 

 public static T[] Permute<T>(int input, List<T> items)
    {
        List<T> brute = new List<T>();
        while (true)
        {
            var temp = (decimal)input / (decimal)items.Count;
            var r = input % items.Count;
            input = (int)temp-1;
            if (temp < 1)
            {
                brute.Add(items[r]);
                break;
            }
            else
            {
                brute.Add(items[r]);
            }
        }
        return brute.ToArray();
    }

and the use it in a for loop to get your desired output: 

 static void Main(string[] args)
 {
     List<char> ls = new List<char> { 'A', 'B', 'C', 'D', 'E' };
     for (int i = ls.Count; i < (ls.Count * ls.Count)+ls.Count ; i++) {
         var x = Permute(i, ls);
         for (int j = 0; j < x.Length; j++) {
             Console.Write(x[j] + " ");
         }
         Console.WriteLine();
     }
     Console.ReadKey(true);

 }

Keep in mind, you'd better use Math.Pow method instead of (ls.Count * ls.Count) depending on how long the output has to be. And you have to calculate the offset in the for loop in order to get the exact size of strings you need.

This approach 100% relies on base conversion as if you have 5 alphabets and you have two places, then you fill in the first place with the five alphabets, then since there is no 6th, the 1st must be put into another place and the same process must repeat again and again.

Upvotes: 1

Related Questions