Permuting items in list

Question

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?

Doesn't the accepted answer on that question work? LINQ is almost always slow. — , Oct 05 '17 at 13:32
@someone "LINQ is almost always slow" Sais whom? That entirely depends on how you´re iterating your collection and has nothing to do with linq per-sé. — MakePeaceGreatAgain, Oct 05 '17 at 13:35
I did not say it is impossible to write fast code with linq, but code without linq will likely be faster. — , Oct 05 '17 at 13:36
Anyway I assume this is a better fit for review.stackexchange.com — MakePeaceGreatAgain, Oct 05 '17 at 13:36
Since a word allows repetitions of chars, you shouldn't generate permutations but combinations with repetitions. Even if the code is performant, you could be still generating a huge amount of data with those numbers. No, Linq is not slow. — Mauro Sampietro, Oct 05 '17 at 13:45

Transcendent · Accepted Answer · 2017-10-05T13:44:44.103

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.

You could want to `ref` a single list to Permute and save a few million list creations and casts to array. — , Oct 05 '17 at 13:44
@someone This problem can get very obscure and complex, the point is to teach the OP. They can then optimize it as they need. This is not a read-to-use solution. — Transcendent, Oct 05 '17 at 13:45

Permuting items in list

1 Answers1