悩んでいる人
C/C++言語で順列と組み合わせを全通り表示する方法を教えて！
こういった悩みにお答えします．
本記事の信頼性
- リアルタイムシステムの研究歴12年．
- 東大教員の時に，英語でOS（Linuxカーネル）の授業．
- 2012年9月～2013年8月にアメリカのノースカロライナ大学チャペルヒル校（UNC）コンピュータサイエンス学部で客員研究員として勤務．C言語でリアルタイムLinuxの研究開発．
- プログラミング歴15年以上，習得している言語: C/C++，Python，Solidity/Vyper，Java，Ruby，Go，Rust，D，HTML/CSS/JS/PHP，MATLAB，Assembler (x64，ARM)．
- 東大教員の時に，C++言語で開発した「LLVMコンパイラの拡張」，C言語で開発した独自のリアルタイムOS「Mcube Kernel」をGitHubにオープンソースとして公開．
- 2020年1月～現在はアメリカのノースカロライナ州チャペルヒルにあるGuarantee Happiness LLCのCTOとしてECサイト開発やWeb/SNSマーケティングの業務．2022年6月～現在はアメリカのノースカロライナ州チャペルヒルにあるJapanese Tar Heel, Inc.のCEO兼CTO．
- 最近は自然言語処理AIとイーサリアムに関する有益な情報発信に従事．
- （AI全般を含む）自然言語処理AIの論文の日本語訳や，AIチャットボット（ChatGPT，Auto-GPT，Gemini（旧Bard）など）の記事を50本以上執筆．アメリカのサンフランシスコ（広義のシリコンバレー）の会社でプロンプトエンジニア・マネージャー・Quality Assurance（QA）の業務委託の経験あり．
- （スマートコントラクトのプログラミングを含む）イーサリアムや仮想通貨全般の記事を200本以上執筆．イギリスのロンドンの会社で仮想通貨の英語の記事を日本語に翻訳する業務委託の経験あり．
こういった私から学べます．
C言語を独学で習得することは難しいです．
私にC言語の無料相談をしたいあなたは，公式LINE「ChishiroのC言語」の友だち追加をお願い致します．
私のキャパシティもあり，一定数に達したら終了しますので，今すぐ追加しましょう！
独学が難しいあなたは，元東大教員がおすすめするC言語を学べるオンラインプログラミングスクール5社で自分に合うスクールを見つけましょう．後悔はさせません！
C/C++言語で順列と組み合わせを全通り表示する方法を紹介します．
順列と組み合わせの個数を計算する方法を知りたいあなたは，関数の再帰呼び出しを読みましょう．
目次
C++言語で順列を全通り表示
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
namespace std { template <class BidirectionalIterator> bool next_permutation(BidirectionalIterator first, BidirectionalIterator last); // (1) C++03 template <class BidirectionalIterator> constexpr bool next_permutation(BidirectionalIterator first, BidirectionalIterator last); // (1) C++20 template <class BidirectionalIterator, class Compare> bool next_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp); // (2) C++03 template <class BidirectionalIterator, class Compare> constexpr bool next_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp); // (2) C++20 } |
C++言語で順列を全通り表示するためには，std::next_permutation関数を利用します．
std::next_permutation関数の引数には昇順にソート済みのコンテナ（ベクタ等）を設定します．
std::next_permutationを利用するコードは以下になります．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
/* * Author: Hiroyuki Chishiro * License: 2-Clause BSD */ #include <iostream> #include <vector> #include <algorithm> int main(void) { std::vector<int> v = {1, 2, 3, 4}; do { std::for_each(v.begin(), v.end(), [](int x) { std::cout << x << " "; }); std::cout << std::endl; } while (std::next_permutation(v.begin(), v.end())); return 0; } |
実行結果は以下になります．
順列を全通り表示していることがわかります．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
$ g++ next_permutation.cpp $ a.out 1 2 3 4 1 2 4 3 1 3 2 4 1 3 4 2 1 4 2 3 1 4 3 2 2 1 3 4 2 1 4 3 2 3 1 4 2 3 4 1 2 4 1 3 2 4 3 1 3 1 2 4 3 1 4 2 3 2 1 4 3 2 4 1 3 4 1 2 3 4 2 1 4 1 2 3 4 1 3 2 4 2 1 3 4 2 3 1 4 3 1 2 4 3 2 1 |
C言語で順列を全通り表示
C言語でC++言語のstd::next_permutation関数に相当するものはないので，順列を全通り表示するためには自作する必要があります．
C言語でnext_permutation関数の自作コードは以下になります．
\({}_4 \mathrm{P}_4\)の場合の全通り（24通り）を表示します．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 |
/* * Author: Hiroyuki Chishiro * License: 2-Clause BSD */ #include <stdio.h> #include <stdbool.h> void swap(int *pa, int *pb) { int tmp; tmp = *pa; *pa = *pb; *pb = tmp; } void reverse(size_t first, size_t last, int v[]) { while (first != last && first != --last) { swap(&v[first], &v[last]); first++; } } bool next_permutation(size_t first, size_t last, int v[]) { size_t i, j, k; if (first == last) { return false; } if (first + 1 == last) { return false; } i = last - 1; while (true) { j = i--; if (v[i] < v[j]) { k = last; while (!(v[i] < v[--k])) { } swap(&v[i], &v[k]); reverse(j, last, v); return true; } if (i == first) { reverse(first, last, v); return false; } } } int main(void) { int v[] = {1, 2, 3, 4}; size_t i; size_t n = sizeof(v) / sizeof(v[0]); do { for (i = 0; i < n; i++) { printf("%d ", v[i]); } printf("\n"); } while (next_permutation(0, n, v)); return 0; } |
実行結果は以下になります．
C++言語の実行結果と同様です．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
$ gcc next_permutation.c $ a.out 1 2 3 4 1 2 4 3 1 3 2 4 1 3 4 2 1 4 2 3 1 4 3 2 2 1 3 4 2 1 4 3 2 3 1 4 2 3 4 1 2 4 1 3 2 4 3 1 3 1 2 4 3 1 4 2 3 2 1 4 3 2 4 1 3 4 1 2 3 4 2 1 4 1 2 3 4 1 3 2 4 2 1 3 4 2 3 1 4 3 1 2 4 3 2 1 |
C++言語で組み合わせを全通り表示
C++言語で組み合わせを全通り表示するnext_combination関数に相当するものはないので，自作する必要があります．
next_combination関数の自作コードは以下になります．
\({}_5 \mathrm{C}_3\)の場合の全通り（10通り）を表示します．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 |
/* * Author: Hiroyuki Chishiro * License: 2-Clause BSD */ #include <algorithm> #include <iostream> #include <vector> template <class BidirectionalIterator, class Compare> bool next_combination(BidirectionalIterator first, BidirectionalIterator last, Compare comp, size_t r) { BidirectionalIterator subset = first + r; BidirectionalIterator src = subset; BidirectionalIterator dst = subset; if (first == last || first == subset || last == subset) { return false; } while (first != src) { src--; if (comp(*src, *(last - 1))) { while (*src >= *dst) { dst++; } std::iter_swap(src, dst); std::rotate(src + 1, dst + 1, last); std::rotate(subset, subset + (last - dst) - 1, last); return true; } } rotate(first, subset, last); return false; } template <class BidirectionalIterator> bool next_combination(BidirectionalIterator first, BidirectionalIterator last, size_t r) { using value_type = typename std::iterator_traits<BidirectionalIterator>::value_type; return next_combination(first, last, std::less<value_type>(), r); } int main(void) { std::vector<int> v{1, 2, 3, 4, 5}; size_t r = 3; do { std::for_each(v.begin(), v.begin() + r, [](int x) { std::cout << x << " "; }); std::cout << "| "; std::for_each(v.begin() + r, v.end(), [](int x) { std::cout << x << " "; }); std::cout << std::endl; } while (next_combination(v.begin(), v.end(), r)); return 0; } |
実行結果は以下になります．
組み合わせを全通り表示していることがわかります．
|
1 2 3 4 5 6 7 8 9 10 11 12 |
$ g++ next_combination.cpp $ a.out 1 2 3 | 4 5 1 2 4 | 3 5 1 2 5 | 3 4 1 3 4 | 2 5 1 3 5 | 2 4 1 4 5 | 2 3 2 3 4 | 1 5 2 3 5 | 1 4 2 4 5 | 1 3 3 4 5 | 1 2 |
C言語で組み合わせを全通り表示
C言語もnext_combination関数に相当するものはないので，組み合わせを全通り表示するためには自作する必要があります．
next_combination関数の自作コードは以下になります．
C++言語のコードと同様に，\({}_5 \mathrm{C}_3\)の場合の全通り（10通り）を表示します．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 |
/* * Author: Hiroyuki Chishiro * License: 2-Clause BSD */ #include <stdio.h> #include <stdbool.h> void swap(int *pa, int *pb) { int tmp; tmp = *pa; *pa = *pb; *pb = tmp; } void rotate(size_t first, size_t middle, size_t last, int v[]) { size_t middle_org; if (first == middle || middle == last) { return; } middle_org = middle; while (first != middle_org && middle != last) { swap(&v[first++], &v[middle++]); } if (first == middle_org) { rotate(first, middle, last, v); } else { rotate(first, middle_org, last, v); } } bool next_combination(size_t first, size_t last, size_t r, int v[]) { size_t subset = first + r; size_t src = subset; size_t dst = subset; if (first == last || first == subset || last == subset) { return false; } while (first != src) { src--; if (v[src] < v[last - 1]) { while (v[src] >= v[dst]) { dst++; } swap(&v[src], &v[dst]); rotate(src + 1, dst + 1, last, v); rotate(subset, subset + (last - dst) - 1, last, v); return true; } } rotate(first, subset, last, v); return false; } int main(void) { int v[] = {1, 2, 3, 4, 5}; size_t i; size_t n = sizeof(v) / sizeof(v[0]); size_t r = 3; do { for (i = 0; i < r; i++) { printf("%d ", v[i]); } printf("| "); for (i = r; i < n; i++) { printf("%d ", v[i]); } printf("\n"); } while (next_combination(0, n, r, v)); return 0; } |
実行結果は以下になります．
C++言語の実行結果と同様です．
|
1 2 3 4 5 6 7 8 9 10 11 12 |
$ gcc next_combination.c $ a.out 1 2 3 | 4 5 1 2 4 | 3 5 1 2 5 | 3 4 1 3 4 | 2 5 1 3 5 | 2 4 1 4 5 | 2 3 2 3 4 | 1 5 2 3 5 | 1 4 2 4 5 | 1 3 3 4 5 | 1 2 |
まとめ
C/C++言語で順列と組み合わせを全通り表示する方法を紹介しました．
順列と組み合わせを全通り表示する方法は定番のアルゴリズムですので，使いこなせるようにしましょう！
C言語を独学で習得することは難しいです．
私にC言語の無料相談をしたいあなたは，公式LINE「ChishiroのC言語」の友だち追加をお願い致します．
私のキャパシティもあり，一定数に達したら終了しますので，今すぐ追加しましょう！
独学が難しいあなたは，元東大教員がおすすめするC言語を学べるオンラインプログラミングスクール5社で自分に合うスクールを見つけましょう．後悔はさせません！
