permutation-rs

Rust代码用于解决排列谜题。

教程

在本教程中，我们将学习如何解决Brainbow。让我们先创建一个新的项目。

cargo new --bin --name brainbow solve-brainbow

打开Cargo.toml并添加对permutation.rs的依赖。

permutation-rs = "1.1.0"

打开src/main.rs并引入permutation-rs。

#[macro_use]
extern crate permutation_rs;

接下来，我们将导入所有内容，以便开始使用Brainbow组。

use std::collections::HashMap;
use permutation_rs::group::{Group, GroupElement, Morphism};
use permutation_rs::group::special::SLPPermutation;
use permutation_rs::group::tree::SLP;
use permutation_rs::group::free::Word;
use permutation_rs::group::permutation::Permutation;

我们将专注于创建相应的Brainbow组。为此，我们引入了一个函数。

fn brainbow() -> Group<u64, SLPPermutation> {
    let transposition = SLPPermutation::new(
        SLP::Generator(0),
        permute!(
            0, 0,
            1, 1,
            2, 2,
            3, 5,
            4, 4,
            5, 3
        ),
    );

    let rotation = SLPPermutation::new(
        SLP::Generator(1),
        permute!(
            0, 1,
            1, 2,
            2, 3,
            3, 4,
            4, 5,
            5, 0
        ),
    );

    let gset: Vec<u64> = vec!(0, 1, 2, 3, 4, 5);
    let generators = vec!(transposition, rotation);

    Group::new(gset, generators)
}

让我们谈谈这里发生了什么。从签名中我们可以了解到，我们返回一个Group<u64, SLPPermutation>。组元素由SLPPermutation组成，作用于u64。一个SLPPermutation是由一个SLP和一个Permutation组合而成，还有一些额外的记账。我们将深入了解这究竟意味着什么。

在函数中，我们定义了两个生成器。你可以看到SLPPermutation是如何由一个SLP和一个Permutation组成的。注意，我们使用permute!宏创建了一个Permutation。例如

permute!(
  0, 0,
  1, 1,
  2, 2,
  3, 5,
  4, 4,
  5, 3
)

对应于以下不相交循环表示法中的排列 (3 5)。我们通过列出我们的群作用域的域元素来创建一个 gset，并且我们也收集我们的群的生成元。从这些元素中，我们创建实际的群。

有了创建群的可能性，我们应该开始使用它。在主函数调用中，调用 brainbow 函数并将其分配给一个变量。

let group = brainbow();

现在，是时候将 brainbow 混乱，并创建一个相应的群元素来检查。

let element = SLPPermutation::new(
    SLP::Identity,
    permute!(
        0, 1,
        1, 0,
        2, 5,
        3, 4,
        4, 3,
        5, 2
    ),
);

我们将使用我们的 group 来剥离这个元素。这确定了一些事情。它可以告诉我们这个元素是否在群中。我们将要学习的另一件事是，如果元素在群中，它将解决混乱的 brainbow 的单词。

let stripped = group.strip(element);

为了知道解决这个 brainbow 问题的序列，我们需要一个 Morphism。一个 Morphism 告诉我们如何将 SLP 元素映射到指令。

let morphism = morphism!(0, 't', 1, 'r');

让我们用它来解决我们的谜题。

if stripped.element.1.is_identity() {
    println!("{}", stripped.transform(&morphism).inverse());
} else {
    println!("Not solveable");
}

运行这个程序将输出

t^1r^4t^-1r^-1t^-1r^1t^1r^1

这将解决我们的谜题。

SLP 排列是什么？

我们之前说过，一个 SLPPermutation 是一个 SLP 和一个 Permutation 的组合。如果我们了解这些个别概念的含义，我们就能了解组合。

排列是什么？

排列是从一个集合到另一个集合的双射。基本上，它将一个集合的每个元素，例如 0, 1, 2 发送到该集合的一个元素。例如

0 -> 1
1 -> 2
2 -> 0

SLP 是什么？

SLP 是指 直线程序。它是可以与其他群元素一起执行的计算的描述。在这个项目中使用的实现与传统程序略有不同。它更类似于一个 抽象语法树。

例如，以下 SLP 的表示

(Product
  (Generator 0)
  (Inverse (Generator 1)))

以及一个将 生成器 0 映射到 (1 2) 并将 生成器 1 映射到 (1 2 3) 的映射，对应于排列 (2 3)