如何编写一个函数来打印给定字符串中所有可能的字符串？

Question

我正在尝试编写执行以下操作的代码： 1.有一个字符串“abc” 2.它打印出所有可能的字符串： abc, bac, cba, acb, cab, bca

以下是我编写的代码，但它始终给出错误：

def swap(n: Int, source: String): String = {
  val new_array = source.toCharArray
  if (n == 1) {
    new_string
  } else {
    var letter = new_array(n)
    letter = new_array(n-1)
    new_array(n-1) = letter
    var k = new String(new_array)
    swap(n, source)
  }
}

你能告诉我我的错误在哪里吗？

先感谢您。

Answer 1

scala> "abc".permutations.toList
res1: List[String] = List(abc, acb, bac, bca, cab, cba)

不过我不会把那个上交。

Answer 2

真正明显的错误是你把名字搞混了。

我可以看到 new_array 正在初始化，但随后您尝试使用 new_string，它似乎不是来自任何地方。

Answer 3

一件明显的事情是，您尝试交换两个字母，但顺序错误。应该是 可能

val letter = new_array(n)
new_array(n) = new_array(n-1)
new_array(n-1) = letter

还有其他错误，但因为这是作业......

Answer 4

正如之前所说，这是一个排列问题。使用 Scala 2.8，您可以编写类似的内容：

def permut[T](l: List[T]): List[List[T]] = {
  def retire(e: T, l: List[T]): List[T] = l match {
    case Nil                => Nil
    case x::xs if e == x    => xs
    case x::xs              => x::retire(e, xs)
  }

  l match {
    case Nil => List(Nil)
    case _   => for ( x <- l; p <- permut(retire(x, l))) yield (x :: p)
  }
}

然后：（

scala> permut("abc" toList) map {_.mkString }                              
res11: List[String] = List(abc, acb, bac, bca, cab, cba)

不过，我不确定我的排列是最佳的。至少，退休可能是尾递归的）

Answer 5

您想要编写一个 next_permutation 函数，其操作可以总结如下：查找数组中按降序排列的最长后缀 - 假设它从索引 m 开始。找出索引 m-1 处的值属于该后缀的位置，然后交换这两个值。然后将后缀从 m 反转到列表末尾，使其按排序顺序排列。