編集1：
再帰のない単一行のソリューション
コア メソッドを再作成したため (この回答の下の以前のソリューションから)、再帰的ではなくなりました。これから単一行のソリューションを作成するのは簡単です。
Enumerableただし、それを行うにはメソッドと拡張メソッドを使用する必要がありました。これらがなければ、これを行うことは不可能だと思います。
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]);
}
}
これで最終的な解決策
その結果がこの怪物です。
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());
}
}
以前のソリューション
私はあなたが探しているものかもしれないものを作成しました:
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]);
}
}
使用方法の例:
var items = new[] { "0", "1", "2" };
var p = Permutator.Get(items);
var result = p.Select(a=>a.ToArray()).ToArray();
使い方
核となるのはCreateIndices方法です。順列ごとに、ソース要素のインデックスを含むシーケンスを作成します。
例を挙げて説明するのが最善です:
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 ]
これは、列挙可能な拡張機能と LINQ 構文クエリのみに基づく再帰的な方法です。
再帰の考え方は、各レベルが前のレベルに基づいて構築されるということです。
CreateIndices(n)n-1によって返される順列にCreateIndices(n-1)、使用可能なすべての位置に要素を追加します。
再帰のルートは、CreateIndices(0)順列の空のセットを返しています。
順を追って説明します：CreateIndices(3)
1. の結果を作成することから始めましょうCreateIndices(0):
2. 次に、次の結果CreateIndices(1):
- 位置 0 [ 0 ]で、前の順列のそれぞれに要素
0(n-1) を
追加します
3.次に、の結果CreateIndices(2)
- 位置 0 [ 1, 0 ]で、前の順列のそれぞれに要素
1(n-1) を
追加します
- 位置 1 [ 0, 1 ]で、前の順列のそれぞれに要素
1(n-1) を
追加します。
4. 次に、CreateIndices(3)
- 位置 0 [ 2, 1, 0 ]
[ 2, 0, 1 ] で、前の順列のそれぞれに要素
2(n-1) を
追加します。
- 位置 1 [ 1, 2, 0 ]
[ 0, 2, 1 ] で、前の順列のそれぞれに要素
2(n-1) を
追加します。
- 位置 2 [ 1, 0, 2 ]
[ 0, 1, 2 ] で、前の順列のそれぞれに要素
2(n-1) を
追加します。
次は何が起こる
各順列のインデックスを取得したので、それらを使用して値の実際の順列を構築できます。これがジェネリックGetメソッドの機能です。
Getまた、このメソッドは、ソース シーケンスを配列に実体化する唯一のメソッドであることに注意してください。はCreateIndices単なる列挙子であり、実際のオブジェクトはありません...したがって、シーケンスを列挙するときとGet、ソース シーケンスの配列を作成するために を呼び出すときにコストのみを支払います。
これは、例を呼び出した後Get、結果を使用できるように結果を具体化する必要があった理由を説明しています。
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
これにより、順列の半分を列挙するだけで、コストの半分だけを支払うことができます。