4. 順列
著者:梅谷 武
順列を生成する処理を実装する。
作成:2024-06-22
更新:2024-10-30
4.1 課題
 探索空間がある集合の順列集合になることがある。ここでは与えられた集合の順列を生成する技法について検討する。

順列

 位数nの集合Aの順列じゅんれつ, partial permutation(partial permutation)とはAのある部分集合Bの元を並べた列のことである。これは言い換えればBの位数をrとするとき、一対一対応
{0,1,⋯,r－1} longrightarrow E
のことである。n個の元からr個選ぶ順列の総数をP(n,r)で表わすと
P(n,r) =
n!
(n－r)!
となる。

課題

 n≧r＞0が与えられたとき、添字集合
{0, 1, ⋯, n－1}
をリストとして与え、そのr-順列全体をリストのリストとして求める。
4.2 プログラム

C++再帰

 まず再帰で書いてみる。
 perm1.cpp: 
#include <print>
#include <vector>
 
template <typename T>
void print_perms(std::vector<std::vector<T>> &perms) {
  for (const auto &perm : perms) {
    std::print("( ");
    for (const auto &val : perm)
      std::print("%d ", val);
    std::print(")\n");
  }
}
 
template <typename T>
void genPerms(std::vector<T> &lst,
              int r,
              std::vector<T> &temp,
              std::vector<bool> &used,
              std::vector<std::vector<T>> &result) {
  if (temp.size() == r) {
    result.push_back(temp);
    return;
  }
  for (int i = 0; i < lst.size(); ++i) {
    if (!used[i]) {
      used[i] = true;
      temp.push_back(lst[i]);
      genPerms(lst, r, temp, used, result);
      temp.pop_back();
      used[i] = false;
    }
  }
}
 
int main(int argc, char *argv[]) {
  if (argc != 3) {
    std::println("Usage: perm1 n r");
    return 1;
  }
  int n = std::stoll(argv[1]);
  int r = std::stoll(argv[2]);
  if ((n < 1) || (r < 1) || (r > n)) {
    std::println("Invalid arguments: ({}, {})", n, r);
    return 1;
  }
  std::println("arguments: ({}, {})", n, r);
  std::vector<int> lst;
  for (int i = 0; i < n; ++i)
    lst.push_back(i);
  std::vector<std::vector<int>> result;
  std::vector<int> temp;
  std::vector<bool> used(n, false);
  genPerms(lst, r, temp, used, result);
  std::println("total perms = {}", result.size());
  // print_perms(result);
  return 0;
}


 makefile: 
CPPG = g++
CPPL = clang++
CPPFLAGS = -std=c++23 -O2
SRC = perm1.cpp
EXES = perm1_g perm1_l
 
all: $(EXES)
 
perm1_g: $(SRC)
	$(CPPG) $(CPPFLAGS) -o $@ $(SRC)
 
perm1_l: $(SRC)
	$(CPPL) $(CPPFLAGS) -o $@ $(SRC)
 
clean:
	rm -f $(EXES)


 (n,r) = (10,10)で測定する。 
$ measure ./perm1_g 10 10
arguments: (10, 10)
total perms = 3628800
======================================
Process exited with status: 0
total time:  0.605177 [sec]
mem  size:     259540 [KB]
code size:        123 [KB]

$ measure ./perm1_l 10 10
arguments: (10, 10)
total perms = 3628800
======================================
Process exited with status: 0
total time:  0.598662 [sec]
mem  size:     258848 [KB]
code size:         96 [KB]

C++STL

 次にstd::next_permutationを使ってみる。
 perm2.cpp: 
#include <algorithm>
#include <print>
#include <vector>
 
template <typename T>
void print_perms(std::vector<std::vector<T>> &perms) {
  for (const auto &perm : perms) {
    std::print("( ");
    for (const auto &val : perm)
      std::print("{} ", val);
    std::print(")\n");
  }
}
 
template <typename T>
std::vector<std::vector<T>> genPerms(std::vector<T> &lst, int r) {
  std::vector<std::vector<T>> result;
  std::vector<bool> selector(lst.size(), false);
  std::fill(selector.begin(), selector.begin() + r, true);
  do {
    std::vector<T> current;
    for (size_t i = 0; i < lst.size(); ++i)
      if (selector[i])
        current.push_back(lst[i]);
    do {
      result.push_back(current);
    } while (next_permutation(current.begin(), current.end()));
  } while (prev_permutation(selector.begin(), selector.end()));
  return result;
}
 
int main(int argc, char *argv[]) {
  if (argc != 3) {
    std::println("Usage: perm2 n r");
    return 1;
  }
  int n = std::stoll(argv[1]);
  int r = std::stoll(argv[2]);
  if ((n < 1) || (r < 1) || (r > n)) {
    std::println("Invalid arguments: ({}, {})", n, r);
    return 1;
  }
  std::println("arguments: ({}, {})", n, r);
  std::vector<int> lst;
  for (int i = 0; i < n; ++i)
    lst.push_back(i);
  auto result = genPerms(lst, r);
  std::println("total perms = {}", result.size());
  // print_perms(result);
  return 0;
}


 makefile: 
