从n个列表中选择n个唯一元素

Question

我一直在考虑编程问题。如果我们有n个列表，我们想要输出n个不同的元素（每个元素来自不同的列表）。我怀疑这可以通过某种回溯算法来解决，但我不知道如何正确实现它。

Answer 1

虽然您可以通过评论中建议的回溯来解决这个问题，但更有效的解决方案是使用max-flow算法。 将其建模为图形。 Source，Sink是每个不同元素的节点和每个列表的节点。您将源连接到每个不同的元素。每个元素都连接到它所在的每个列表，并且列表连接到汇聚节点。每个边缘的容量为1。 最大流量是您可以选择的不同列表中的不同元素的最大数量。

https://en.wikipedia.org/wiki/Maximum_flow_problem https://en.wikipedia.org/wiki/Edmonds%E2%80%93Karp_algorithm

Answer 2

我不确定这没有错误并解决了被问到的问题;我希望这次我能理解正确的问题:)

            //test
            int[][] arr = new int[][] {
            new int[] { 1, 1, 1, 1, 6 },
            new int[] { 1, 1, 1, 1, 5 },
            new int[] { 1, 1, 1, 4, 9 },
            new int[] { 1, 1, 3, 8, 1 },
            new int[] { 1, 2, 7, 1, 1 },
            new int[] { 1, 1, 1, 1, 1 } };

            int[] res = getItems(arr).ToArray(); //6,5,4,3,2,1

        private static IEnumerable<T> getItems<T>(T[][] array)
        {
            int N = array.GetLength(0);
            item<T>[] items = new item<T>[N];

            HashSet<T> hs = new HashSet<T>();
            for (int i = 0; i < N; i++)
            {
                bool ok = false;
                T[] arr = array[i];
                for (int j = items[i].Index; j < arr.Length; j++)
                {
                    T val = arr[j];
                    if (hs.Add(val))
                    {
                        items[i] = new item<T>() { Val = val, Index = j };
                        ok = true;
                        break;
                    }
                }
                if (!ok)
                {
                    item<T> item;
                    do
                    {
                        if (i == 0) throw new Exception("no solution");
                        items[i] = new item<T>();
                        item = items[--i];
                        item.Index++;
                        items[i] = item;
                    }
                    while (item.Index >= array[i].Length);
                    hs.Clear();
                    for (int j = 0; j < i; j++)
                        hs.Add(array[j][items[j].Index]);
                    i--;
                }
            }
            return hs;
        }
        private struct item<T>
        {
            public T Val;
            public int Index;

            public override string ToString()
            {
                return string.Format("Val:{0} Index:{1}", Val, Index);
            }
        }