Zenn
🦀

permutationsってなんやねん 〜オレオレnext_permutation実装まで〜

2024/09/05に公開
Rust
algorithm
tech
  • 順列のこと
  • 最近AtCoderに参加して、詰まる問題のパーツになっている事が多い
  • 解説を見てもしれっと next_permutation() などと出てきてはい終わり、みたいなことも多い
  • 学業で登場するときなどは専ら順列の「数」など個数に着目するが、競プロの題材においては順列の「中身」に着目するんだなぁ

概念

  • いわゆる「箱の中に1~4の数字が書かれたカードが4枚あり、箱の中から1枚ずつ順番にすべてのカードを取ったときにありうる順番を列挙したもの」というやつ
+---------+
| box     |
+---------+
| 1,3,4   |
+---------+

+---+
| 2 |
+---+

+---------+
| box     |
+---------+
| 3,4     |
+---------+

+---+---+
| 2 | 1 |
+---+---+

+---------+
| box     |
+---------+
| 3       |
+---------+

+---+---+---+
| 2 | 1 | 4 |
+---+---+---+

+---------+
| box     |
+---------+
|         |
+---------+

+---+---+---+---+
| 2 | 1 | 4 | 3 |
+---+---+---+---+

↑これの取りうるパターンすべてを網羅する

チープな実装で掴む

  • ある内容を持つ Vec の順列を求める関数を書いてみる
fn permutations<T: Clone>(v: Vec<T>) -> Vec<Vec<T>> {
    // 継ぎ接ぎしていくので、 LinkedListに変換して進める
    let mut list = LinkedList::from_iter(v.iter().cloned());
    return permutations_core(&mut Vec::new(), &mut list);
}
fn permutations_core<T: Clone>(picked: &mut Vec<T>, list: &mut LinkedList<T>) -> Vec<Vec<T>> {
    if list.len() == 0 {
        return vec![picked.clone()];
    }

    let mut res = Vec::new();

    for i in 0..list.len() {
        let mut after = list.split_off(i);
        if let Some(v) = after.pop_front() {
            picked.push(v);
            list.append(&mut after);
            let mut vv = permutations_core(picked, list);
            res.append(&mut vv);

            // もとに戻す
            let v = picked.pop().unwrap();
            after = list.split_off(i);
            after.push_front(v);
        }
        list.append(&mut after);
    }

    return res;
}
  • 継ぎ接ぎしやすいよう、 LinkedList に変換している
  • リストの先頭方向を優先してひとつ取り、再帰的に実行している

テストを書く

  • 正しく振る舞っているか、ひとつひとつテストのassertを増やして確認した
#[cfg(test)]
mod tests {
    use crate::permutations;

    #[test]
    fn test_permutations() {
        let vv = permutations(vec![1, 2, 3, 4]);

        assert_eq!(vv[0], vec![1, 2, 3, 4]);
        assert_eq!(vv[1], vec![1, 2, 4, 3]);
    }
}
  • 上述の実装に基づけば vv[0] は素直に元の順番で選ばれるはず
  • vv[1] は3つ目の要素を選ぶときに、list の中身 [3,4] から 4 を選ぶはずだ
  • そのようにして最終的なテストは以下のようになった
#[cfg(test)]
mod tests {
    use crate::permutations;

    #[test]
    fn test_permutations() {
        let vv = permutations(vec![1, 2, 3, 4]);
        assert_eq!(vv.len(), 24);

        assert_eq!(vv[0], vec![1, 2, 3, 4]);
        assert_eq!(vv[1], vec![1, 2, 4, 3]);
        assert_eq!(vv[2], vec![1, 3, 2, 4]);
        assert_eq!(vv[3], vec![1, 3, 4, 2]);
        assert_eq!(vv[4], vec![1, 4, 2, 3]);
        assert_eq!(vv[5], vec![1, 4, 3, 2]);

        assert_eq!(vv[6], vec![2, 1, 3, 4]);
        assert_eq!(vv[7], vec![2, 1, 4, 3]);
        assert_eq!(vv[8], vec![2, 3, 1, 4]);
        assert_eq!(vv[9], vec![2, 3, 4, 1]);
        assert_eq!(vv[10], vec![2, 4, 1, 3]);
        assert_eq!(vv[11], vec![2, 4, 3, 1]);

        assert_eq!(vv[12], vec![3, 1, 2, 4]);
        assert_eq!(vv[13], vec![3, 1, 4, 2]);
        assert_eq!(vv[14], vec![3, 2, 1, 4]);
        assert_eq!(vv[15], vec![3, 2, 4, 1]);
        assert_eq!(vv[16], vec![3, 4, 1, 2]);
        assert_eq!(vv[17], vec![3, 4, 2, 1]);

        assert_eq!(vv[18], vec![4, 1, 2, 3]);
        assert_eq!(vv[19], vec![4, 1, 3, 2]);
        assert_eq!(vv[20], vec![4, 2, 1, 3]);
        assert_eq!(vv[21], vec![4, 2, 3, 1]);
        assert_eq!(vv[22], vec![4, 3, 1, 2]);
        assert_eq!(vv[23], vec![4, 3, 2, 1]);
    }
}
  • 4つの数字の集合から4つを選んだときの順列は 4! 通り、つまり 24 通り
  • assertの内容を観察すると、「入力が昇順ソートされていて、かつ重複がない場合」、得られた結果も昇順ソートされているようにみえる

