n 목록에서 n 개의 고유 한 요소 선택

Question

프로그래밍 문제를 생각해 보았습니다. n 개의리스트가있는 경우, 개의 다른 요소 (각각 목록)를 출력하고 싶습니다. 나는 이것이 어떤 종류의 백 트랙 알고리즘으로 해결 될 수 있다고 생각하지만 올바르게 구현하는 법을 모르겠습니다.

Answer 1

의견에서 제안한대로 역 추적으로이를 해결할 수 있지만보다 효율적인 해결책은 최대 흐름 알고리즘을 사용하는 것입니다.
그래프로 표시하십시오. 소스, 싱크 각 개별 요소에 대한 노드 및 각 목록에 대한 노드. 원본은 각기 다른 요소에 연결되어 있습니다. 각 요소는 연결된 모든 목록에 연결되고 목록은 싱크 노드에 연결됩니다. 용량이있는 각 모서리 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); 
      } 
     }