3

我有一个不可变的列表，我需要在其中交换位置。有什么简单的方法吗？

下面是我的代码：

def swap(i:Int, j:Int,li:List[T]):List[T]={
        if(i>=li.size && j >=li.size)
            throw new Error("invalie argument");

        val f = li(i)
        li(i) = li(j) //wont work
        li(j) = f;//wont work
        li;
    }

最初，我尝试将其转换为数组，更改位置，然后再次将其转换为列表。有什么简单的方法吗？

4

4 回答 4

15

这样做的一个简单（但不是非常有效的方法）是

val l = List(1,2,3)
l: List[Int] = List(1, 2, 3)

l.updated(0,l(2)).updated(2,l(0))
res1: List[Int] = List(3, 2, 1)
于 2012-12-09T10:20:39.217 回答
5

您只能在 中创建一个新列表O(n)。您可能想要使用不同的数据结构。你可以这样做： 

def swap[T](i:Int, j:Int,li:List[T]):List[T]={
    if(i>=li.size || j >=li.size || i >= j)
         throw new Error("invalid argument")

    li.dropRight(li.length - i) ::: (li(j) :: li.dropRight(li.length - j).drop(i+1)) ::: ((li(i) :: li.drop(j + 1)))
}

它不是很优雅，但它会完成这项工作。基本上，我在索引i&上对列表进行切片j，所以我有 5 个部分：之前列表的前缀i、 、 &i之间的部分排他性 、以及之后列表的后缀。从那里，它是与&交换的简单连接。如果您使用列表缓冲区，它可能会更有效，如果您将在可变的 s 上工作，则效率会更高...ijjjijArray

于 2012-12-09T10:07:00.423 回答
1

您可能想要尝试的一件事（取决于应用程序，例如您是否经常更新某个点等...）是使用“拉链”，见下文。您可能想要添加一个“moveTo”方法或类似方法。如果处理不可变列表，您可能会有更少的更新。我认为上面的简单解决方案可能最适合小型列表。

编辑：如果你知道你正在追逐彼此靠近的元素等，可能可以进行调整。

case class Zipper[A](focus: A, left: List[A], right: List[A]) {

  def fromZipper: List[A] = left ::: List(focus) ::: right

  /** Will throw NoSuchElementException if try to move beyond start. */

  /** directions are forward and backward across the list. */
  def moveForward: Zipper[A] = Zipper(right.head,left :+ focus,right.tail)
  def moveBackward: Zipper[A] = Zipper(left.last,left.init,focus :: right)

  /** Update the focus element. */
  def update(a: A): Zipper[A] = Zipper(a,left,right)
}


def apply[A](left: List[A], focus: A, right: List[A]): Zipper[A]
  = Zipper(focus,left,right)

def apply[A](xs: List[A]): Zipper[A]
    = Zipper(xs.head,List.empty[A],xs.tail)
于 2017-04-19T07:40:21.730 回答
0

我不确定这是否是这样做的好方法，但我这样的事情怎么样？

def swapElements(list: List[Any], first: Int, second: Int) = {
 def elementForIndex(index: Int, element: Any) = {
   if(index == first) {
     list(second)
   } else if(index == second){
     list(first)
   } else {
     element
   }
 }

 for(element <- ((0 to list.size - 1) zip list).to[List])
   yield elementForIndex(element._1, element._2)
}
于 2015-03-24T21:53:54.853 回答