Combinations without repetitions with must included in the combos

Question

I have 2 list of ints and I need a list of all possible combinations without repetitions of 5 numbers. But it also needs to include all the ints from another list.

Example:

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

I have been using KwCombinatorics but it takes ages to finish. And almost 80% of the result is useless because it doesn't contain the ints from the mustInclude list.

Example of output:

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

It doesn't have to be in this order, as long as it doesn't contain repetitions.

Just create the combinations of 2 numbers from the other values and then add the required to the results. — juharr, Nov 16 '18 at 17:42

score 2 · Accepted Answer · answered Nov 16 '18 at 18:41

Borrowing GetAllCombos from this Question, and using the idea from @juharr, I believe the following code gives you the results you are looking for.

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 gives you all the combinations without the numbers required by all Lists, and then the second AddListToEachList method will add the required numbers to each List.

score 1 · Answer 2 · answered Nov 16 '18 at 18:23

As already suggested in the comments, you can remove the three required numbers from the list and generate the combinations of two instead of five.

Something like this:

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

Combinations without repetitions with must included in the combos

2 Answers2