没有重复的组合必须包含在组合中

Question

我有 2 个 int 列表，我需要一个所有可能组合的列表，不重复 5 个数字。但它还需要包含另一个列表中的所有 int。

示例：

var takeFrom = new List<int> { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
var mustInclude = new List<int> { 1, 3, 5 };

我一直在使用 KwCombinatorics，但需要很长时间才能完成。几乎 80% 的结果是无用的，因为它不包含 mustInclude 列表中的 int。

输出示例：

var result = new List<int> 
{
     { 1, 3, 5, 9, 10 },
     { 1, 3, 5, 8, 7 },
     { 1, 3, 5, 6, 9 },
}

不必按此顺序，只要不重复即可。

Answer 1

正如评论中已经建议的那样，您可以从列表中删除三个必需的数字并生成两个而不是五个的组合。

像这样：

takeFrom = takeFrom.Except(mustInclude).ToList();
listOfPairs = KwCombinatorics(takeFrom, 2);
result = listOfPairs.Select(pair => mustInclude.Concat(pair).ToList()).ToList();

Answer 2

从this Question 借用GetAllCombos，并使用@juharr 的想法，我相信下面的代码会给你想要的结果。

List<int> takeFrom = new List<int> { 2, 4, 6, 7, 8, 9, 10 };
    List<int> mustInclude = new List<int> { 1, 3, 5 };

    protected void Page_Load(object sender, EventArgs e)
    {
        List<List<int>> FinalList = new List<List<int>>();

        FinalList = GetAllCombos(takeFrom);
        FinalList = AddListToEachList(FinalList, mustInclude);

        gvCombos.DataSource = FinalList;
        gvCombos.DataBind();
    }

    // Recursive
    private static List<List<T>> GetAllCombos<T>(List<T> list)
    {
        List<List<T>> result = new List<List<T>>();
        // head
        result.Add(new List<T>());
        result.Last().Add(list[0]);
        if (list.Count == 1)
            return result;
        // tail
        List<List<T>> tailCombos = GetAllCombos(list.Skip(1).ToList());
        tailCombos.ForEach(combo =>
        {
            result.Add(new List<T>(combo));
            combo.Add(list[0]);
            result.Add(new List<T>(combo));
        });
        return result;
    }

    private static List<List<int>> AddListToEachList(List<List<int>> listOfLists, List<int> mustInclude)
    {
        List<List<int>> newListOfLists = new List<List<int>>();

        //Go through each List
        foreach (List<int> l in listOfLists)
        {
            List<int> newList = l.ToList();

            //Add each item that should be in all lists
            foreach(int i in mustInclude)
                newList.Add(i);

            newListOfLists.Add(newList);
        }

        return newListOfLists;
    }

    protected void gvCombos_RowDataBound(object sender, GridViewRowEventArgs e)
    {
        if (e.Row.RowType == DataControlRowType.DataRow)
        {
            List<int> drv = (List<int>)e.Row.DataItem;
            Label lblCombo = (Label)e.Row.FindControl("lblCombo");

            foreach (int i in drv)
                lblCombo.Text += string.Format($"{i} "); 
        }
    }

GetAllCombos给你所有的组合没有所有List需要的数字，然后第二个AddListToEachList方法将需要的数字相加每个列表。

没有重复的组合必须包含在组合中

Combinations without repetitions with must included in the combos

c#

combinations

non-repetitive