赤チャート(数学IA)の問題をpythonとRustで解いてみた①（順列）

数学IAの復習のために赤チャートを買ってみた。
自分が学んでいた頃とは、教育課程もかなり変わっているみたいなので、初見の部分と復習の部分があるが、基本的にほとんど忘れているので、一から勉強し直しながらその中の一部をプログラミングで解くことで数学の復習とプログラミングの勉強を併せてしていこうと思う。

基本的には、言語はPythonを使う予定。できればRustも交えていければ良いなという感じ。
問題は前からではなく、気になった問題を解いていく。

第１問 順列

最初は、赤チャートI+A　P352　「同じものを含む順列について」
AtcoderだとABCのA問題かB問題くらいかな

小問１

scienceの7文字を横一列に並べるときの並べ方の総数

※同じアルファベットは区別できないので、2回出現するc,eは区別できないので7!/(2!*2!)が答えとなる

Python ver

from collections import defaultdict
from math import factorial

P = defaultdict(int)
N = int(input())
S = list(input())

for s in S:
    P[s] += 1
ans1 = factorial(N)
for c in P.values():
    if c > 1:
        ans1 //= factorial(c)
print(ans1)

Rust ver

use proconio::input;
use std::collections::HashMap;

fn factorial(n: u64) -> u64 {
    (1..=n).product()
}

fn main() {
    input! {
        n: usize,
        s: String,
    }

    let mut p = HashMap::new();
    for c in s.chars() {
        *p.entry(c).or_insert(0) += 1;
    }

    let mut ans1 = factorial(s.len() as u64);
    for &count in p.values() {
        if count > 1 {
            ans1 /= factorial(count);
        }
    }
    println!("{}", ans1);
}

小問２

ccとeeという並べ方をともに含む並べ方の数
つまり、同じアルファベットがある場合、まとめたときの並べ方の数

Python ver

from collections import defaultdict
from math import factorial

P = defaultdict(int)
N = int(input())
S = list(input())

for s in S:
    P[s] += 1
ans2 = factorial(len(P))
print(ans2)

Rust ver

use proconio::input;
use std::collections::HashSet;

fn factorial(n: usize) -> usize {
    (1..=n).product()
}

fn main() {
    input! {
        _: usize,
        s: String,
    }

    let mut unique_chars = HashSet::new();
    for c in s.chars() {
        unique_chars.insert(c);
    }

    let ans2 = factorial(unique_chars.len());
    println!("{}", ans2);
}

小問３

s,i,nがこの順番に並ぶ並べ方の数
つまり、与えられた文字列に1個しか存在しないアルファベットの順番を元の順番で並べる並べ方の数

Python ver

from collections import defaultdict
from math import factorial

P = defaultdict(int)
N = int(input())
S = list(input())

for s in S:
    P[s] += 1
single_cnt = 0
for k, v in P.items():
    if v == 1:
        single_cnt += 1
import math

single_ans = math.comb(N, single_cnt)
not_single_ans = factorial(N - single_cnt)
for k, v in P.items():
    if v > 1:
        not_single_ans //= factorial(v)
ans3 = single_ans * not_single_ans
print(ans3)

Rust ver

use proconio::input;
use std::collections::HashMap;

fn factorial(n: usize) -> usize {
    (1..=n).product()
}

fn combinations(n: usize, k: usize) -> usize {
    if k > n {
        0
    } else {
        factorial(n) / (factorial(k) * factorial(n - k))
    }
}

fn main() {
    input! {
        _: usize,
        s: String,
    }

    let mut char_count = HashMap::new();
    for c in s.chars() {
        *char_count.entry(c).or_insert(0) += 1;
    }

    let mut single_cnt = 0;
    for &v in char_count.values() {
        if v == 1 {
            single_cnt += 1;
        }
    }

    let single_ans = combinations(s.len(), single_cnt);
    let mut not_single_ans = factorial(s.len() - single_cnt);
    for &v in char_count.values() {
        if v > 1 {
            not_single_ans /= factorial(v);
        }
    }

    let ans3 = single_ans * not_single_ans;
    println!("{}", ans3);
}