CPPG = g++
CPPL = clang++
CPPFLAGS = -std=c++23 -O2
SRC = perm2.cpp
EXES = perm2_g perm2_l
 
all: $(EXES)
 
perm2_g: $(SRC)
	$(CPPG) $(CPPFLAGS) -o $@ $(SRC)
 
perm2_l: $(SRC)
	$(CPPL) $(CPPFLAGS) -o $@ $(SRC)
 
clean:
	rm -f $(EXES)


 (n,r) = (10,10)で測定する。 
$ measure ./perm2_g 10 10
arguments: (10, 10)
total perms = 3628800
======================================
Process exited with status: 0
total time:  0.359256 [sec]
mem  size:     259108 [KB]
code size:        123 [KB]

$ measure ./perm2_l 10 10
arguments: (10, 10)
total perms = 3628800
======================================
Process exited with status: 0
total time:  0.372344 [sec]
mem  size:     258936 [KB]
code size:         96 [KB]
 perm1より速い。

OCaml

 perm1.ml: 
open Printf
 
let map f lst =
  let rec aux acc = function
    | [] -> List.rev acc
    | x :: xs -> aux (f x :: acc) xs
    in
    aux [] lst
 
let rec remove x lst =
  match lst with
    | [] -> []
    | hd :: tl ->
        if hd = x then
          tl
        else
          hd :: remove x tl
 
let print_perms perms =
  List.iter (fun perm ->
    print_string "( ";
    List.iter (fun num -> print_int num; print_string " ") perm;
    print_endline ")"
  ) perms
 
let rec gen_perms lst r =
  if r = 0 then
    [[]]
  else
    List.concat (
      map (fun x ->
        map (fun perm -> x :: perm) (gen_perms (remove x lst) (r - 1))
      ) lst
    )
 
let () =
  let len = Array.length Sys.argv in
  if len <> 3 then
    printf "Usage: perm1 n r\n"
  else
    let n = int_of_string (Sys.argv.(1)) in
    let r = int_of_string (Sys.argv.(2)) in
    if (n < 1) || (r < 1) || (r > n)  then
      printf "Invalid arguments: (%d, %d)\n" n r
    else
      let lst = List.init n (fun i -> i) in
      let result = gen_perms lst r in
      printf "arguments: (%d, %d)\n" n r;
      printf "total perms = %d\n" (List.length result)
      (* print_perms result *)


 (n,r) = (10,10)で測定する。 
$ ocamlopt -O2 -o perm1 perm1.ml
$ measure ./perm1 10 10
arguments: (10, 10)
total perms = 3628800
======================================
Process exited with status: 0
total time:  5.721817 [sec]
mem  size:    1265316 [KB]
code size:       2365 [KB]

Racket

 perm1.rkt: 
#lang racket
(require iso-printf)
 
(define (print-perms perms)
  (for ([perm perms])
    (display "( ")
    (for ([val perm])
      (display val)
      (display " "))
    (display ")")
    (newline)))
 
(define (gen-perms lst r)
  (cond
    [(= r 0) (list '())]
    [else
     (apply append
        (map (λ (x)
          (map (λ (perm) (cons x perm))
            (gen-perms (remove x lst) (- r 1))))
         lst))]))
 
(define (main args)
  (let ([len (vector-length args)])
    (cond
      [(= len 2)
        (define n (string->number (vector-ref args 0)))
        (define r (string->number (vector-ref args 1)))
        (cond
          [(and (> n 0) (> r 0) (<= r n))
            (define lst (range n))
            (define result (gen-perms lst r))
            (printf "arguments: (%d, %d)\n" n r)
            (printf "total perms = %d\n" (length result))
            ;(print-perms result)
            ]
          [else
            (printf "Invalid arguments: (%d, %d)\n" n r)])]
      [else
        (printf "Usage: perm1 n r\n")])))
 
(main (current-command-line-arguments))


 (n,r) = (10,10)で測定する。 
$ raco exe perm1.rkt
$ measure ./perm1 10 10
arguments: (10, 10)
total perms = 3628800
======================================
Process exited with status: 0
total time:  7.889482 [sec]
mem  size:     890016 [KB]
code size:      12444 [KB]
4.3 まとめ
 測定結果を表にまとめる。単位は秒[sec]。
測定項目 GCC Clang OCaml Racket
permutation 0.359 0.372 5.722 7.889
語　　句
順列 じゅんれつ, partial permutation
ある集合の部分集合の元を並べた列。
 
This document is licensed under the MIT License.
Copyright (C) 2024 Takeshi Umetani