重複の可能性：
List <List<int>>の組み合わせ
私は複数のリストを持っています。2つまたは3つから最大10のリストで、複数の値が含まれている可能性があります。今私がする必要があるのは、それらすべての組み合わせを取得することです。
たとえば、次の値を持つ3つのリストがあるとします。
私はこれらの組み合わせを取得します
問題は、リストがいくつあるかわからないため、これを簡単に実行できないことです。したがって、必要なループの数を決定します。
あなたはおそらくそれをもっと簡単にすることができますが、これは私が今考えていたものです：
List<List<int>> lists = new List<List<int>>();
lists.Add(new List<int>(new int[] { 3, 5, 7 }));
lists.Add(new List<int>(new int[] { 3, 5, 6 }));
lists.Add(new List<int>(new int[] { 2, 9 }));
int listCount = lists.Count;
List<int> indexes = new List<int>();
for (int i = 0; i < listCount; i++)
indexes.Add(0);
while (true)
{
// construct values
int[] values = new int[listCount];
for (int i = 0; i < listCount; i++)
values[i] = lists[i][indexes[i]];
Console.WriteLine(string.Join(" ", values));
// increment indexes
int incrementIndex = listCount - 1;
while (incrementIndex >= 0 && ++indexes[incrementIndex] >= lists[incrementIndex].Count)
{
indexes[incrementIndex] = 0;
incrementIndex--;
}
// break condition
if (incrementIndex < 0)
break;
}
私が完全に間違っていなければ、これはO(Nm)リストmの数と順列の数（すべてのリストNの長さの積）であるはずです。m
非再帰的なソリューションであり、IEnumerableリストを固めることなく、（リストだけでなく）任意のsで機能します。
public static IEnumerable<IEnumerable<T>> Permutations<T>(
this IEnumerable<IEnumerable<T>> source)
{
// Check source non-null, non-empty?
var enumerables = source.ToArray();
Stack<IEnumerator<T>> fe = new Stack<IEnumerator<T>>();
fe.Push(enumerables[0].GetEnumerator());
while (fe.Count > 0)
{
if (fe.Peek().MoveNext())
{
if (fe.Count == enumerables.Length)
yield return new Stack<T>(fe.Select(e => e.Current));
else
fe.Push(enumerables[fe.Count].GetEnumerator());
}
else
{
fe.Pop().Dispose();
}
}
}
List<List<yourValueType> mainlistあなたはあなたがあなたのすべてのリストを置くことを作ることができます。その後、簡単に
int numberOfIterations = 1;
foreach(var item in mainlist)
{
numberOfIterations *= item.Count;
}
これにより、合計で実行する必要のある反復の量が得られます。
あまり効率的ではありませんが、非常に理解しやすいアプローチは、このタスクを再帰的に解決することかもしれません。N個のリストの順列を計算する方法を考えてみましょう。このような方法がある場合は、 N個のリストのすべての順列を最後のリストのすべての数値と組み合わせることで、 N+1個のリストの順列を簡単に計算できます。0リストの順列であるコーナーケースも処理する必要があります。その場合、実装は簡単なようです。
IEnumerable<IEnumerable<T>> GetAllPermutations<T>(IEnumerable<IEnumerable<T>> inputLists)
{
if (!inputLists.Any()) return new [] { Enumerable.Empty<T>() };
else
{
foreach (var perm in GetAllPermutations(inputLists.Skip(1)))
foreach (var x in inputLists.First())
yield return new[]{x}.Concat(perm);
}
}
別の方法として、ローリングスの一般的な考え方に従うと、次のことが機能するはずです
public static IEnumerable<IEnumerable<T>> Permutations<T> (this IEnumerable<IEnumerable<T>> underlying)
{
var enumerators = new Queue<IEnumerator<T>>(underlying.Select(u => u.GetEnumerator())
.Where(enumerator => enumerator.MoveNext());
Boolean streaming = enumerators.Any();
if(streaming)
{
IEnumerable<T> result;
IEnumerator<T> finalEnumerator = enumerators.Dequeue();
Func<Boolean,Boolean> finalAction = b => b ? b : finalEnumerator.MoveNext();
Func<Boolean,Boolean> interimAction =
enumerators.Reverse()
.Select(enumerator => new Func<Boolean,Boolean>(b => b ? b : (enumerator.MoveNext() ? true : enumerator.ResetMove())))
.Aggregate((f1,f2) => (b => f1(f2(b)));
enumerators.Enqueue(finalEnumerator);
Func<Boolean,Boolean> permutationAction =
interimAction == null ?
finalAction :
b => finalAction(interimAction(b));
while(streaming)
{
result = new Queue<T>(enumerators.Select(enumerator => enumerator.Current))
streaming = permutationAction(true);
yield return result;
}
}
private static Boolean ResetMove<T>(this IEnumerator<T> underlying)
{
underlying.Reset();
underlying.MoveNext();
return false;
}