EDIT 1:
Single-line solution without recursions
I have recreated the core method (from the Previous Solution below in this answer), so that now it is not recursive anymore. It is now easy to make a single-line solution from this.
I had to use Enumerable methods and extension methods to do it though. Without these, I think it is impossible to do this.
class Permutator
{
private static IEnumerable<IEnumerable<int>> CreateIndices(int length)
{
var factorial = Enumerable.Range(2, length - 1)
.Aggregate((a, b) => a * b);
return (from p in Enumerable.Range(0, factorial)
// creating module values from 2 up to length
// e.g. length = 3: mods = [ p%2, p%3 ]
// e.g. length = 4: mods = [ p%2, p%3, p%4 ]
let mods = Enumerable.Range(2, length - 1)
.Select(m => p % m).ToArray()
select (
// creating indices for each permutation
mods.Aggregate(
new[] { 0 },
(s, i) =>
s.Take(i)
.Concat(new[] { s.Length })
.Concat(s.Skip(i)).ToArray())
));
}
public static IEnumerable<IEnumerable<T>> Get<T>(IEnumerable<T> items)
{
var array = items.ToArray();
return from indices in CreateIndices(array.Length)
select (from i in indices select array[i]);
}
}
Now the final solution
The resulting thing is this monstrosity:
class Permutator
{
public static IEnumerable<IEnumerable<T>> Get<T>(IEnumerable<T> items)
{
return
from p in Enumerable.Range(0,
Enumerable.Range(2, items.Count() - 1)
.Aggregate((a, b) => a * b))
let mods = Enumerable.Range(2, items.Count() - 1)
.Select(m => p % m).ToArray()
select mods.Aggregate(
items.Take(1).ToArray(),
(s, i) =>
s.Take(i)
.Concat(items.Skip(s.Length).Take(1))
.Concat(s.Skip(i)).ToArray());
}
}
Previous solution
I have created something that might be what you are looking for:
class Permutator
{
private static IEnumerable<IEnumerable<int>> CreateIndices(int length)
{
return (from p in Enumerable.Range(0, length)
select (
from s in Permutator.CreateIndices(length - 1)
.DefaultIfEmpty(Enumerable.Empty<int>())
select s.Take(p)
.Concat(new[] { length - 1 })
.Concat(s.Skip(p))
))
.SelectMany(i => i);
}
public static IEnumerable<IEnumerable<T>> Get<T>(IEnumerable<T> items)
{
var array = items.ToArray();
return from indices in CreateIndices(array.Length)
select (from i in indices select array[i]);
}
}
Example of how to use it:
var items = new[] { "0", "1", "2" };
var p = Permutator.Get(items);
var result = p.Select(a=>a.ToArray()).ToArray();
How it works
The core is the CreateIndices method. It creates a sequence that contains the indices of the source elements, for each permutation.
It is best to explain with an example:
CreateIndices(0);
// returns no permutations
CreateIndices(1);
// returns 1 permutation
// [ 0 ]
CreateIndices(2);
// returns 2 permutations
// [ 1, 0 ]
// [ 0, 1 ]
CreateIndices(3);
// returns 6 permutations
// [ 2, 1, 0 ]
// [ 2, 0, 1 ]
// [ 1, 2, 0 ]
// [ 0, 2, 1 ]
// [ 1, 0, 2 ]
// [ 0, 1, 2 ]
It is a recursive method, based only on enumerable extensions, and LINQ syntax queries.
The idea of the recursion is that each level builds based on the previous.
CreateIndices(n) adds the element n-1 to the permutations returned by CreateIndices(n-1), in all available positions.
The root of the recursion is CreateIndices(0) returning an empty set of permutations.
Explaining step by step: CreateIndices(3)
1. Lets start by creating the result of CreateIndices(0):
2. Then the result of CreateIndices(1):
- add element
0 (n-1) to each of previous permutations, at position 0
[ 0 ]
3. Then the result of CreateIndices(2)
- add element
1 (n-1) to each of previous permutations, at position 0
[ 1, 0 ]
- add element
1 (n-1) to each of previous permutations, at position 1
[ 0, 1 ]
4. Then the result of CreateIndices(3)
- add element
2 (n-1) to each of previous permutations, at position 0
[ 2, 1, 0 ]
[ 2, 0, 1 ]
- add element
2 (n-1) to each of previous permutations, at position 1
[ 1, 2, 0 ]
[ 0, 2, 1 ]
- add element
2 (n-1) to each of previous permutations, at position 2
[ 1, 0, 2 ]
[ 0, 1, 2 ]
What happens next
Now that we have the indices for each of the permutations, we can use them to build the real permutations of values. This is what the generic Get method does.
Also note that the Get method is the only one that materializes the source sequence into an array. The CreateIndices is just an enumerator, without any real objects... so you only pay the cost, when enumerating the sequences, and when calling the Get you pay to create an array of the source sequence.
This explains why after calling Get in the example, I had to materialize the result, so that we can use it:
var items = new[] { "0", "1", "2" };
var p = Permutator.Get(items); // pay to create array from source elements
var result = p.Select(a => a.ToArray() // pay to create arrays for each of the permutations
).ToArray(); // pay to get the permutations
This allows us to pay only half of the cost, if we just enumerate half of the permutations.
