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

Question

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

Answer 1

尽管您可以按照评论中的建议通过回溯来解决此问题，但更有效的解决方案是使用最大流算法。
将其建模为图形。一个 Source，一个 Sink，每个不同元素的节点和每个列表的节点。您将源连接到每个不同的元素。每个元素都连接到它所在的每个列表，列表连接到一个汇节点。每条边的容量为 1.
最大流是您可以 select 来自不同列表的最大不同元素数。

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);
            }
        }

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

Choose n unique elements from n lists

algorithm

backtracking