如何获得多个List<int>的所有组合
如何获得多个List<int>的所有组合
提问于 2013-07-14 17:23:51
与上面建议的解决方案不同的是，列表项只能针对每一行出现一次。
这是我的水疗预约系统。不同的员工可以进行不同的处理。
我有一个List<List<int>>。这些都是治疗师，他们可以进行预定的治疗。
每个列表(预订)包含许多这样的整数(这些是可以执行预订的治疗师)：
{1, 3, 6}, //Booking 1
{1, 2, 6}, //Booking 2
{1}, //Booking 3
{2,3} //Booking 4我想看到所有可能的组合，其中的数字只能出现在一个地方。对于上述清单，两种可能的缺失是：
6,2,1,3或3,6,1,2
这是第一个组合：
- 预订1:治疗师6
- 预订2:治疗师2
- 预订3:治疗师1
- 预订4:治疗师3
希望这能让问题更清楚一点。
回答 3
Stack Overflow用户
回答已采纳
发布于 2013-07-14 18:08:06
这一解决办法远远没有效率：
private static void Main()
{
List<List<int>> list = new List<List<int>>
{
new List<int>() {1, 3, 6}, //Booking 1
new List<int>() {1, 2, 6}, //Booking 2
new List<int>() {1}, //Booking 3
new List<int>() {2, 3}
};
List<int[]> solutions = new List<int[]>();
int[] solution = new int[list.Count];
Solve(list, solutions, solution);
}
private static void Solve(List<List<int>> list, List<int[]> solutions, int[] solution)
{
if (solution.All(i => i != 0) && !solutions.Any(s => s.SequenceEqual(solution)))
solutions.Add(solution);
for (int i = 0; i < list.Count; i++)
{
if (solution[i] != 0)
continue; // a caller up the hierarchy set this index to be a number
for (int j = 0; j < list[i].Count; j++)
{
if (solution.Contains(list[i][j]))
continue;
var solutionCopy = solution.ToArray();
solutionCopy[i] = list[i][j];
Solve(list, solutions, solutionCopy);
}
}
}听起来这个问题可以用动态规划更有效地解决，但我已经有一段时间没有上过相关的课程了。
Stack Overflow用户
发布于 2013-07-14 18:14:05
递归求解：
static IEnumerable<List<int>> GetCombinations(IEnumerable<List<int>> lists, IEnumerable<int> selected)
{
if (lists.Any())
{
var remainingLists = lists.Skip(1);
foreach (var item in lists.First().Where(x => !selected.Contains(x)))
foreach (var combo in GetCombinations(remainingLists, selected.Concat(new int[] { item })))
yield return combo;
}
else
{
yield return selected.ToList();
}
}
static void Main(string[] args)
{
List<List<int>> lists = new List<List<int>>
{
new List<int> { 1, 3, 6 },
new List<int> { 1, 2, 6 },
new List<int> { 1 },
new List<int> { 2, 3 }
};
var combos = GetCombinations(lists, new List<int>()).Distinct();
foreach (var combo in combos)
Console.WriteLine("{ " + string.Join(", ", combo.Select(x => x.ToString())) + " }");
return;
}输出：
{ 3, 6, 1, 2 }
{ 6, 2, 1, 3 }Stack Overflow用户
发布于 2013-07-14 19:07:44
处理这个问题的一个简单方法是从值列表的所有组合中进行选择，其中组合中的每个值都是唯一的。
首先，找出所有值的组合是什么。
public static IEnumerable<IList<T>> Combinations<T>(IEnumerable<IList<T>> collections)
{
if (collections.Count() == 1)
{
foreach (var item in collections.Single())
yield return new List<T> { item };
}
else if (collections.Count() > 1)
{
foreach (var item in collections.First())
foreach (var tail in Combinations(collections.Skip(1)))
yield return new[] { item }.Concat(tail).ToList();
}
}然后，您需要一种方法来确定所有的值是否是唯一的。一个简单的方法是检查不同值的计数是否等于所有值的计数。
public static bool AllUnique<T>(IEnumerable<T> collection)
{
return collection.Distinct().Count() == collection.Count();
}一旦你拥有了所有这些，就把它们放在一起。
var collections = new[]
{
new List<int> { 1, 3, 6 },
new List<int> { 1, 2, 6 },
new List<int> { 1 },
new List<int> { 2, 3 },
};
var results =
from combination in Combinations(collections)
where AllUnique(combination)
select combination;
// results:
// 3,6,1,2
// 6,2,1,3页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/17641769
复制相关文章
相似问题
腾讯云开发者
