All possible permutations of values for such a map

Consider such a map:

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

I want to get a list of all possible permutations of elements under Iterable, one element for each key. For this example, this would be something like:

// 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),...)

What would be a good way to accomplish that?

Answers


val m = Map("one" -> Iterable(1,2,3,4), "two" -> Iterable(5,6,7), "three" -> Iterable(8,9))

If you want every combination:

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

If you want each iterable to march up together, but stop when the shortest is exhuasted:

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

If you want each iterable to wrap around but stop when the longest one has been exhausted:

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

Edit: If you want arbitrary numbers of input lists, then you're best off with recursive functions. For Cartesian products:

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

and to replace zipped you want something like:

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

You can try these out with cart(m.values), zipper(m.values), and zipper(m.values.map(icf)).


Need Your Help

Jquery Isotope : How to fill empty gaps?

jquery jquery-isotope

I've tried basically every single hint / tip / advice to achieve that, but still, I got these empty ugly spaces while using Isotope.

Compilation type step for JavaScript

javascript jslint

I guess I am used to compiled static languages.

About UNIX Resources Network

Original, collect and organize Developers related documents, information and materials, contains jQuery, Html, CSS, MySQL, .NET, ASP.NET, SQL, objective-c, iPhone, Ruby on Rails, C, SQL Server, Ruby, Arrays, Regex, ASP.NET MVC, WPF, XML, Ajax, DataBase, and so on.