next permutation/prev permutation関数の使い方

10400 ワード
prev_permuatation 整列 next_permutation C テキストリンク

関数の概要


アルゴリズムヘッダファイルを
  • STL(#include)に追加すると、以下の関数でシーケンス
    • を得ることができる.
  • 関数にベクトルの反復器または配列のアドレスが追加された場合、次のシーケンス(1−2−3−4の次のシーケンスは1−2−4−3)または前のシーケンス(1−2−4−3の前のシーケンスは1−2−3−4)の結果がベクトルまたは配列に適用される.
  • next permutation:現在表示されている数列からパラメータまでの範囲を求め、trueを返します.次のシーケンスがない場合(次のシーケンスが前のシーケンスより小さい場合)、falseが返されます.
  • prev permutation:現在表示されている数列からパラメータまでの範囲内の前のシーケンスを求め、trueを返します.前のシーケンスがない場合(次のシーケンスが前のシーケンスより大きい場合)、falseが返されます.

    • next置換関数

  • 使用法:
    1-2-3-4配列があり、シーケンスを取得したい場合はnext permutationの関数を使用して、配列の値が次のシーケンス1-2-4-3になり、関数はtrueを返します.
  • コード
    • // 첫번째 인자가 구하고자 하는 순열의 시작, 두번째 인자가 순열의 끝
bool next_permutation (BidirectionalIterator first, BidirectionalIterator last);

// 아래처럼 직접 비교함수를 넣어줘도 됩니다.
bool next_permutation (BidirectionalIterator first, BidirectionalIterator last, Compare comp);
  • 実装コード
    • #include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(){

	// 1부터 4까지 저장할 벡터 선언 (배열도 가능!)
	vector<int> v(4);

	// 1부터 4까지 벡터에 저장
	for(int i=0; i<4; i++){
		v[i] = i+1;
	}

	// next_permutation을 통해서 다음 순열 구하기
	do{
		for(int i=0; i<4; i++){
			cout << v[i] << " ";
		}
		cout << '\n';
	}while(next_permutation(v.begin(),v.end()));

	return 0;

}

  • 実装結果
    1 2 3 4
    1 2 4 3
    1 3 2 4
    ...
    4 2 3 1
    4 3 1 2
    4 3 2 1

    • prev置換関数

  • 使用法:
    4-3-2-1配列があり、シーケンスを要求したい場合はprev permutationの関数を使用します.配列の値は次のシーケンス4-3-1-2になり、関数はtrueを返します.
  • コード
    • // 첫번째 인자가 구하고자 하는 순열의 시작, 두번째 인자가 순열의 끝
bool prev_permutation (BidirectionalIterator first, BidirectionalIterator last);

// 아래처럼 직접 비교함수를 넣어줘도 됩니다.
bool prev_permutation (BidirectionalIterator first, BidirectionalIterator last, Compare comp);
  • 実装コード
    • #include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
	// 1부터 4까지 저장할 벡터 선언 (배열도 가능!)
	vector<int> v(4);

	// 4부터 1까지 벡터에 저장
	for(int i=0; i<4; i++){
		v[i] = 4-i;
	}

	// prev_permutation을 통해서 이전 순열 구하기
	do{
		for(int i=0; i<4; i++){
			cout << v[i] << " ";
		}
		cout << '\n';
	}while(prev_permutation(v.begin(),v.end()));

	return 0;

}

  • 実装結果
    4 3 2 1
    4 3 1 2
    4 2 3 1
    ...
    1 3 2 4
    1 2 4 3
    1 2 3 4
    • [leetcode-python3] 238. Product of Array Except Self
    Chapter 1. DBとDBMS