0

我正在尝试构建具有唯一数字的所有 N 位长数字的列表，但我无法弄清楚如何将其概括为更大问题的一部分，为此我需要所有（1 到 N ) 具有唯一数字的长数字。

这是 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
4

3 回答 3

8 
scala> "1234".combinations(2).toList
res9: List[String] = List(12, 13, 14, 23, 24, 34)

范围：

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

作为整数列表：

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

如果您实际上对各种排列感兴趣（自从我写了上述答案以来，问题已经发生了一些变化）

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)
于 2013-07-01T20:39:31.297 回答
1

您正在寻找的是所谓的单子测序。当您使用for诸如

for(x <- Set(...)
    y <- Set(...))
  yield (x, y)

您可以将其视为具有一对单子计算(Set(...), Set(...))并将其转换为包含一对结果的单子Set((...,...), (...,...), ...)。

这可以推广到任意长度的序列。scalaz库定义了 trait ，Traversable它表示我们可以定义这样一个操作的序列。它的traverse操作更通用，我们可以用它来定义一元排序：

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

在我们的例子中，Mwill beSet和Twill be Seq。因此，给定一系列类型的选择（表示为集合）Seq[Set[Int]]，sequence将得到我们Set[Seq[Int]]从选择中选择的所有可能组合的集合：

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

然后，您可以过滤某些数字多次出现的序列。

如果你想在这个过程中包含这种过滤，它会变得更加复杂。您需要在单子计算期间保持一些状态，这将保存哪些数字仍然可用。让我们定义

type Choices = Set[Int]
type DigitChoose[A] = StateT[Set,Choices,A]

DigitChoose具有非确定性结果的 monad 也是如此（每个操作都会产生一组可能的结果，就像以前一样），但也保持 type 的状态Choices，它告诉我们哪些数字仍然可用。

接下来，我们定义一些辅助函数来帮助编译器（通用类型太多了：））。

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

所以现在我们为序列定义了单子DigitChoose序列。

使用DigitChoose我们可以定义从一个可用数字中选择一个数字并更新状态的操作（从集合中删除所选数字）：

// Pick any of the available digits:
def choose: DigitChoose[Int] =
  stateT((s: Choices) => for(i <- s) yield (s - i, i));

以及一些限制数字选择的受限变体：

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

最后，我们执行以下操作：

// 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 : _*) );

完整的代码可在 gist 上找到。

于 2013-07-02T06:56:46.123 回答
0

我的方法是过滤掉您不感兴趣的结果。
过滤使用集合的属性，其中它们只有不同的值。
n>10 的情况与 n=10 的情况不会产生不同的结果，因此我们可以默认返回。

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

这不会产生最快的解决方案，但它的概念简单易懂。

例子：

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)
于 2013-07-01T20:38:39.200 回答