如何获得几个List <int>的所有组合

Question

与上面的sugested解决方案不同,列表项只能为每一行显示一次.

这是我的水疗中心的预订系统.不同的员工可以进行不同的治疗

我有一个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

希望这会让问题更加清晰.

Answer 1

通过递归求解:

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 }

Answer 2

这个解决方案远非高效：

    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);
            }
        }
    }

听起来这可以通过动态编程更有效地解决，但自从我学习相关课程以来已经有一段时间了。