gpt4 book ai didi

c# - 将整数列表 (IEnumerable) 转换为特定长度的元组列表 (IEnumerable>)

转载 作者:行者123 更新时间:2023-12-05 00:44:41 36 4
gpt4 key购买 nike

我尝试解决下一个练习:

输入:整数列表 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 .在 中是否有解决此问题的算法?短时间 ?

最佳答案

让我们摆脱递归并拥有 512项目:

代码:

//TODO: you may want to declare it as IEnumerable<T[]> Combinations<T> 
public static IEnumerable<IEnumerable<T>> Combinations<T>(
this IEnumerable<T> elements, int k) {

if (null == elements)
throw new ArgumentNullException(nameof(elements));
else if (k < 0)
throw new ArgumentOutOfRangeException(nameof(k));

T[] alphabet = elements.ToArray();

// Special cases
if (alphabet.Length <= 0)
yield break;
else if (k == 0)
yield break;

int[] indexes = new int[k];

do {
yield return indexes
.Select(i => alphabet[i])
.ToArray();

for (int i = indexes.Length - 1; i >= 0; --i)
if (indexes[i] >= alphabet.Length - 1)
indexes[i] = 0;
else {
indexes[i] += 1;

break;
}
}
while (!indexes.All(index => index == 0));
}

演示:
string report = string.Join(Environment.NewLine, Combinations(new int[] { 1, 2}, 9)
.Select(line => string.Join(", ", line)));

Console.Write(report);

结果: ( 512 记录)
1, 1, 1, 1, 1, 1, 1, 1, 1
1, 1, 1, 1, 1, 1, 1, 1, 2
1, 1, 1, 1, 1, 1, 1, 2, 1
1, 1, 1, 1, 1, 1, 1, 2, 2
1, 1, 1, 1, 1, 1, 2, 1, 1
1, 1, 1, 1, 1, 1, 2, 1, 2
1, 1, 1, 1, 1, 1, 2, 2, 1
1, 1, 1, 1, 1, 1, 2, 2, 2
1, 1, 1, 1, 1, 2, 1, 1, 1
...
2, 2, 2, 2, 2, 2, 1, 2, 1
2, 2, 2, 2, 2, 2, 1, 2, 2
2, 2, 2, 2, 2, 2, 2, 1, 1
2, 2, 2, 2, 2, 2, 2, 1, 2
2, 2, 2, 2, 2, 2, 2, 2, 1
2, 2, 2, 2, 2, 2, 2, 2, 2

让我们生成所有 2**20 == 1048576项目( k = 20 ),即超过 100 万个大小为 20 的数组:
  Stopwatch sw = new Stopwatch();

sw.Start();

int count = Combinations(new int[] { 1, 2 }, 20).Count();

sw.Stop();

Console.Write($"{count.ToString()} items at {sw.ElapsedMilliseconds:f0} milliseconds");

结果:
  1048576 items at 469 milliseconds

关于c# - 将整数列表 (IEnumerable<int>) 转换为特定长度的元组列表 (IEnumerable<IEnumerable<int>>),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/59453407/

36 4 0