I'm trying to construct the list of all N digit long numbers with unique digits, but I can't figure out how to generalize it, as a part of a bigger problem, for which I need the list of all (1 to N) digit long numbers with unique digits.
Here is the hand-written code for n = 4:
for {
x1 <- 1 to 9
x2 <- 1 to 9
x3 <- 1 to 9
x4 <- 1 to 9
if (x1 != x2 && x2 != x3 && x3 != x4 && x1 != x3 && x1 != x4 && x2 != x4)
num4 = x1 + x2 * 10 + x3 * 100 + x4 * 1000
} yield num4
scala> "1234".combinations(2).toList
res9: List[String] = List(12, 13, 14, 23, 24, 34)
With a range:
scala> (1 to 9).combinations(4).toList
res12: List[scala.collection.immutable.IndexedSeq[Int]] = List(Vector(1, 2, 3, 4), Vector(1, 2, 3, 5), Vector(1, 2, 3, 6), Vector(1, 2, 3, 7), Vector(1, 2, 3, 8), Vector(1, 2, 3, 9), Vector(1, 2, 4, 5), Vector(1, 2, 4, 6), Vector(1, 2, 4, 7), Vector(1, 2, 4, 8), Vector(1, 2, 4, 9), Vector(1, 2, 5, 6), Vector(1, 2, 5, 7), Vector(1, 2, 5, 8), Vector(1, 2, 5, 9), Vector(1, 2, 6, 7), Vector(1, 2, 6, 8), Vector(1, 2, 6, 9), Vector(1, 2, 7, 8), Vector(1, 2, 7, 9), Vector(1, 2, 8, 9), Vector(1, 3, 4, 5), Vector(1, 3, 4, 6), Vector(1, 3, 4, 7), Vector(1, 3, 4, 8), Vector(1, 3, 4, 9), Vector(1, 3, 5, 6), Vector(1, 3, 5, 7), Vector(1, 3, 5, 8), Vector(1, 3, 5, 9), Vector(1, 3, 6, 7), Vector(1, 3, 6, 8), Vector(1, 3, 6, 9), Vector(1, 3, 7, 8), Vector(1, 3, 7, 9), Vector(1, 3, 8, 9), Vector(1, 4, 5...
As a List of Ints:
"123456789".combinations(4).map(_.toInt).toList
res37: List[Int] = List(1234, 1235, 1236, 1237, 1238, 1239, 1245, 1246, 1247, 1248, 1249, 1256, 1257, 1258, 1259, 1267, 1268, 1269, 1278, 1279, 1289, 1345, 1346, 1347, 1348, 1349, 1356, 1357, 1358, 1359, 1367, 1368, 1369, 1378, 1379, 1389, 1456, 1457, 1458, 1459, 1467, 1468, 1469, 1478, 1479, 1489, 1567, 1568, 1569, 1578, 1579, 1589, 1678, 1679, 1689, 1789, 2345, 2346, 2347, 2348, 2349, 2356, 2357, 2358, 2359, 2367, 2368, 2369, 2378, 2379, 2389, 2456, 2457, 2458, 2459, 2467, 2468, 2469, 2478, 2479, 2489, 2567, 2568, 2569, 2578, 2579, 2589, 2678, 2679, 2689, 2789, 3456, 3457, 3458, 3459, 3467, 3468, 3469, 3478, 3479, 3489, 3567, 3568, 3569, 3578, 3579, 3589, 3678, 3679, 3689, 3789, 4567, 4568, 4569, 4578, 4579, 4589, 4678, 4679, 4689, 4789, 5678, 5679, 5689, 5789, 6789)
And if you are in fact interested in the various permutations (the question has changed a bit since I wrote the above answers)
scala> "1234".combinations(2).toList.flatMap(_.permutations).map(_.toInt)
res51: List[Int] = List(12, 21, 13, 31, 14, 41, 23, 32, 24, 42, 34, 43)
What you're looking for is called monadic sequencing. When you use for comprehension such as
for(x <- Set(...)
y <- Set(...))
yield (x, y)
you can view it as having a pair of monadic computations (Set(...), Set(...)) and converting it into a monad holding a pair of results Set((...,...), (...,...), ...).
This can be generalized to sequences of arbitrary lengths. The scalaz library defines trait Traversable, which represents sequences for which we can define such an operation. It's traverse operation is more general and we can use it to define monadic sequencing:
import scalaz._
import scalaz.Scalaz._
import scala.collection.immutable._
def sequence[M[_]: Applicative, T[_], A](seq: T[M[A]])
(implicit t: Traverse[T]): M[T[A]] =
t.traverse(identity[M[A]], seq);
In our case, M will be Set and T will be Seq. So given a sequence of choices (represented as sets) of type Seq[Set[Int]], sequence will get us Set[Seq[Int]] which is the set of all possible combinations picked from the choices:
// a helper function
def set[A](seq: Seq[A]): Set[A] = Set(seq : _*);
// prints all sequences where the first number is from 1 to 9
// and the second number from 2 to 9:
println( sequence(List(set(1 to 9), set(2 to 9))) )
You can then filter the sequences where some number occurs more than once.
If you want to include this kind of filtering in the process, it will get more complicated. You need to keep some state during the monadic computation, which will hold what numbers remain available. Let's define
type Choices = Set[Int]
type DigitChoose[A] = StateT[Set,Choices,A]
So DigitChoose is a monad which has non-deterministic results (every operation produces a set of possible outcomes, like before), but also keeps a state of type Choices, which tells us what numbers are still available.
Next, we define some helper functions to help the compiler a bit (the general types are too much for it :)).
// See http://stackoverflow.com/q/7782589/1333025 why we need this:
implicit val applicativeDC: Applicative[DigitChoose]
= implicitly[Monad[DigitChoose]]
def sequenceDC[A](seq: Seq[DigitChoose[A]]): DigitChoose[Seq[A]]
= sequence(seq);
so now we have monadic sequencing defined over DigitChoose for sequences.
Using DigitChoose we can define operations that pick a digit from one of available ones and update the state (remove the chosen digit from the set):
// Pick any of the available digits:
def choose: DigitChoose[Int] =
stateT((s: Choices) => for(i <- s) yield (s - i, i));
and some restricted variants that restrict the choice of digits:
// Pick an available digit that is also in the given set of choices:
def choose(c: Choices): DigitChoose[Int] =
stateT((s: Choices) => for(i <- s intersect c ) yield (s - i, i));
// Pick an available digit that is also in the given set of choices:
def choose(cs: Seq[Int]): DigitChoose[Int]
= choose(cs.toSet);
Finally, we do things like:
// First digit is unrestricted
// Second digit is from 1 to 3
// Third digit is from 1 to 2
// ... and no digits will be the same!
val choices = Seq(choose, choose(1 to 3), choose(1 to 2));
// Sequence the choices, given that we start with digits 1 to 9
println( sequenceDC(choices) ! Set(1 to 9 : _*) );
My approach would be to filter out the results you aren't interested in.
Filtering uses the property of Sets where they only have distinct values.
Cases where n>10 won't yield different results than cases where n=10, so we can default back to that.
def generateUniqueList(n: Int) = {
val sanitizedInput = if(n>10) 10 else n
0 to math.pow(10, sanitizedInput).toInt-1 filter(num => num.toString.toSeq.size == num.toString.toSet.size)
}
This won't yield the quickest solution, but its concept is simple and easy to understand.
Example:
val result = generateUniqueList(2)
//> result : scala.collection.immutable.IndexedSeq[Int] = Vector(0, 1, 2, 3, 4,
//| 5, 6, 7, 8, 9, 10, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 23, 24, 25, 26,
//| 27, 28, 29, 30, 31, 32, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 45, 46, 47,
//| 48, 49, 50, 51, 52, 53, 54, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 67, 68,
//| 69, 70, 71, 72, 73, 74, 75, 76, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 89,
//| 90, 91, 92, 93, 94, 95, 96, 97, 98)
