c# - 21 个列表中 3 个不重复数字的组总数

Question

我正在为一个有 21 名学生的同事做这个。他需要在一年中将他们分成 3 人一组，但每组永远不能有一个成员与另一个成员在一个组中。

我已经编写了程序，它给了我 25 组的输出。但我不知道这是不是最多的群体，似乎太少了。

当一个学生与之前正在接受测试的学生在一起时，我如何进入 foreach 的下一行。Break 停止整个循环，Continue 被标记为冗余。我可以在组中有 2 个人，第一个与被检查的人在一起，但第二个没有，所以 bool 被重置为 false。

 else //they have met that person before
                    {
                        IsStudentBeen = true;
                    }

有人可以检查我的代码是否正确吗？

        private void BtnCalc_Click(object sender, EventArgs e)
    {

        //need to have a list of all students to record all students they have been in a group with
       //output to date = 25 groups

        //All students have a list that contains all the students they have been in a group with before.


        List<string>[] StudentHistory = new List<string>[22];

        //Instantiate the lists = names
        for (int i = 1; i < 22; i++)
        {
            StudentHistory[i] = new List<string>();
        }
        List<string> singlegroup = new List<string>();

        for (int k = 1; k < 21; k++) //get all permutations
        {
            for (int i = k; i < 22; i++)
            {
                string student = i.ToString();
                string StudentToAdd = null;
                //Need to add the first memebr manually or it crashes at the foreach
                if (singlegroup.Count == 0)
                {
                    singlegroup.Add(student);
                    StudentHistory[1].Add(student);
                }
                else
                {
                    bool IsStudentBeen = false;
                    foreach (var AGroupStudent in singlegroup) // for each person in the group
                    { //convert the person to an int to find their history list
                        int GroupStudent = Convert.ToInt32(AGroupStudent);

                        if (!StudentHistory[GroupStudent].Contains(student))
                        {
                            //if the student isn't in the group, and they have never been with the others then add them
                            if (IsStudentBeen == false)
                            {
                                StudentToAdd = student;
                            }
                            //add that person to the history of the others
                            StudentHistory[GroupStudent].Add(student);
                        }
                        else //they have met that person before
                        {
                            IsStudentBeen = true;
                        }
                    }
                    //add the student to the group
                    if (IsStudentBeen == false)
                    {
                        singlegroup.Add(StudentToAdd);
                    }
                    //if the group has reached 3 then print it and clear it for the next group

                    if (singlegroup.Count == 3)
                    {
                        String Group = null;

                        foreach (var item in singlegroup)
                        {
                            Group += item + " ";
                        }

                        lbxOutput.Items.Add(Group);
                        singlegroup.Clear(); //empty the list ready for the next one
                    }
                }

            }
            //  count++;
            // this.Text = count.ToString();
            // }
        }
    }

标签： c#

Answer 1

另一位 SO 参与者的回答如下：

 var students = Enumerable.Range(1, 21).ToArray();
 var groups = new List<int[]>();

 foreach(var s1 in students)
     foreach(var s2 in students.Where(s => s > s1))
        foreach(var s3 in students.Where(s => s > s2))
        {
            int[] a = { s1, s2, s3 };

            bool allowed = true;

            foreach(var g in groups)
            {
               if (g.Contains(s1) && (g.Contains(s2) || g.Contains(s3)) ||
                   g.Contains(s2) && g.Contains(s3))
               {
                   allowed = false;
                   break;
               }
            }

            if (allowed)
            {
                groups.Add(a);
            }
        }
 Console.WriteLine($"groups: {groups.Count}");

这个答案对我来说很有意义，但被原作者删除了。它会找到每个学生50组3，其中没有任何组共享同一对学生。

---

替代答案：（
在有些不同的假设下）

有7支队伍，每轮3名学生。对于下一轮，没有学生可以与他/她以前的2r团队成员组队，如果r是到目前为止的轮数。因此，25 轮是不可能的。对于 21 名学生，最大轮数必须小于 10。

以下代码找到了 6 轮：

1:  1  2  3 |  4  5  6 |  7  8  9 | 10 11 12 | 13 14 15 | 16 17 18 | 19 20 21
2:  8 12 21 | 20 17  7 |  2 11 15 |  1 16 10 |  4  9 19 | 13  3  5 | 18  6 14
3: 20  2 18 |  5 12 14 |  8 16  4 | 10  7 21 |  6  1 19 |  3 15 17 | 11 13  9
4: 12  9  2 |  5  8 11 |  1 13 17 | 19 10 18 |  3 20 16 |  4 14  7 | 21  6 15
5:  7 19  5 | 14  1  8 | 15 12 20 | 21 16 11 | 17 10  4 | 18  3  9 | 13  2  6
6: 18  8 15 | 13 12  7 |  2 10  5 |  6 11 17 | 19 16 14 | 20  1  9 |  4 21  3

class Program
{
    static Random random = new Random();
    static int students = 21;
    static int studentsPerGroup = 3;
    static int groups = students / studentsPerGroup;
    static List<int[]> history = new List<int[]>();

    static void Main(string[] args)
    {
        int[] order = Enumerable.Range(1, students).ToArray();
        int round = 1;

        history.Add(order);
        showOrder(round, order);

        while (++round < 500)
        {
            do
            {
                order = shuffle(ref order);
            }
            while (!allowed(ref order));

            history.Add(order);
            showOrder(round, order);
        }

        Console.WriteLine("ciao!");

    }

    private static bool allowed(ref int[] order)
    {
        for (int g = 0; g < groups; g++)
            for (int i = 0; i < studentsPerGroup - 1; i++)
                for (int j = i + 1; j < studentsPerGroup; j++)
                {
                    int student1 = order[g * studentsPerGroup + i];
                    int student2 = order[g * studentsPerGroup + j];

                    foreach (var ord in history)
                    {
                        int g1 = 0;
                        int g2 = 0;

                        for (int k = 0; k < students; k++)
                            if (ord[k] == student1)
                            {
                                g1 = k / studentsPerGroup;
                                break;
                            }
                        for (int k = 0; k < students; k++)
                            if (ord[k] == student2)
                            {
                                g2 = k / studentsPerGroup;
                                break;
                            }
                        if (g1 == g2)
                        {
                            return false;
                        }
                    }
                }

        return true;
    }

    static void showOrder(int n, int[] order)
    {
        string s = string.Format("{0,4}:", n);
        int i = 0;

        foreach(var st in order)
        {
            s += string.Format(" {0,2}", st);
            if (++i % studentsPerGroup == 0)
            {
                s += " |";
            }
        }

        Console.WriteLine(s);
    }

    static int[] shuffle(ref int[] arr)
    {
        return arr.OrderBy(i => random.Next()).ToArray();
    }
}

我无法分析21! = 5.1e1921 名学生的所有排列。因此，我采取了随机洗牌。