I've tried to write a method which returns the permutation of a given enumerable as simple as possible. The code:
using System.Collections.Generic;
public static partial class Permutable {
static IEnumerable<IEnumerable<T>> PermuteIterator<T>(
IEnumerable<T> source, int offset) {
var count=0;
foreach(var dummy in source)
if(++count>offset)
foreach(
var sequence in
Permutable.PermuteIterator(
source.Exchange(offset, count-1), 1+offset)
)
yield return sequence;
if(offset==count-1)
yield return source;
}
public static IEnumerable<IEnumerable<T>> AsPermutable<T>(
this IEnumerable<T> source) {
return Permutable.PermuteIterator(source, 0);
}
public static IEnumerable<T> Exchange<T>(
this IEnumerable<T> source, int index1, int index2) {
// exchange elements at index1 and index2
}
}
As the code has simplified within the iterator block, I'm trying to make it simply a single query expression of LINQ.
There's a recursion in the nested foreach with this code, even another possibly yield outside the foreach; and which is the difficult part for me to rewrite it in query syntax.
I've read this answer:
But I guess it's not the solution for me ..
I tried various ways, and think it's not so easy to do. How can I get it done?
(The Exchange method is another problem, and I've asked a question:
How to exchange the items of enumeration by interating only once?
But I guess it's not the matter here .. )
EDIT 1:
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());
}
}
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();
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):
0 (n-1) to each of previous permutations, at position 0
3. Then the result of CreateIndices(2)
1 (n-1) to each of previous permutations, at position 0
1 (n-1) to each of previous permutations, at position 1
4. Then the result of CreateIndices(3)
2 (n-1) to each of previous permutations, at position 0
2 (n-1) to each of previous permutations, at position 1
2 (n-1) to each of previous permutations, at position 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.