Все возможные перестановки значений для такой карты - PullRequest
Новая
       25

Все возможные перестановки значений для такой карты

0 голосов
/ 23 мая 2011

Рассмотрим такую ​​карту: 

Map("one" -> Iterable(1,2,3,4), "two" -> Iterable(3,4,5), "three" -> Iterable(1,2))

Я хочу получить список всех возможных перестановок элементов в Iterable, по одному элементу для каждого ключа.В этом примере это будет что-то вроде: 

// first element of "one", first element of "two", first element of "three"
// second  element of "one", second element of "two", second element of "three"
// third  element of "one", third element of "two", first element of "three"
// etc.
Seq(Iterable(1,3,1), Iterable(2,4,2), Iterable(3,5,1),...)

Какой хороший способ сделать это?

Ответы [ 3 ]

3 голосов
/ 23 мая 2011 
val m = Map("one" -> Iterable(1,2,3,4), "two" -> Iterable(5,6,7), "three" -> Iterable(8,9))

Если вы хотите, чтобы каждая комбинация: 

for (a <- m("one"); b <- m("two"); c <- m("three")) yield Iterable(a,b,c)

Если вы хотите, чтобы каждая итерация шла вместе, но остановитесь, когда самая короткая эксгустация: 

(m("one"), m("two"), m("three")).zipped.map((a,b,c) => Iterable(a,b,c))

Если выхотите, чтобы каждая итерация была обернута, но остановилась, когда самый длинный из них был исчерпан: 

val maxlen = m.values.map(_.size).max
def icf[A](i: Iterable[A]) = Iterator.continually(i).flatMap(identity).take(maxlen).toList
(icf(m("one")), icf(m("two")), icf(m("three"))).zipped.map((a,b,c) => Iterable(a,b,c))

Редактировать: если вам нужно произвольное количество входных списков, то лучше всего использовать рекурсивные функции.Для декартовых продуктов: 

def cart[A](iia: Iterable[Iterable[A]]): List[List[A]] = {
  if (iia.isEmpty) List()
  else {
    val h = iia.head
    val t = iia.tail
    if (t.isEmpty) h.map(a => List(a)).toList
    else h.toList.map(a => cart(t).map(x => a :: x)).flatten
  }
}

и для замены zipped вам нужно что-то вроде: 

def zipper[A](iia: Iterable[Iterable[A]]): List[List[A]] = {
  def zipp(iia: Iterable[Iterator[A]], part: List[List[A]] = Nil): List[List[A]] = {
    if (iia.isEmpty || !iia.forall(_.hasNext)) part
    else zipp(iia, iia.map(_.next).toList :: part)
  }
  zipp(iia.map(_.iterator))
}

Вы можете попробовать их с cart(m.values), zipper(m.values) и zipper(m.values.map(icf)).

2 голосов
/ 23 мая 2011

Если вы хотите получить декартово произведение, у меня есть решение для списков списков чего-либо .

xproduct (List (List (1, 2, 3, 4), List (3, 4, 5), List (1, 2)))    
res3: List[List[_]] = List(List(1, 3, 1), List(2, 3, 1), List(3, 3, 1), List(4, 3, 1), List(1, 3, 2), List(2, 3, 2), List(3, 3, 2), List(4, 3, 2), List(1, 4, 1), List(2, 4, 1), List(3, 4, 1), List(4, 4, 1), List(1, 4, 2), List(2, 4, 2), List(3, 4, 2), List(4, 4, 2), List(1, 5, 1), List(2, 5, 1), List(3, 5, 1), List(4, 5, 1), List(1, 5, 2), List(2, 5, 2), List(3, 5, 2), List(4, 5, 2))

Вызовите его с помощью Rex 'm: 

xproduct (List (m("one").toList, m("two").toList, m("three").toList))
1 голос
/ 24 мая 2011

Посмотрите на этот ответ . Вопрос о фиксированном количестве списков для объединения, но некоторые ответы касаются общего случая.

...