パフォーマンスは悪い

#[cfg(test)]
mod tests {
    use crate::permutations;
    #[test]
    fn test_permutations_10() {
        let v = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
        let vv = permutations(v);
    }
}
// successes:
//    tests::test_permutations_speed
//
// test result: ok. 1 passed; 0 failed; 0 ignored; 0 measured; 1 filtered out; finished in 4.20s
  • assertはなく、ただ実行するだけのテスト
  • 要素は10個だが、4秒もかかってしまっている
    • 10! 通り。すなわち 3_628_800 通り。
      • 秒間 1_000_000 通りくらいは処理可能になってほしい

next_permutation に近づく

  • next_permutation() は、順列として列挙された配列たちを辞書順、あるいは昇順でソートした結果において、次の形を返すもの
    • 上述の permutations_core() はすべての組み合わせを網羅するまで止まらない
      • また、要素の重複に対応していない

要素の入れ替え

  • assertを見ると、末尾から入れ替えていくと良さそうである
| 1,2,3,4 |
|     ^ ^ |
|     j i |
↓ i と j を交換する
| 1,2,4,3 |
  • これ以上、v[3] と v[2] を入れ替えても新しい配列は生まれない
    • v[1] が次の値になるべきだろう
  • 末尾の値から、自身より小さい値を探していくと、どうやら v[1] と交換しそうである

ソートをかける、のではなく逆順？

| 1,2,4,3 |
|   j   i |
↓
| 1,3,4,2 |
| 1,3,2,4 | ← 期待する形
  • v[1] は望む形になったが、assertの順番と合わない
    • v[2] と v[3] を交換すればいい、それだけ？
  • ほかの事例も見る
| 1,4,3,2 | ← vv[5]
| j     i |
↓
| 2,4,3,1 | ← 交換直後
| 2,1,3,4 | ← 期待する形

| 1,5,4,3,2 |
| j       i |
↓
| 2,5,4,3,1 | ← 交換直後
| 2,1,3,4,5 | ← 期待する形
  • どうやら、交換した先より後ろの要素を逆順にすれば良さそうだ

不具合

| 1,3,4,2 |
| j     i |
↓
| 2,3,4,1 | ← 交換直後
| 2,1,4,3 | ← j+1 以降逆順
| 1,4,2,3 | ← 期待する形
  • 末尾の 2 より 冒頭の 1 のほうが小さいので、末尾より小さいものを探して入れ替えると当然そうなる
  • 注目しなければいけないのは「昇順になっている箇所」だった(v[1] < v[2])
  • 配列中のそれぞれの隣り合った要素が昇順であるとき、その配列は昇順だ
    • 末尾に近い昇順を崩していくことで次の形が見つかる

再帰関数からの脱却

| 1,3,5,4,2 |
|   i   j   |
↓
| 1,4,5,3,2 | ← 交換直後
| 1,4,2,3,5 | ← i+1 以降逆順
  • 着目すべき位置 i は「末尾に近い昇順なペアの、小さい方」になる
    • つまり、末尾に近い昇順のペアより後ろは「すべて降順」である
  • 末尾から交換すべき要素 j を探す
fn permutations_core<T: Clone + Ord>(v: &mut Vec<T>) -> Vec<Vec<T>> {
    let l = v.len();
    if l <= 1 {
        return vec![v.clone()];
    }

    let mut res = Vec::new();

    let mut i = l - 1;
    loop {
        let ii = i;
        i -= 1;
        // 昇順の箇所を探す
        if v[i] < v[ii] {
            for j in (ii..l).rev() {
                // 昇順が見つかったなら必ず交換できる
                if v[i] < v[j] {
                    res.push(v.clone());
                    v.swap(i, j);
                    v[ii..l].reverse();
                    break;
                }
            }
            // また末尾から探す
            i = l - 1;
            continue;
        }
        if i == 0 {
            break;
        }
    }
    res.push(v.clone());

    return res;
}

パフォーマンスは改善した

  • 1.11s 程度にまで改善された

next_permutation() にする

  • 少々整えれば next_permutation() にできる
fn permutations<T: Clone + Ord + Debug>(v: Vec<T>) -> Vec<Vec<T>> {
    let mut v = v.clone();
    let mut res = Vec::new();

    res.push(v.clone());
    while let Some(next) = next_permutations(&v) {
        res.push(next.clone());
        v = next;
    }

    return res;
}
fn next_permutation<T: Clone + Ord>(v: &Vec<T>) -> Option<Vec<T>> {
    let mut v = v.clone();
    let l = v.len();
    if l <= 1 {
        return Some(v);
    }

    let mut i = l - 1;
    loop {
        let ii = i;
        i -= 1;
        // 昇順の箇所を探す
        if v[i] < v[ii] {
            for j in (ii..l).rev() {
                // 昇順が見つかったなら必ず交換できる
                if v[i] < v[j] {
                    v.swap(i, j);
                    v[ii..l].reverse();
                    return Some(v);
                }
            }
        }
        if i == 0 {
            break;
        }
    }

    return None;
}

できた。Vec に生やすなりしてもよいかも。

むすび

  • permutations および、 next_permutation について理解を深めた
  • できたコードはスニペットとして活用していく
    • まだ既存の外部crateを使うほど馴染んでいないため

参考

GitHubで編集を提案

Discussion