morelinq / MoreLINQ

Extensions to LINQ to Objects
https://morelinq.github.io/
Apache License 2.0
3.67k stars 412 forks source link

`Permutations` returns wrong number of permutations for N > 12 #978

Closed atifaziz closed 1 year ago

atifaziz commented 1 year ago

Code to reproduce:

using MoreLinq;

var sources =
    from count in MoreEnumerable.Generate(1, x => x + 1)
    select (count, Enumerable.Range(1, count));

foreach (var (count, source) in sources)
    Console.WriteLine($"Permutations({count:N0}) = {source.Permutations().Count():N0}");

Results for first 26:

Permutations(1) = 1
Permutations(2) = 2
Permutations(3) = 6
Permutations(4) = 24
Permutations(5) = 120
Permutations(6) = 720
Permutations(7) = 5,040
Permutations(8) = 40,320
Permutations(9) = 362,880
Permutations(10) = 3,628,800
Permutations(11) = 39,916,800
Permutations(12) = 479,001,600
Permutations(13) = 1,932,053,504
Permutations(14) = 1,278,945,280
Permutations(15) = 2,004,310,016
Permutations(16) = 2,004,189,184
Permutations(17) = 1
Permutations(18) = 1
Permutations(19) = 109,641,728
Permutations(20) = 1
Permutations(21) = 1
Permutations(22) = 1
Permutations(23) = 862,453,760
Permutations(24) = 1
Permutations(25) = 2,076,180,480
Permutations(26) = 1
…

Results for Permutations(13) and onward produce incorrect results.

Discussed in https://github.com/morelinq/MoreLINQ/discussions/977

Originally posted by **laurinpaech** March 1, 2023 Hi! I was trying to loop over the permutations of a list of objects. The objects are of a custom type, not builtin. It does work but only generates a single permutation and therefore iterates once and then stops. Do they need to implement some function for it to work? I couldn't find anything in the documentation. The same code works when using ints