주어진 문자열에서 다음으로 큰 순열을 찾는 알고리즘
주어진 문자열의 다음으로 큰 순열을 찾는 효율적인 알고리즘을 원합니다.
Wikipedia에는 사전 순서 생성에 대한 멋진 기사 가 있습니다. 또한 다음 순열을 생성하는 알고리즘을 설명합니다.
인용 :
다음 알고리즘은 주어진 순열 후에 사전 식으로 다음 순열을 생성합니다. 주어진 순열을 제자리에서 변경합니다.
- 다음
i
과 같은 가장 높은 인덱스를 찾으십시오s[i] < s[i+1]
. 이러한 인덱스가 없으면 순열이 마지막 순열입니다.- 다음
j > i
과 같은 가장 높은 인덱스를 찾으십시오s[j] > s[i]
. 그러한 색인j
이기 때문에 그러한 것이 반드시 존재해야합니다i+1
.- 스왑
s[i]
과 함께s[j]
.- 인덱스 이후의 모든 요소의 순서를
i
마지막 요소까지 역순으로합니다 .
작동하는 훌륭한 솔루션은 https://www.nayuki.io/page/next-lexicographical-permutation-algorithm에 설명되어 있습니다 . 그리고 다음 순열이 존재하면 반환하고 그렇지 않으면 다음을 반환하는 솔루션 false
:
function nextPermutation(array) {
var i = array.length - 1;
while (i > 0 && array[i - 1] >= array[i]) {
i--;
}
if (i <= 0) {
return false;
}
var j = array.length - 1;
while (array[j] <= array[i - 1]) {
j--;
}
var temp = array[i - 1];
array[i - 1] = array[j];
array[j] = temp;
j = array.length - 1;
while (i < j) {
temp = array[i];
array[i] = array[j];
array[j] = temp;
i++;
j--;
}
return array;
}
숙제? 어쨌든, C ++ 함수 std :: next_permutation 또는 다음을 볼 수 있습니다.
http://blog.bjrn.se/2008/04/lexicographic-permutations-using.html
@Fleischpfanzerl이 인용 한 출처 사용
다음 사전 순열을 찾기 위해 다음 단계를 따릅니다.
nums = [0,1,2,5,3,3,0]
nums = [0]*5
curr = nums[-1]
pivot = -1
for items in nums[-2::-1]:
if items >= curr:
pivot -= 1
curr = items
else:
break
if pivot == - len(nums):
print('break') # The input is already the last possible permutation
j = len(nums) - 1
while nums[j] <= nums[pivot - 1]:
j -= 1
nums[j], nums[pivot - 1] = nums[pivot - 1], nums[j]
nums[pivot:] = nums[pivot:][::-1]
> [1, 3, 0, 2, 3, 5]
그래서 아이디어는 : 아이디어는 단계를 따르는 것입니다.
- 배열 끝에서 nums [i-1] <nums [i]가되는 인덱스 'pivot'을 찾습니다.
- nums [j]> nums [pivot-1]과 같은 인덱스 j를 찾습니다.
- 이 두 인덱스를 모두 바꿉니다.
- 피벗에서 시작하는 접미사 반전
다음 단계를 사용하여 주어진 문자열 S에 대해 다음으로 큰 사전 식 문자열을 찾을 수 있습니다.
1. Iterate over every character, we will get the last value i (starting from the first character) that satisfies the given condition S[i] < S[i + 1]
2. Now, we will get the last value j such that S[i] < S[j]
3. We now interchange S[i] and S[j]. And for every character from i+1 till the end, we sort the characters. i.e., sort(S[i+1]..S[len(S) - 1])
주어진 문자열은의 다음으로 큰 사전 식 문자열입니다 S
. next_permutation
C ++에서 함수 호출을 사용할 수도 있습니다 .
nextperm (a, n)
1. find an index j such that a[j….n - 1] forms a monotonically decreasing sequence.
2. If j == 0 next perm not possible
3. Else
1. Reverse the array a[j…n - 1]
2. Binary search for index of a[j - 1] in a[j….n - 1]
3. Let i be the returned index
4. Increment i until a[j - 1] < a[i]
5. Swap a[j - 1] and a[i]
O(n) for each permutation.
void Solution::nextPermutation(vector<int> &a) {
int i,j=-1,k,t=a.size();
for(i=0;i<t-1;i++)
{
if(a[i]<a[i+1])
j=i;
}
if(j==-1)
reverse(a.begin(),a.end());
else
{
for(i=j+1;i<t;i++)
{
if(a[j]<a[i])
k=i;
}
swap(a[j],a[k]);
reverse(a.begin()+j+1,a.end());
}
}
작동하는 훌륭한 솔루션은 https://www.nayuki.io/page/next-lexicographical-permutation-algorithm에 설명되어 있습니다 . 그리고 당신이 찾고 있다면
소스 코드:
/**
* method to find the next lexicographical greater string
*
* @param w
* @return a new string
*/
static String biggerIsGreater(String w) {
char charArray[] = w.toCharArray();
int n = charArray.length;
int endIndex = 0;
// step-1) Start from the right most character and find the first character
// that is smaller than previous character.
for (endIndex = n - 1; endIndex > 0; endIndex--) {
if (charArray[endIndex] > charArray[endIndex - 1]) {
break;
}
}
// If no such char found, then all characters are in descending order
// means there cannot be a greater string with same set of characters
if (endIndex == 0) {
return "no answer";
} else {
int firstSmallChar = charArray[endIndex - 1], nextSmallChar = endIndex;
// step-2) Find the smallest character on right side of (endIndex - 1)'th
// character that is greater than charArray[endIndex - 1]
for (int startIndex = endIndex + 1; startIndex < n; startIndex++) {
if (charArray[startIndex] > firstSmallChar && charArray[startIndex] < charArray[nextSmallChar]) {
nextSmallChar = startIndex;
}
}
// step-3) Swap the above found next smallest character with charArray[endIndex - 1]
swap(charArray, endIndex - 1, nextSmallChar);
// step-4) Sort the charArray after (endIndex - 1)in ascending order
Arrays.sort(charArray, endIndex , n);
}
return new String(charArray);
}
/**
* method to swap ith character with jth character inside charArray
*
* @param charArray
* @param i
* @param j
*/
static void swap(char charArray[], int i, int j) {
char temp = charArray[i];
charArray[i] = charArray[j];
charArray[j] = temp;
}
동일한 비디오 설명을 찾고 있다면 여기 를 방문 하십시오 .
나는 훌륭한 튜토리얼을 보았습니다. 링크 : https://www.youtube.com/watch?v=quAS1iydq7U
void Solution::nextPermutation(vector<int> &a) {
int k=0;
int n=a.size();
for(int i=0;i<n-1;i++)
{
if(a[i]<a[i+1])
{
k=i;
}
}
int ele=INT_MAX;
int pos=0;
for(int i=k+1;i<n;i++)
{
if(a[i]>a[k] && a[i]<ele)
{
ele=a[i];pos=i;
}
}
if(pos!=0)
{
swap(a[k],a[pos]);
reverse(a.begin()+k+1,a.end());
}
}
- 목록 끝에서 순회를 시작합니다. 각각을 이전 인덱스 값과 비교하십시오.
- 이전 인덱스 (예 : index
i-1
) 값x
이 현재 인덱스 (indexi
) 값 보다 낮다면 현재 위치에서 시작하여 오른쪽에 하위 목록을 정렬합니다i
. 현재 위치에서 끝까지 더 높은 값을 하나 선택
x
하고 인덱스에 넣습니다i-1
. 인덱스에서 값이 선택되었습니다x
. 그건:swap(list[i-1], list[j]) where j >= i, and the list is sorted from index "i" onwards
암호:
public void nextPermutation(ArrayList<Integer> a) {
for (int i = a.size()-1; i > 0; i--){
if (a.get(i) > a.get(i-1)){
Collections.sort(a.subList(i, a.size()));
for (int j = i; j < a.size(); j++){
if (a.get(j) > a.get(i-1)) {
int replaceWith = a.get(j); // Just higher than ith element at right side.
a.set(j, a.get(i-1));
a.set(i-1, replaceWith);
return;
}
}
}
}
// It means the values are already in non-increasing order. i.e. Lexicographical highest
// So reset it back to lowest possible order by making it non-decreasing order.
for (int i = 0, j = a.size()-1; i < j; i++, j--){
int tmp = a.get(i);
a.set(i, a.get(j));
a.set(j, tmp);
}
}
예 :
10 40 30 20 => 20 10 30 40 // 20 is just bigger than 10
10 40 30 20 5 => 20 5 10 30 40 // 20 is just bigger than 10. Numbers on right side are just sorted form of this set {numberOnRightSide - justBigger + numberToBeReplaced}.
이것은 11 개의 문자로 된 문자열까지 충분히 효율적입니다.
// next_permutation example
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
void nextPerm(string word) {
vector<char> v(word.begin(), word.end());
vector<string> permvec; // permutation vector
string perm;
int counter = 0; //
int position = 0; // to find the position of keyword in the permutation vector
sort (v.begin(),v.end());
do {
perm = "";
for (vector<char>::const_iterator i = v.begin(); i != v.end(); ++i) {
perm += *i;
}
permvec.push_back(perm); // add permutation to vector
if (perm == word) {
position = counter +1;
}
counter++;
} while (next_permutation(v.begin(),v.end() ));
if (permvec.size() < 2 || word.length() < 2) {
cout << "No answer" << endl;
}
else if (position !=0) {
cout << "Answer: " << permvec.at(position) << endl;
}
}
int main () {
string word = "nextperm";
string key = "mreptxen";
nextPerm(word,key); // will check if the key is a permutation of the given word and return the next permutation after the key.
return 0;
}
이 코드가 도움이 되길 바랍니다.
int main() {
char str[100];
cin>>str;
int len=strlen(len);
int f=next_permutation(str,str+len);
if(f>0) {
print the string
} else {
cout<<"no answer";
}
}
'development' 카테고리의 다른 글
Chrome 확장 프로그램 ID-찾는 방법 (0) | 2021.01.09 |
---|---|
jQuery는 문자열 등에서 특수 문자를 제거합니다. (0) | 2021.01.09 |
비활성으로 인한 Amazon EC2 SSH 시간 초과 (0) | 2021.01.09 |
NOT DUPLICATED 값만있는 PHP 병합 배열 (0) | 2021.01.09 |
How to get rid of the underline in a Spannable String with a Clickable Object? (0) | 2021.01.09 |