Рекурсивных ходить значение в карте

Question

Я пытаюсь ходить Map[String,List[String]] рекурсивно для извлечения и сглаживать все значения, связанные с картой

val x = Map("a" -> List("b","c","d"), "b" -> List("f","g","h"), "f" -> List("i","j","k"), "g" -> List("p","q","r")) 

1. Для каждого из ключей, значения экстракта, то есть список
2. Для каждого пункт в списке значений:
   • Проверьте ключ существует, а затем извлечь значения

Продолжайте делать так рекурсивно, пока ключи не имеют значения и придавить значение списка для ключа

Результат должен быть

Map("a" -> List("b","c","d","f","g","h","i","j","k","p","q","r"), 
    "b" -> List("f","g","h","i","j","k","p","q","r"), 
    "f" -> List("i","j","k"), 
    "g" -> List("p","q","r")) 

Answer 1

Вы можете попробовать перебирать, пока не будет никаких изменений:

def getValues(dict: Map[String, List[String]]) = Iterator.iterate(dict) { _.mapValues { 
     _.flatMap(v => v :: dict.get(v).toList.flatten).toSet.toList 
    } filterNot { _._2.isEmpty } 
}.sliding(2) find { x => x.head == x.last } 

Это, безусловно, не является наиболее эффективным решением, но это довольно лаконична!

Answer 2

Попробуйте этот код:

def f(map: Map[String, List[String]]): Map[String, List[String]] = { 
    def f(x: Map[String, List[String]], acc: Map[String, List[String]]): Map[String, List[String]] = { 
    if (x.isEmpty) acc 
    else { 
     val keys = x.keySet 
     val (complex, simple) = x partition {_._2 exists {s => keys contains s}} 

     val newX = 
     (for ((ck, cl) <- complex) 
     yield (ck -> (simple.filter(x => cl.contains (x._1)).map(_._2).flatten ++ cl).toList)).toMap 

     f(newX, acC++ simple) 
    } 
    } 

    f(map, Map.empty) 
} 

val x = Map("a" -> List("b","c","d"), "b" -> List("f", "g", "h"), "f" -> List("i","j","k"), "g" -> List("p","q","r")) 

println(f(x)) //Map(f -> List(i, j, k), g -> List(p, q, r), b -> List(i, j, k, p, q, r, f, g, h), a -> List(i, j, k, p, q, r, f, g, h, b, c, d)) 

Однако это предполагается, что на карте нет рекурсии, например ("a" -> List("b")), ("b" -> List("a"). Если это произойдет, функция закончится бесконечным циклом. Вам придется добавить дополнительный код для обработки таких ситуаций.