我尝试解决下一个练习:
输入:整数列表,其中
输出:这些整数的所有可能元组,长度为
例如:
输入:
输入:整数列表,其中
count >= 1;
和某个正整数k
。输出:这些整数的所有可能元组,长度为
k
。例如:
输入:
{1, 2}; k = 4
输出:{
{1, 1, 1, 1},
{1, 1, 1, 2},
{1, 1, 2, 1},
{1, 1, 2, 2},
{1, 2, 1, 1},
{1, 2, 1, 2},
{1, 2, 2, 1},
{1, 2, 2, 2},
{2, 1, 1, 1},
{2, 1, 1, 2},
{2, 1, 2, 1},
{2, 1, 2, 2},
{2, 2, 1, 1},
{2, 2, 1, 2},
{2, 2, 2, 1},
{2, 2, 2, 2}
}
我试图创建一个包含k
个输入列表副本的数组,然后使用Combinations
:
public static IEnumerable<IEnumerable<T>> Combinations<T>(
this IEnumerable<T> elements,
int k)
{
return k == 0
? new[] { new T[0] }
: elements.SelectMany((e, i) => elements
.Skip(i + 1)
.Combinations(k - 1)
.Select(c => (new[] { e }).Concat(c)));
}
但是当 k > 9
时,这需要太长时间了。是否有一种算法能在短时间内解决这个问题?
Math.Power(elements.Count(), k)
个项目; 在你的情况下,仅有2**9 == 512
个项目。 - Dmitry Bychenko