如何就地洗牌

Question

我想在 Rust 中就地洗牌一个字符串，但我似乎遗漏了什么。修复可能是微不足道的...

use std::rand::{Rng, thread_rng};

fn main() {
    // I want to shuffle this string...
    let mut value: String = "SomeValue".to_string();
    let mut bytes = value.as_bytes();
    let mut slice: &mut [u8] = bytes.as_mut_slice();

    thread_rng().shuffle(slice);

    println!("{}", value); 
}

我得到的错误是

<anon>:8:36: 8:41 error: cannot borrow immutable dereference of `&`-pointer `*bytes` as mutable
<anon>:8         let mut slice: &mut [u8] = bytes.as_mut_slice();
                                            ^~~~~

我读到了 String::as_mut_vec()，但它不安全，所以我不想使用它。

Answer 1

我也是 Rust 的初学者，但是呢：

fn main() {
    // I want to shuffle this string...
    let value = "SomeValue".to_string();
    let mut bytes = value.into_bytes();

    bytes[0] = bytes[1]; // Shuffle takes place.. sorry but std::rand::thread_rng is not available in the Rust installed on my current machine.

    match String::from_utf8(bytes) { // Should not copy the contents according to documentation.
        Ok(s) => println!("{}", s),
        _ => println!("Error occurred!")
    }
}

另外请记住，在摆弄字节序列时，Rust 默认的字符串编码是 UTF-8。 ;)

这是一个很好的建议，引导我找到以下解决方案，谢谢！

use std::rand::{Rng, thread_rng};

fn main() {
    // I want to shuffle this string...
    let value: String = "SomeValue".to_string();
    let mut bytes = value.into_bytes();

    thread_rng().shuffle(&mut *bytes.as_mut_slice());

    match String::from_utf8(bytes) { // Should not copy the contents according to documentation.
        Ok(s) => println!("{}", s),
        _ => println!("Error occurred!")
    }
}

rustc 0.13.0-nightly (ad9e75938 2015-01-05 00:26:28 +0000)

Answer 2

没有很好的方法来做到这一点，部分原因是字符串的 UTF-8 编码的性质，部分原因是 Unicode 和文本的固有属性。

在一个 UTF-8 字符串中至少可以打乱三层内容：

原始字节
编码的代码点
字素

打乱原始字节可能会给出无效的 UTF-8 字符串作为输出，除非该字符串完全是 ASCII。非 ASCII 字符被编码为多字节的特殊序列，对这些字符进行混洗几乎肯定不会在最后以正确的顺序排列它们。因此，改组字节通常不好。

改组代码点（Rust 中的 char）更有意义，但仍然存在 "special sequences" 的概念，即所谓的 combining characters can be layered on to a single letter adding diacritics etc (e.g. letters like ä can be written as a plus U+0308, the codepoint representing the diaeresis）。因此，改组字符不会给出无效的 UTF-8 字符串，但它可能会破坏这些代码点序列并给出无意义的输出。

这让我想到字素：构成单个可见字符的代码点序列（如 ä 在写为一个或两个代码点时仍然是单个字素）。这将给出最可靠合理的答案。

然后，一旦您决定要洗牌，就可以制定洗牌策略：

如果字符串保证是纯 ASCII，用 .shuffle 打乱字节是明智的（在 ASCII 假设下，这等同于其他）
否则，没有标准的就地操作方式，可以将元素作为迭代器获取（.chars() 用于代码点，.graphemes(true) 用于字素），将它们放入带有 .collect::<Vec<_>>()，打乱向量，然后将所有内容收集回一个新的 String，例如.iter().map(|x| *x).collect::<String>().

处理代码点和字素的困难是因为 UTF-8 没有将它们编码为固定宽度，因此无法随机取出 codepoint/grapheme 并将其插入其他位置，或者交换两个元素高效...无需将所有内容解码为外部 Vec.

不在原位是不幸的，但字符串很难。

（如果您的字符串保证是 ASCII，那么使用 ascii 提供的 Ascii 之类的类型将是在类型级别保持直截了当的好方法。）

举个三者区别的例子，看一下：

fn main() {
    let s = "U͍̤͕̜̲̼̜n̹͉̭͜ͅi̷̪c̠͍̖̻o̸̯̖de̮̻͍̤";
    println!("bytes: {}", s.bytes().count());
    println!("chars: {}", s.chars().count());
    println!("graphemes: {}", s.graphemes(true).count());
}

它打印：

bytes: 57
chars: 32
graphemes: 7

(Generate your own, 演示将多个组合字符放在一个字母上。)

Answer 3

综合以上建议：

use std::rand::{Rng, thread_rng};

fn str_shuffled(s: &str) -> String {
    let mut graphemes = s.graphemes(true).collect::<Vec<&str>>();
    let mut gslice = graphemes.as_mut_slice();
    let mut rng = thread_rng();
    rng.shuffle(gslice);
    gslice.iter().map(|x| *x).collect::<String>()
}


fn main() {
    println!("{}", str_shuffled("Hello, World!"));
    println!("{}", str_shuffled("selam dünya"));
    println!("{}", str_shuffled("你好世界"));
    println!("{}", str_shuffled("γειά σου κόσμος"));
    println!("{}", str_shuffled("Здравствулте мир"));

}

如何就地洗牌

How to shuffle a str in place

rust