如何迭代不同长度的列表以查找所有排列
本文关键字:列表 查找 排列 何迭代 迭代 | 更新日期: 2023-09-27 17:59:25
这个应该不会太难,但我的脑海中似乎有堆栈溢出(huehue)。我有一系列的列表,我想找到所有可以排序的排列。所有的列表都有不同的长度。
例如:
列表1:1
列表2:1,2
所有排列都是:
1,1
1,2
在我的情况下,我不会转换数字。(例如2,1)写这篇文章最简单的方法是什么?
我不能说下面的方法是否是最简单的方法,但IMO是最有效的方法。这基本上是我对锯齿状阵列中的每个组合的回答的广义版本:
public static class Algorithms
{
public static IEnumerable<T[]> GenerateCombinations<T>(this IReadOnlyList<IReadOnlyList<T>> input)
{
var result = new T[input.Count];
var indices = new int[input.Count];
for (int pos = 0, index = 0; ;)
{
for (; pos < result.Length; pos++, index = 0)
{
indices[pos] = index;
result[pos] = input[pos][index];
}
yield return result;
do
{
if (pos == 0) yield break;
index = indices[--pos] + 1;
}
while (index >= input[pos].Count);
}
}
}
你可以在链接的答案中看到解释(很快它就模仿了嵌套循环)。此外,由于性能原因,它会产生内部缓冲区而不进行克隆,因此如果您想存储结果以供以后处理,则需要对其进行克隆。
示例用法:
var list1 = new List<int> { 1 };
var list2 = new List<int> { 1, 2 };
var lists = new[] { list1, list2 };
// Non caching usage
foreach (var combination in lists.GenerateCombinations())
{
// do something with the combination
}
// Caching usage
var combinations = lists.GenerateCombinations().Select(c => c.ToList()).ToList();
UPDATE:GenerateCombinations
是一个标准的C#迭代器方法,其实现基本上模拟N
嵌套循环(其中N
是input.Count
),如下所示(在伪代码中):
for(int i0=0;i0<input[0]。Count;i0++)
for(int i1=0;i1<input[1].Count;i1++)
for(int i2=0;i2<input[2].Count;i2>++)
…
for(int iN-1=0;iN-1<input[N-1].Count;iN-1++)
产生{input[0][i0],input[1][i1],input[2][i2,…,input[N-1][iN-1]}
或者以不同的方式显示:
for (indices[0] = 0; indices[0] < input[0].Count; indices[0]++)
{
result[0] = input[0][indices[0]];
for (indices[1] = 0; indices[1] < input[1].Count; indices[1]++)
{
result[1] = input[1][indices[1]];
// ...
for (indices[N-1] = 0; indices[N-1] < input[N-1].Count; indices[N-1]++)
{
result[N-1] = input[N-1][indices[N-1]];
yield return result;
}
}
}
我制作了以下IEnumerable<IEnumerable<TValue>>
类来解决这个问题,该类允许使用通用IEnumerable,其枚举器返回所有值的排列,每个内部列表中有一个。它可以在foreach循环中直接使用。
这是Michael Liu对IEnumerable和递归使用收益率返回的回答的变体
我对它进行了修改,使其返回具有排列的列表,而不是单个值。
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
namespace Permutation
{
public class ListOfListsPermuter<TValue> : IEnumerable<IEnumerable<TValue>>
{
private int count;
private IEnumerable<TValue>[] listOfLists;
public ListOfListsPermuter(IEnumerable<IEnumerable<TValue>> listOfLists_)
{
if (object.ReferenceEquals(listOfLists_, null))
{
throw new ArgumentNullException(nameof(listOfLists_));
}
listOfLists =listOfLists_.ToArray();
count = listOfLists.Count();
for (int i = 0; i < count; i++)
{
if (object.ReferenceEquals(listOfLists[i], null))
{
throw new NullReferenceException(string.Format("{0}[{1}] is null.", nameof(listOfLists_), i));
}
}
}
// A variant of Michael Liu's answer in StackOverflow
// https://stackoverflow.com/questions/2055927/ienumerable-and-recursion-using-yield-return
public IEnumerator<IEnumerable<TValue>> GetEnumerator()
{
TValue[] currentList = new TValue[count];
int level = 0;
var enumerators = new Stack<IEnumerator<TValue>>();
IEnumerator<TValue> enumerator = listOfLists[level].GetEnumerator();
try
{
while (true)
{
if (enumerator.MoveNext())
{
currentList[level] = enumerator.Current;
level++;
if (level >= count)
{
level--;
yield return currentList;
}
else
{
enumerators.Push(enumerator);
enumerator = listOfLists[level].GetEnumerator();
}
}
else
{
if (level == 0)
{
yield break;
}
else
{
enumerator.Dispose();
enumerator = enumerators.Pop();
level--;
}
}
}
}
finally
{
// Clean up in case of an exception.
enumerator?.Dispose();
while (enumerators.Count > 0)
{
enumerator = enumerators.Pop();
enumerator.Dispose();
}
}
}
IEnumerator IEnumerable.GetEnumerator()
{
return GetEnumerator();
}
}
}
你可以直接在前臂上使用它,如下所示:
public static void Main(string[] args)
{
var listOfLists = new List<List<string>>()
{
{ new List<string>() { "A", "B" } },
{ new List<string>() { "C", "D" } }
};
var permuter = new ListOfListsPermuter<string>(listOfLists);
foreach (IEnumerable<string> item in permuter)
{
Console.WriteLine("{ '"" + string.Join("'", '"", item) + "'" }");
}
}
输出:
{ "A", "C" }
{ "A", "D" }
{ "B", "C" }
{ "B", "D" }
List<int> listA = (whatever), listB = (whatever);
var answers = new List<Tuple<int,int>>;
for(int a in listA)
for(int b in listB)
answers.add(Tuple.create(a,b));
// do whatever with answers
试试这个:
Func<IEnumerable<string>, IEnumerable<string>> combine = null;
combine = xs =>
xs.Skip(1).Any()
? xs.First().SelectMany(x => combine(xs.Skip(1)), (x, y) => String.Format("{0}{1}", x, y))
: xs.First().Select(x => x.ToString());
var strings = new [] { "AB", "12", "$%" };
foreach (var x in combine(strings))
{
Console.WriteLine(x);
}
这给了我:
A1$A1%A2$A2%B1$B1%B2$B2%