9

与上面建议的解决方案不同，列表项每行只能出现一次。

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

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

希望这能让问题更清楚一点。

4

3 回答 3

5

递归求解：

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 }
于 2013-07-14T18:14:05.520 回答
3

查看此问题的一种简单方法是从值列表的所有组合中进行选择，其中组合中的每个值都是唯一的。

首先弄清楚所有值的组合是什么。

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
于 2013-07-14T19:07:44.007 回答
3

该解决方案远非有效：

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

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

于 2013-07-14T18:08:06.300 回答