Xáo trộn một phần của một ArrayBuffer tại chỗ

Question

Tôi cần trộn một phần của một ArrayBuffer, tốt nhất là tại chỗ nên không cần sao chép. Ví dụ, nếu một ArrayBuffer có 10 yếu tố, và tôi muốn xáo trộn các yếu tố 3-7:

// Unshuffled ArrayBuffer of ints numbered 0-9 
0, 1, 2, 3, 4, 5, 6, 7, 8, 9 

// Region I want to shuffle is between the pipe symbols (3-7) 
0, 1, 2 | 3, 4, 5, 6, 7 | 8, 9 

// Example of how it might look after shuffling 
0, 1, 2 | 6, 3, 5, 7, 4 | 8, 9 

// Leaving us with a partially shuffled ArrayBuffer 
0, 1, 2, 6, 3, 5, 7, 4, 8, 9 

Tôi đã viết một cái gì đó giống như hình dưới đây, nhưng nó đòi hỏi bản và lặp lại trên vòng một vài lần. Có vẻ như có một cách hiệu quả hơn để làm điều này.

def shufflePart(startIndex: Int, endIndex: Int) { 

    val part: ArrayBuffer[Int] = ArrayBuffer[Int]() 

    for (i <- startIndex to endIndex) { 
    part += this.children(i) 
    } 

    // Shuffle the part of the array we copied 
    val shuffled = this.random.shuffle(part) 
    var count: Int = 0 

    // Overwrite the part of the array we chose with the shuffled version of it 
    for (i <- startIndex to endIndex) { 
    this.children(i) = shuffled(count) 
    count += 1 
    } 
} 

Tôi không thể tìm thấy gì về việc xáo trộn một bộ ArrayBuffer với Google. Tôi cho rằng tôi sẽ phải viết phương pháp của riêng mình, nhưng khi làm như vậy tôi muốn ngăn chặn các bản sao.

Answer 1

Tôi không hoàn toàn chắc chắn lý do tại sao nó phải được đặt ra - bạn có thể muốn suy nghĩ điều đó. Nhưng, giả sử đó là điều đúng đắn nên làm, điều này có thể làm điều đó:

import scala.collection.mutable.ArrayBuffer 

implicit def array2Shufflable[T](a: ArrayBuffer[T]) = new { 
    def shufflePart(start: Int, end: Int) = { 
    val seq = (start.max(0) until end.min(a.size - 1)).toSeq 
    seq.zip(scala.util.Random.shuffle(seq)) foreach { t => 
     val x = a(t._1) 
     a.update(t._1, a(t._2)) 
     a(t._2) = x 
    } 
    a 
    } 
} 

Bạn có thể sử dụng nó như:

val a = ArrayBuffer(1,2,3,4,5,6,7,8,9) 
println(a) 
println(a.shufflePart(2, 7)) 

chỉnh sửa: Nếu bạn sẵn sàng trả thêm chi phí một trình tự trung gian, điều này là hợp lý hơn, nói theo thuật toán:

def shufflePart(start: Int, end: Int) = { 
    val seq = (start.max(0) until end.min(a.size - 1)).toSeq 
    seq.zip(scala.util.Random.shuffle(seq) map { i => 
     a(i) 
    }) foreach { t => 
     a.update(t._1, t._2) 
    } 
    a 
    } 
} 

Answer 2

Nếu bạn có thể sử dụng một kiểu con của ArrayBuffer bạn có thể truy cập mảng cơ bản trực tiếp, vì ResizableArray có một bảo vệ thành viên array:

import java.util.Collections 
import java.util.Arrays 
import collection.mutable.ArrayBuffer 


val xs = new ArrayBuffer[Int]() { 
    def shuffle(a: Int, b: Int) { 
    Collections.shuffle(Arrays.asList(array: _*).subList(a, b)) 
    } 
} 

xs ++= (0 to 9) // xs = ArrayBuffer(0, 1, 2, 3, 4, 5, 6, 7, 8, 9) 
xs.shuffle(3, 8) // xs = ArrayBuffer(0, 1, 2, 4, 6, 5, 7, 3, 8, 9) 

Ghi chú:

• Các giới hạn trên cho java.util.List#subList là độc quyền
• Đó là một cách hợp lý hiệu quả vì Arrays#asList không tạo ra một tập mới của các yếu tố: nó được hỗ trợ bởi chính mảng đó (do đó không có phương thức thêm hoặc loại bỏ)
• Nếu sử dụng cho thực tế, bạn có thể muốn thêm giới hạn kiểm tra trên a và b