Suppose, I have an alphabet of N symbols and want to enumerate all different strings of length M over this alphabet. Does Scala provide any standard library function for that?
Asked
Active
Viewed 285 times
0
Michael
- 10,185
- 12
- 59
- 110
2 Answers
3
Taking inspiration from another answer:
val letters = Seq("a", "b", "c")
val n = 3
Iterable.fill(n)(letters) reduceLeft { (a, b) =>
for(a<-a;b<-b) yield a+b
}
Seq[java.lang.String] = List(aaa, aab, aac, aba, abb, abc, aca, acb, acc, baa, bab, bac, bba, bbb, bbc, bca, bcb, bcc, caa, cab, cac, cba, cbb, cbc, cca, ccb, ccc)
To work with something other than strings:
val letters = Seq(1, 2, 3)
Iterable.fill(n)(letters).foldLeft(List(List[Int]())) { (a, b) =>
for (a<-a;b<-b) yield(b::a)
}
The need for the extra type annotation is a little annoying but it will not work without it (unless someone knows another way).
-
1Can we get rid of the auxiliary list of size `n`? – Michael Nov 20 '11 at 14:21
-
@Michael yes using `fill` as 4e6 suggests. I'll edit my answer to reflect this. – Owen Nov 20 '11 at 21:43
-
Great! Thanks for the new version. – Michael Nov 21 '11 at 06:41
-
@Owen -- Is there a way to make this work for general sequences (not just strings)? – dsg Dec 02 '11 at 04:17
-
@dsg Yes though it is slightly more awkward – Owen Dec 02 '11 at 06:48
2
Another solution:
val alph = List("a", "b", "c")
val n = 3
alph.flatMap(List.fill(alph.size)(_))
.combinations(n)
.flatMap(_.permutations).toList
Update: If you want to get a list of strings in the output, then alph should be a string.
val alph = "abcd"
4e6
- 10,696
- 4
- 52
- 62
-
This doesn't seem to work when `n` is bigger than the size of `alph`. For example: `alph = List(0, 1)`, `n = 3` yields only 6 sequences, as opposed to the expected `8`. – dsg Dec 02 '11 at 04:16