一个算法问题

Question

给大家出一道题，在DataTable中存储了这样一张表：
数组序号           数组值
1                 1,2,3,4,6,10,12
2                 1,4,5
3                 3,4,5,6,7,11现在要从1,2,3数组中随机抽取不重复的数值，要求每个数组中抽取3个，要确保尽可能每个数组中都能抽取到3个，且所有抽取出的数值不重复，并且抽取到的数值个数尽可能的多，请大家设计算法。这个是示例数据，题目本意是，在每个数组中任意存储了一堆不重复的数值，然后从每个数组中随机抽取不重复的数值，每个数组抽取N个，要尽可能每个数组中都能抽取到N个，且所有抽取出的数值不重复，而且要求抽取出的数值个数尽可能的多。（要考虑到的问题是：1.有些数组中存储的数值个数可能小于等于N；2.不同的数组存储的数值可能有重复）转自其他论坛，看到挺有趣，拿来共享一下，大家一起出谋划策。

Answer 1

            int m = 3;//每组尽可能抽 m 个            List<List<int>> list = new List<List<int>>();
            // ... 初始化数据            List<int> result = new List<int>();
            Random rand = new Random();            for (int i = 0; i < list.Count; i++)
            {
                int count = 0;
                while (count < m)
                {
                    int value = list[i][rand.Next(list[i].Count)];
                    if (!result.Contains(value))
                    {
                        result.Add(value);
                        count++;
                    }                    list[i].Remove(value);//移除，下次随机抽就不会抽到
                }
            }

Answer 2

Sorry，忘了处理 n < m 
            int m = 3;//每组尽可能抽 m 个            List<List<int>> list = new List<List<int>>();
            // ... 初始化数据            List<int> result = new List<int>();
            Random rand = new Random();            for (int i = 0; i < list.Count; i++)
            {
                int count = 0;
                while (count < m)
                {
                    int value = list[i][rand.Next(list[i].Count)];
                    if (!result.Contains(value))
                    {
                        result.Add(value);
                        count++;
                    }                    list[i].Remove(value);//移除，下次随机抽就不会抽到                    if (list[i].Count == 0)
                        break;
                }
            }

Answer 3

SharePoint板块冷清啊~  再加上比较厉害的几个人好像很忙  不常来  就被我一个人独占了

Answer 4

如果不可以修改这个表，则另存一个副本来整。
为了尽量保证每个数组都能抽取N个，需要从元素最少的数组开始。
算法：
声明一个新的空间 aList 用于存放结果。
Start:;
对这些数组进行排序，排序标准是数组的长度，也就是数组中元素的个数。
从元素最少的数组开始。
到当前数组;
如果元素的数量少于N，则全部提取。否则随机选择N个数。将结果放到 aList 中未使用的空间;
在剩下的所有数组中执行下列算法：如果某个元素已存在于 aList 当中，则将它从当前数组删除。
如果已完成所有数组的运算，
则 goto Trim;
否则 goto Start;
Trim:;
将aList 中未使用的空间加以清除

Answer 5

你这么整不完善  假设最少数组中随机取出了N个，这N个恰恰也存在于另外的数组中，且另外的数组中不同的元素不够N个，此时第一个数组中如果取的是其他的元素，就不会产生冲突。这样的情况怎么整呢？我感觉关键点就是这里。

Answer 6

good

Answer 7

所以要从数字最少的数组当中进行抽取。如果后面的数组 aB 因为数字和前面的数组 aA 重复而被删除，那真的没什么办法如果先在 aA 里操作，aB 里能够取得的数就更少，达不到“要尽可能每个数组中都能抽取到N个”这个条件。如果这个条件改成"必须每个数组中都能抽取到N个"，那么这个条件是有可能达不到的，所以还是应该用我说的方法来做。

Answer 8

呵呵，确实是二分图的最大匹配问题，用最大流可以，也可以用Hopcroft-Karp来解，效率比一般的最大流算法要高一些，如果LZ对于图论比较有基础的话，应该可以看明白。

Answer 9

对于LZ给的例子，大概是这样，有一个源S，分别有3条容量为3的边，流向数组1,2,3,
数组1有7条容量为1的边，分别流向元素1,2,3,4,6,10,12，
数组2有3条容量为1的边，分别流向元素1,4,5
数组3有6条容量为1的边，分别流向元素3,4,5,6,7,11元素1,2,3,4,5,6,7,10,11,12个有一条容量为1的边流向共同的汇T，最多可选择的元素个数，就是源S => 汇T的最大流。LZ可以想象成一股水流，从S流到T，最大的流量是多少，就能够选取多少个元素。最普通的解法就是先用贪心，确定一个匹配方案，然后不断的在残流中，寻找增广路径，直到找不到新的增广路径，就表明已经是最大流了。(无法再压入更多的流量，就表明已经饱和了)，程序就不写了，大概是这个意思。