バランスの取れたカッコ列と二分木は 1 対 1 に対応します。二分木を行きがけ順で巡回するとき、途中の節では左カッコ ( を出力して左右の枝をたどり、葉に到達したら右カッコ ) を出力すると、カッコ列を生成することができます。
リスト : カッコ列と二分木
#[derive(Debug)]
enum Tree {
Leaf,
Node(Box<Tree>, Box<Tree>)
}
// カッコ列を二分木に変換
fn kakko_to_tree(ks: &str) -> Tree {
fn kakko_sub(i: usize, ks: &Vec<char>) -> (Tree, usize) {
if ks.len() == i {
(Tree::Leaf, i)
} else if ks[i] == ')' {
(Tree::Leaf, i + 1)
} else {
let (left, j) = kakko_sub(i + 1, ks);
let (right, k) = kakko_sub(j, ks);
(Tree::Node(Box::new(left), Box::new(right)), k)
}
}
let xs: Vec<char> = ks.chars().collect();
kakko_sub(0, &xs).0
}
// 二分木をカッコ列に変換
fn tree_to_kakko(tree: &Tree) -> String {
fn tree_sub(tree: &Tree, a: &mut String) {
match tree {
&Tree::Leaf => a.push(')'),
&Tree::Node(ref left, ref right) => {
a.push('(');
tree_sub(left, a);
tree_sub(right, a);
}
}
}
let mut a = String::new();
tree_sub(tree, &mut a);
a.pop();
a
}
fn main() {
for s in vec!["((()))", "(())()", "()()()", "()(())", "(()())"] {
let tree = kakko_to_tree(s);
print!("{} => ", s);
print!("{:?} => ", tree);
println!("{}", tree_to_kakko(&tree));
}
}
((())) => Node(Node(Node(Leaf, Leaf), Leaf), Leaf) => ((())) (())() => Node(Node(Leaf, Leaf), Node(Leaf, Leaf)) => (())() ()()() => Node(Leaf, Node(Leaf, Node(Leaf, Leaf))) => ()()() ()(()) => Node(Leaf, Node(Node(Leaf, Leaf), Leaf)) => ()(()) (()()) => Node(Node(Leaf, Node(Leaf, Leaf)), Leaf) => (()())
関数 tree_to_kakko() の実際の処理は局所関数 tree_sub() で行います。引数が葉 (Leaf) の場合、累積変数 a に右カッコを追加します。引数が節 (Node) の場合、累積変数 a に左カッコを追加します。そして、tree_sub() を再帰呼び出しして左部分木 left をたどり、それから右部分木 right をたどります。ただし、最後に余分な右カッコが付いてくるので、最後の文字を pop() で削除します。
二分木の場合、葉 (Leaf) の個数を n とすると、節 (Node) の個数は n - 1 になります。カッコ列と違って Leaf の個数が一つ多くなることに注意してください。
関数 kakko_to_tree() も局所関数 kakko_sub() で変換処理を行います。カッコ列 (文字列) はベクタに変換して引数 ks に渡します。ks の i 番目の要素が右カッコの場合は (Leaf, i + 1) を返します。左カッコの場合は、kakko_sub() を再帰呼び出しして左部分木 left を生成し、それから右部分木 right を生成します。あとは Node を生成して k といっしょに返すだけです。ただし、葉に対応する右カッコがひとつ少ないので、引数 i がベクタの終端に到達した場合は Leaf を返すようにします。
Four Four は数字を使ったパズルです。いろいろなルールがあるのですが、今回は簡易ルールで行きましょう。それでは問題です。
数字 4 を 4 つと＋, －, ×, ÷, （, ） を使って、答えが 1 から 10 になる式を作りなさい。数字は 4 だけではなく、44 や 444 のように合体させてもよい。また、－を符号として使うことは禁止する。
基本的には、数式を生成して答えをチェックするだけです。Four Fours の場合、4 つの数値に 3 つの演算子しかありませんから、数式のパターンは簡単に求めることができます。数式を二分木で表すと、次に示す 5 つのパターンになります。
Ｘ Ｘ Ｘ
／ ＼ ／ ＼ ／ ＼
／ ＼ ４ Ｙ Ｙ ４
Ｙ Ｚ ／ ＼ ／ ＼
／ ＼ ／ ＼ ４ Ｚ Ｚ ４
４ ４ ４ ４ ／ ＼ ／ ＼
４ ４ ４ ４
（１） （２） （３）
Ｘ Ｘ
／ ＼ ／ ＼
４ Ｙ Ｙ ４
／ ＼ ／ ＼
Ｚ ４ ４ Ｚ
／ ＼ ／ ＼
４ ４ ４ ４
（４） （５）
図 : 数式のパターン（二分木）
X, Y, Z が演算子を表します。これを式で表すと、次のようになります。
あとは、X, Y, Z に演算子 +, -, *, / を入れて数式を計算すればいいわけです。Four Fours は数字を合体できるので、数字が 3 つで演算子が 2 つ、数字が 2 つで演算子が 1 つ、というパターンもあります。演算子が 1 つの場合は簡単ですね。演算子が 2 つの場合は、次の式になります。
a, b, c が数字で X, Y が演算子を表しています。数字は 4 か 44 になります。この場合、a, b, c の組み合わせを生成する必要があります。組み合わせを (a, b, c) で表すと、(4, 4, 44), (4, 44, 4), (44, 4, 4) の 3 通りとなります。これと演算子の組み合わせにより数式を生成して、答えを求めてチェックします。
それではプログラムを作りましょう。今回は浮動小数点数ではなく、以前作成した「有理数」を使います。ratio.rs をライブラリ (クレート) として使用できるように修正します。具体的には公開する名前 (構造体とかメソッドなど) に pub を付けるだけです。詳細はプログラムリストをお読みくださいませ。
まずは最初に、数式を表す二分木を定義します。
リスト : 数式を表す二分木 (演算子は char で表す)
enum Expr {
Leaf(Ratio),
Node(char, Box<Expr>, Box<Expr>)
}
use Expr::*;
数式は列挙型 Expr で表します。Leaf に数値を格納し、Node が節を表します。演算子は文字 '+', '*', '-', '/' で定義します。
次は式を計算する関数 calc_expr() を作ります。
リスト : 式の計算
fn calc_expr(expr: &Expr) -> Result<Ratio, ()> {
match expr {
&Leaf(n) => Ok(n),
&Node(op, ref left, ref right) => {
let lv = calc_expr(left)?;
let rv = calc_expr(right)?;
match op {
'+' => Ok(lv + rv),
'-' => Ok(lv - rv),
'*' => Ok(lv * rv),
'/' => {
if rv.numer() == 0 {
Err(())
} else {
Ok(lv / rv)
}
},
_ => Err(())
}
}
}
}
calc_expr() の返り値の型は Result<Ratio, ()> です。Leaf の場合は数値を Ok に包んで返します。Node の場合、左辺式 left と右辺式 right を calc_expr() で計算して、値を変数 lv, rv にセットします。あとは、演算子 op に従って計算するだけです。徐算の場合、右辺値が 0 であれば Err(()) を返すことに注意してください。。
次は式を表示する関数 print_expr() を作ります。
リスト : 式の表示
fn print_expr(expr: &Expr) {
match expr {
&Leaf(n) => print!("{}", n),
&Node(op, ref left, ref right) => {
print!("(");
print_expr(left);
print!(" {} ", op);
print_expr(right);
print!(")");
}
}
}
式の表示は簡単です。Leaf の場合は格納されている数値を表示します。Node の場合、左カッコを表示して、二分木を通りがけ順で巡回して、右カッコを表示するだけです。
次は式を生成する関数を作ります。
リスト : 式の生成
fn make_node(op: char, left: Expr, right: Expr) -> Expr {
Node(op, Box::new(left), Box::new(right))
}
fn make_expr(op1: char, op2: char, op3: char) -> Vec<Expr> {
let n = Ratio::from_integer(4);
vec![make_node(op1, make_node(op2, make_node(op3, Leaf(n), Leaf(n)), Leaf(n)), Leaf(n)),
make_node(op1, make_node(op2, Leaf(n), Leaf(n)), make_node(op3, Leaf(n), Leaf(n))),
make_node(op1, Leaf(n), make_node(op2, Leaf(n), make_node(op3, Leaf(n), Leaf(n)))),
make_node(op1, Leaf(n), make_node(op2, make_node(op3, Leaf(n), Leaf(n)), Leaf(n))),
make_node(op1, make_node(op2, Leaf(n), make_node(op3, Leaf(n), Leaf(n))), Leaf(n))]
}
関数 make_node() は Node を生成します。あとは、make_node() を使って式を二分木として提議するだけです。make_expr() は 3 つの演算子と 4 つの数値、make_expr2() は 2 つの演算子と 3 つの数値、make_expr3() は 1 つの演算子と 2 つの数値の式をベクタに格納して返します。プログラムは簡単なので説明は省略します。詳細はプログラムリストをお読みくださいませ。
次は式を計算して結果を表示する関数 exec_expr() を作ります。
リスト : 式の評価
fn exec_expr(expr: &Expr) {
match calc_expr(&expr) {
Ok(n) => {
if n.is_integer() {
let m = n.to_integer();
if m > 0 && m <= 10 {
print_expr(&expr);
println!(" = {}", m);
}
}
},
_ => ()
}
}
calc_expr() で式 expr を計算して、結果が Ok(n) の場合、n が整数で範囲内 (0 < n <= 10) であることを確認します。あとは print_expr() で式を表示するだけです。Err() の場合は何もしません。
最後に main() を作ります。
リスト : メイン関数
fn main() {
let ops = vec!['+', '-', '*', '/'];
for op1 in &ops {
for op2 in &ops {
for op3 in &ops {
for expr in make_expr(*op1, *op2, *op3) {
exec_expr(&expr);
}
}
}
}
for op1 in &ops {
for op2 in &ops {
for expr in make_expr2(*op1, *op2) {
exec_expr(&expr);
}
}
}
for op1 in &ops {
for expr in make_expr3(*op1) {
exec_expr(&expr);
}
}
}
main() は演算子の組み合わせを生成して数式を作り、それを exec_expr() に渡して評価するだけです。
これでプログラムは完成です。さっそく実行してみたところ、全部で 100 通りの式が出力されました。このプログラムは重複解のチェックを行っていないので、多数の式が出力されることに注意してください。実行結果の一部を示します。
((4 - 4) + (4 / 4)) = 1 ((4 / 4) + (4 / 4)) = 2 (((4 + 4) + 4) / 4) = 3 (4 + (4 * (4 - 4))) = 4 (((4 * 4) + 4) / 4) = 5 (((4 + 4) / 4) + 4) = 6 (4 + (4 - (4 / 4))) = 7 ((4 + 4) + (4 - 4)) = 8 ((4 + 4) + (4 / 4)) = 9 ((44 - 4) / 4) = 10
この中で、10 になる式は (44 - 4) / 4 しかありません。数字 4 を 4 つと＋, －, ×, ÷, ( , ) だけでは、10 になる式を作ることはできないのですね。
//
// ratio.rs : 簡単な有理数
//
// Copyright (C) 2017-2024 Makoto Hiroi
//
use std::ops::{Add, Div, Mul, Sub};
use std::fmt;
#[derive(PartialEq, Debug, Copy, Clone)]
pub struct Ratio {
numerator: i64, // 分子
denominator: i64 // 分母
}
// ユークリッドの互除法
fn gcd(a: i64, b: i64) -> i64 {
if b == 0 {
a
} else {
gcd(b, a % b)
}
}
impl fmt::Display for Ratio {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
if self.denominator == 1 {
write!(f, "{}", self.numerator)
} else {
write!(f, "{}/{}", self.numerator, self.denominator)
}
}
}
impl Ratio {
pub fn new(p: i64, q: i64) -> Ratio {
if q == 0 { panic!("Ratio: divide by zero"); }
let g = gcd(p.abs(), q.abs());
let s = if q < 0 { -1 } else { 1 };
Ratio { numerator: s * p / g, denominator: s * q / g}
}
pub fn from_integer(n: i64) -> Ratio {
Ratio { numerator: n, denominator: 1 }
}
pub fn to_integer(&self) -> i64 {
self.numerator / self.denominator
}
pub fn to_float(&self) -> f64 {
self.numerator as f64 / self.denominator as f64
}
pub fn numer(&self) -> i64 { self.numerator }
pub fn denom(&self) -> i64 { self.denominator }
pub fn is_integer(&self) -> bool {
self.denominator == 1
}
}
impl Add for Ratio {
type Output = Ratio;
fn add(self, other: Ratio) -> Ratio {
let p = self.numerator * other.denominator + other.numerator * self.denominator;
let q = self.denominator * other.denominator;
Ratio::new(p, q)
}
}
impl Sub for Ratio {
type Output = Ratio;
fn sub(self, other: Ratio) -> Ratio {
let p = self.numerator * other.denominator - other.numerator * self.denominator;
let q = self.denominator * other.denominator;
Ratio::new(p, q)
}
}
impl Mul for Ratio {
type Output = Ratio;
fn mul(self, other: Ratio) -> Ratio {
let p = self.numerator * other.numerator;
let q = self.denominator * other.denominator;
Ratio::new(p, q)
}
}
impl Div for Ratio {
type Output = Ratio;
fn div(self, other: Ratio) -> Ratio {
let p = self.numerator * other.denominator;
let q = self.denominator * other.numerator;
Ratio::new(p, q)
}
}
//
// fours.rs : Four Fours
//
// Copyright (C) 2017-2024 Makoto Hiroi
//
extern crate ratio;
use ratio::Ratio;
// 数式を表す二分木 (演算子は char で表す)
enum Expr {
Leaf(Ratio),
Node(char, Box<Expr>, Box<Expr>)
}
use Expr::*;
// 式の計算
fn calc_expr(expr: &Expr) -> Result<Ratio, ()> {
match expr {
&Leaf(n) => Ok(n),
&Node(op, ref left, ref right) => {
let lv = calc_expr(left)?;
let rv = calc_expr(right)?;
match op {
'+' => Ok(lv + rv),
'-' => Ok(lv - rv),
'*' => Ok(lv * rv),
'/' => {
if rv.numer() == 0 {
Err(())
} else {
Ok(lv / rv)
}
},
_ => Err(())
}
}
}
}
// 式の表示
fn print_expr(expr: &Expr) {
match expr {
&Leaf(n) => print!("{}", n),
&Node(op, ref left, ref right) => {
print!("(");
print_expr(left);
print!(" {} ", op);
print_expr(right);
print!(")");
}
}
}
// 式の生成
fn make_node(op: char, left: Expr, right: Expr) -> Expr {
Node(op, Box::new(left), Box::new(right))
}
fn make_expr(op1: char, op2: char, op3: char) -> Vec<Expr> {
let n = Ratio::from_integer(4);
vec![make_node(op1, make_node(op2, make_node(op3, Leaf(n), Leaf(n)), Leaf(n)), Leaf(n)),
make_node(op1, make_node(op2, Leaf(n), Leaf(n)), make_node(op3, Leaf(n), Leaf(n))),
make_node(op1, Leaf(n), make_node(op2, Leaf(n), make_node(op3, Leaf(n), Leaf(n)))),
make_node(op1, Leaf(n), make_node(op2, make_node(op3, Leaf(n), Leaf(n)), Leaf(n))),
make_node(op1, make_node(op2, Leaf(n), make_node(op3, Leaf(n), Leaf(n))), Leaf(n))]
}
fn make_expr2(op1: char, op2: char) -> Vec<Expr> {
let n = Ratio::from_integer(44);
let m = Ratio::from_integer(4);
vec![make_node(op1, make_node(op2, Leaf(n), Leaf(m)), Leaf(m)),
make_node(op1, Leaf(n), make_node(op2, Leaf(m), Leaf(m))),
make_node(op1, make_node(op2, Leaf(m), Leaf(n)), Leaf(m)),
make_node(op1, Leaf(m), make_node(op2, Leaf(n), Leaf(m))),
make_node(op1, make_node(op2, Leaf(m), Leaf(m)), Leaf(n)),
make_node(op1, Leaf(m), make_node(op2, Leaf(m), Leaf(n)))]
}
fn make_expr3(op: char) -> Vec<Expr> {
let i = Ratio::from_integer(444);
let j = Ratio::from_integer(44);
let k = Ratio::from_integer(4);
vec![make_node(op, Leaf(i), Leaf(k)),
make_node(op, Leaf(k), Leaf(i)),
make_node(op, Leaf(j), Leaf(j))]
}
// 式の評価
fn exec_expr(expr: &Expr) {
match calc_expr(&expr) {
Ok(n) => {
if n.is_integer() {
let m = n.to_integer();
if m > 0 && m <= 10 {
print_expr(&expr);
println!(" = {}", m);
}
}
},
_ => ()
}
}
fn main() {
let ops = vec!['+', '-', '*', '/'];
for op1 in &ops {
for op2 in &ops {
for op3 in &ops {
for expr in make_expr(*op1, *op2, *op3) {
exec_expr(&expr);
}
}
}
}
for op1 in &ops {
for op2 in &ops {
for expr in make_expr2(*op1, *op2) {
exec_expr(&expr);
}
}
}
for op1 in &ops {
for expr in make_expr3(*op1) {
exec_expr(&expr);
}
}
}
「テンパズル」は 4 桁の数字を 1 桁ずつに分解し、それに四則演算とカッコを使って 10 を作るパズルです。「メイク１０」とか「切符番号の問題」と呼ばれることもあります。一般的なルールの場合、数字の順番を入れ替えてもよいのですが、数字を結合させることはできません。
今回はテンパズルを解くプログラムを作ります。four fours のプログラムを改造すれば簡単に作成することができます。詳細はプログラムリストをお読みください。
//
// make10.rs : テンパズル
//
// Copyright (C) 2017-2024 Makoto Hiroi
//
extern crate ratio;
use ratio::Ratio;
// 順列の生成
fn permutations(n: usize, buff: &mut Vec<i64>, func: fn(&Vec<i64>) -> ()) {
if n == buff.len() {
func(buff)
} else {
for i in n .. buff.len() {
buff.swap(n, i);
permutations(n + 1, buff, func);
buff.swap(n, i);
}
}
}
//
// 数式を表す二分木 (演算子は char で表す)
//
enum Expr {
Leaf(Ratio),
Node(char, Box<Expr>, Box<Expr>)
}
use Expr::*;
// 式の計算
fn calc_expr(expr: &Expr) -> Result<Ratio, ()> {
match expr {
&Leaf(n) => Ok(n),
&Node(op, ref left, ref right) => {
let lv = calc_expr(left)?;
let rv = calc_expr(right)?;
match op {
'+' => Ok(lv + rv),
'-' => Ok(lv - rv),
'*' => Ok(lv * rv),
'/' => {
if rv.numer() == 0 {
Err(())
} else {
Ok(lv / rv)
}
},
_ => Err(())
}
}
}
}
// 式の表示
fn print_expr(expr: &Expr) {
match expr {
&Leaf(n) => print!("{}", n),
&Node(op, ref left, ref right) => {
print!("(");
print_expr(left);
print!(" {} ", op);
print_expr(right);
print!(")");
}
}
}
// 式の生成
fn make_node(op: char, left: Expr, right: Expr) -> Expr {
Node(op, Box::new(left), Box::new(right))
}
fn make_expr(op1: char, op2: char, op3: char, nums: &Vec<i64>) -> Vec<Expr> {
let a = Ratio::from_integer(nums[0]);
let b = Ratio::from_integer(nums[1]);
let c = Ratio::from_integer(nums[2]);
let d = Ratio::from_integer(nums[3]);
vec![make_node(op1, make_node(op2, make_node(op3, Leaf(a), Leaf(b)), Leaf(c)), Leaf(d)),
make_node(op1, make_node(op2, Leaf(a), Leaf(b)), make_node(op3, Leaf(c), Leaf(d))),
make_node(op1, Leaf(a), make_node(op2, Leaf(b), make_node(op3, Leaf(c), Leaf(d)))),
make_node(op1, Leaf(a), make_node(op2, make_node(op3, Leaf(b), Leaf(c)), Leaf(d))),
make_node(op1, make_node(op2, Leaf(a), make_node(op3, Leaf(b), Leaf(c))), Leaf(d))]
}
// チェック
fn check10(nums: &Vec<i64>) {
let ops = vec!['+', '*', '-', '/'];
for op1 in &ops {
for op2 in &ops {
for op3 in &ops {
for expr in make_expr(*op1, *op2, *op3, nums) {
match calc_expr(&expr) {
Ok(n) if n.is_integer() && n.numer() == 10 => {
print_expr(&expr);
println!(" = 10");
},
_ => ()
}
}
}
}
}
}
fn main() {
permutations(0, &mut vec![1,1,9,9], check10);
}
((1 + (1 / 9)) * 9) = 10 ((1 + (1 / 9)) * 9) = 10 (((1 / 9) + 1) * 9) = 10 (((1 / 9) + 1) * 9) = 10 ((1 + (1 / 9)) * 9) = 10 ((1 + (1 / 9)) * 9) = 10 (((1 / 9) + 1) * 9) = 10 (((1 / 9) + 1) * 9) = 10 (9 * (1 + (1 / 9))) = 10 (9 * ((1 / 9) + 1)) = 10 (9 * (1 + (1 / 9))) = 10 (9 * ((1 / 9) + 1)) = 10 (9 * ((1 / 9) + 1)) = 10 (9 * (1 + (1 / 9))) = 10 (9 * ((1 / 9) + 1)) = 10 (9 * (1 + (1 / 9))) = 10
このプログラムは重複解のチェックを行っていないので、多数の式が出力されます。興味のある方はプログラムを改造して、いろいろ試してみてください。
整数 n を 1 以上の自然数の和で表すことを考えます。これを「整数の分割」といいます。整数を分割するとき、同じ自然数を何回使ってもかまいませんが、並べる順序が違うだけのものは同じ分割とします。簡単な例を示しましょう。次の図を見てください。
─┬─ 6 : 6
│
├─ 5 ─ 1 : 5 + 1
│
├─ 4 ┬ 2 : 4 + 2
│ │
│ └ 1 ─ 1 : 4 + 1 + 1
│
├─ 3 ┬ 3 : 3 + 3
│ │
│ ├ 2 ─ 1 : 3 + 2 + 1
│ │
│ └ 1 ─ 1 ─ 1 : 3 + 1 + 1 + 1
│
├─ 2 ┬ 2 ┬ 2 : 2 + 2 + 2
│ │ │
│ │ └ 1 ─ 1 : 2 + 2 + 1 + 1
│ │
│ └ 1 ─ 1 ─ 1 ─ 1 : 2 + 1 + 1 + 1 + 1
│
└─ 1 ─ 1 ─ 1 ─ 1 ─ 1 ─ 1 : 1 + 1 + 1 + 1 + 1 + 1
図 : 整数 6 の分割
6 の場合、分割の仕方は上図のように 11 通りあります。この数を「分割数」といいます。今回は整数の分割の仕方を列挙するプログラムと分割数を求めるプログラムを作ります。詳しい説明は拙作のページ「Puzzle DE Programming: 分割数」をお読みくださいませ。
リスト : 分割数
// 整数の分割
fn partition_of_integer(n: i32) {
fn part_int(n: i32, k: i32, a: &mut Vec<i32>) {
if n == 0 {
println!("{:?}", a);
} else if n == 1 {
a.push(1);
println!("{:?}", a);
a.pop();
} else if k == 1 {
for _ in 0 .. n { a.push(1); }
println!("{:?}", a);
for _ in 0 .. n { a.pop(); }
} else {
if n >= k {
a.push(k);
part_int(n - k, k, a);
a.pop();
}
part_int(n, k - 1, a);
}
}
part_int(n, n, &mut vec![]);
}
// 分割数 (二重再帰なのでとても遅い)
fn partition_number(n: i64) -> i64 {
fn part_num(n: i64, k: i64) -> i64 {
if n == 1 || k == 1 {
1
} else if n < 0 || k < 1 {
0
} else {
part_num(n - k, k) + part_num(n, k - 1)
}
}
part_num(n, n)
}
// 動的計画法による高速化
fn partition_number_fast(n: usize) -> usize {
let mut table = vec![1; n + 1];
for k in 2 .. n + 1 {
for m in k .. n + 1 {
table[m] += table[m - k];
}
}
table[n]
}
fn main() {
partition_of_integer(5);
partition_of_integer(6);
for i in 0 .. 11 {
println!("{}", partition_number(i));
}
println!("{}", partition_number(40));
println!("{}", partition_number(60));
// println!("{}", partition_number(80));
println!("{}", partition_number_fast(80));
println!("{}", partition_number_fast(100));
println!("{}", partition_number_fast(200));
}
[5] [4, 1] [3, 2] [3, 1, 1] [2, 2, 1] [2, 1, 1, 1] [1, 1, 1, 1, 1] [6] [5, 1] [4, 2] [4, 1, 1] [3, 3] [3, 2, 1] [3, 1, 1, 1] [2, 2, 2] [2, 2, 1, 1] [2, 1, 1, 1, 1] [1, 1, 1, 1, 1, 1] 0 1 2 3 5 7 11 15 22 30 42 37338 966467 15796476 190569292 3972999029388
配列で表した集合 ls を分割することを考えます。たとえば、集合 [1, 2, 3] は次のように分割することができます。
1 分割 : [[1, 2, 3]] 2 分割 : [[1, 2], [3]], [[1, 3], [2]], [[1], [2, 3]] 3 分割 ; [[1], [2], [3]]
このように、分割した集合 xs は元の集合 ls の部分集合になります。分割した部分集合の積は空集合になり、分割した部分集合のすべての和を求めると元の集合になります。今回は分割の仕方をすべて求める関数 parititon_of_set() を作ります。
リスト : 集合の分割
fn partition_of_set(ls: &[i32]) {
fn part_set(ls: &[i32], a: &mut Vec<Vec<i32>>) {
if ls.len() == 0 {
println!("{:?}", a);
} else {
for i in 0 .. a.len() {
a[i].push(ls[0]);
part_set(&ls[1..], a);
a[i].pop();
}
a.push(vec![ls[0]]);
part_set(&ls[1..], a);
a.pop();
}
}
part_set(&ls[1..], &mut vec![vec![ls[0]]]);
}
fn main() {
partition_of_set(&[1, 2, 3]);
partition_of_set(&[1, 2, 3, 4]);
}
[[1, 2, 3]] [[1, 2], [3]] [[1, 3], [2]] [[1], [2, 3]] [[1], [2], [3]] [[1, 2, 3, 4]] [[1, 2, 3], [4]] [[1, 2, 4], [3]] [[1, 2], [3, 4]] [[1, 2], [3], [4]] [[1, 3, 4], [2]] [[1, 3], [2, 4]] [[1, 3], [2], [4]] [[1, 4], [2, 3]] [[1], [2, 3, 4]] [[1], [2, 3], [4]] [[1, 4], [2], [3]] [[1], [2, 4], [3]] [[1], [2], [3, 4]] [[1], [2], [3], [4]]
集合を分割する方法の総数を「ベル数 (Bell Number)」といい、次の漸化式で求めることができます。
今回はベル数を求める関数 bell_number() を作ります。
リスト : ベル数
// 組み合わせの数
fn combination_number(n: usize, r: usize) -> usize {
if n == r || r == 0 {
1
} else {
combination_number(n, r - 1) * (n - r + 1) / r
}
}
// ベル数
fn bell_number(n: usize) -> usize {
let mut bs = vec![1];
for i in 0 .. n {
let mut a = 0;
for j in 0 .. bs.len() {
a += combination_number(i, j) * bs[j];
}
bs.push(a);
}
bs[bs.len() - 1]
}
fn main() {
for i in 0 .. 11 {
println!("{}", bell_number(i));
}
println!("{}", bell_number(20));
println!("{}", bell_number(25));
}
bell_number() は公式をそのままプログラムするだけです。変数 bs のベクタにベル数を格納します。\({}_n \mathrm{C}_r\) は関数 combination_number() で求めます。次の for ループで \({}_n \mathrm{C}_r \times B(k)\) の総和を計算します。あとは、その値を push() で bs に追加するだけです。
1 1 2 5 15 52 203 877 4140 21147 115975 51724158235372 4638590332229999353
k 個の要素をもつ集合 ls を要素数が等しい m 個の部分集合に分割することを考えます。部分集合の要素数 n は k / m になります。分割の仕方をすべて出力する関数 group() を作ります。
リスト : 集合のグループ分け
fn group(ls: &[i32], n: usize, m: usize) {
fn group_sub(ls: &[i32], n: usize, m: usize, a: &mut Vec<Vec<i32>>) {
if ls.len() == 0 {
println!("{:?}", a);
} else {
for i in 0 .. a.len() {
if a[i].len() < n {
a[i].push(ls[0]);
group_sub(&ls[1..], n, m, a);
a[i].pop();
}
}
if a.len() < m {
a.push(vec![ls[0]]);
group_sub(&ls[1..], n, m, a);
a.pop();
}
}
}
group_sub(&ls[1..], n, m, &mut vec![vec![ls[0]]]);
}
fn main() {
group(&[1,2,3,4], 2, 2);
group(&[1,2,3,4,5,6], 2, 3);
group(&[1,2,3,4,5,6], 3, 2);
}
group() は partition_of_set() を改造するだけで簡単に作成することができます。生成する部分集合の大きさを n に、部分集合の個数を m に制限するだけです。i 番目の部分集合に要素を追加する場合、a[i].len() が n 未満であることをチェックします。新しい部分集合を追加する場合、a.len() が m 未満であることをチェックします。これで集合をグループに分けることができます。
[[1, 2], [3, 4]] [[1, 3], [2, 4]] [[1, 4], [2, 3]] [[1, 2], [3, 4], [5, 6]] [[1, 2], [3, 5], [4, 6]] [[1, 2], [3, 6], [4, 5]] [[1, 3], [2, 4], [5, 6]] [[1, 3], [2, 5], [4, 6]] [[1, 3], [2, 6], [4, 5]] [[1, 4], [2, 3], [5, 6]] [[1, 5], [2, 3], [4, 6]] [[1, 6], [2, 3], [4, 5]] [[1, 4], [2, 5], [3, 6]] [[1, 4], [2, 6], [3, 5]] [[1, 5], [2, 4], [3, 6]] [[1, 6], [2, 4], [3, 5]] [[1, 5], [2, 6], [3, 4]] [[1, 6], [2, 5], [3, 4]] [[1, 2, 3], [4, 5, 6]] [[1, 2, 4], [3, 5, 6]] [[1, 2, 5], [3, 4, 6]] [[1, 2, 6], [3, 4, 5]] [[1, 3, 4], [2, 5, 6]] [[1, 3, 5], [2, 4, 6]] [[1, 3, 6], [2, 4, 5]] [[1, 4, 5], [2, 3, 6]] [[1, 4, 6], [2, 3, 5]] [[1, 5, 6], [2, 3, 4]]