전체 배열 알고리즘 분석 (오리지널 방법 / 일반 방법 / 사전 순서 법)
8556 단어 전체 배열
주어진 시퀀스 {1, 2, 3} 에는 {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1} 등 6 가지 배열 이 있 습 니 다.
쉽게 쓸 수 있 을 것 같 고, 더 긴 서열 에 대해 서도 시간 문제 일 뿐, 결국 펜 으로 일일이 열거 할 수 있 을 것 이다.
하지만 프로그램 으로 이 루어 지 려 면 손 쓸 길이 없 을 수도 있 습 니 다.
오리지널 방법
오리지널 방법 이란 알고리즘 의 효율 과 다른 요 소 를 고려 하지 않 고 문 제 를 해결 하기 위해 스스로 실행 가능 한 방법 을 만 드 는 것 이다 (반드시 좋 은 것 은 아니 지만 문 제 를 해결 할 수 있다).
우선 위 에 있 는 6 개의 서열 을 어떻게 썼 는 지 생각해 보 자.
1. 첫 번 째 원 소 를 확인 하려 면 세 가지 가능성 이 있다. 1, 2, 3.
2. 두 번 째 요소 (1 을 예 로 들 면) 를 확정 하면 두 가지 가능성 이 있다. 2, 3.
3. 세 번 째 요소 (2 를 예 로 들 면) 를 확정 하면 한 가지 가능성 만 있다. 3.이때 우 리 는 하나의 서열 을 얻 었 다. 1, 2, 3.
다음은 우리 가 생각 을 정리 하고 프로그램 으로 어떻게 실현 할 것 인 가 를 생각해 보 자.
길이 가 n 인 서열 에 있어 컴퓨터 가 해 야 할 일 은
1. 제 (i) 위의 요 소 를 확인 하고 (n + 1 - i) 가지 가능성 이 있 습 니 다. 순서대로 i 위 가 될 수 있 는 요 소 를 선택 하여 현재 확 정 된 서열 (길 이 는 i) 을 저장 합 니 다.
2. 제 (i + 1) 위의 요 소 를 확인 하고 (n + 1 - i - i) 가지 가능성 이 있 습 니 다. i + 1 위 가 될 수 있 는 요 소 를 순서대로 선택 하여 현재 확 정 된 서열 (길 이 는 i + 1) 을 저장 합 니 다.
……
n. 제 (n) 위의 요 소 를 확정 하 는 것 은 한 가지 가능 합 니 다. 유일한 가능 한 요 소 를 n 위의 요소 로 하고 출력 이 확 정 된 시퀀스 입 니 다.
분명히 이것 은 일종 의 귀속 방법 이다
자바 코드 는 다음 과 같 습 니 다:
public class FullPermutation {
static int count = 0;
/**
*
* <br /> ： ，
*/
public static void main(String[] args) {
String str = "13234";
str = check(str);//
fullPermutate(0, "", str);
System.out.print(count);
}
/**
* @param index index
* @param path
* @param string
*/
static void fullPermutate(int index, String path, String string)
{
String restStr = strSub(string, path);
if(index == string.length())
{
System.out.println(path + restStr);
count++;//
return;
}
else
{
for(int i = 0;i < string.length() - index;i++)
fullPermutate(index + 1, path + restStr.charAt(i), string);
}
}
/**
* @param full
* @param part
* @return rest full part
*/
static String strSub(String full, String part)
{
String rest = "";
for(int i = 0;i < full.length();i++)
{
String c = full.charAt(i) + "";
if(!part.contains(c))
rest += c;
}
return rest;
}
/**
* @param str
* @return
*/
static String check(String str)
{
for(int i = 0;i < str.length() - 1;i++)
{
String firstPart = str.substring(0, i + 1);
String restPart = str.substring(i + 1);
str = firstPart + restPart.replace(str.charAt(i) + "", "");
}
return str;
}
}
P. S. 위의 코드 에서 왜 매개 변수 중의 중복 요 소 를 제거 해 야 하 는 지 에 대해 프로그램의 노 스틱 성 을 강화 하기 위해 서 입 니 다. 전형 적 인 배열 문 제 는 중복 요 소 를 포함 하지 않 은 서열 에 대해 중복 요 소 를 포함 한 서열 에 대해 우 리 는 뒤에서 토론 할 것 입 니 다.
2. 일반 알고리즘 (가장 흔히 볼 수 있 는 것 이자 가장 전형 적 인 전체 배열 알고리즘)
핵심 사상 은 교환 이다. 구체 적 으로 말 하면 길이 가 n 인 꼬치 에 대해 모든 배열 을 얻 으 려 면 우 리 는 이렇게 할 수 있다.
1. 현재 위치 에 있 는 요 소 를 그 후의 모든 요소 와 순서대로 교환 합 니 다.
2. 다음 에 똑 같이 처리 하고 현재 가 마지막 일 때 까지 출력 시퀀스
[주의해 야 할 점: 우리 의 사상 은 '교환' 이다. 즉, 원 데 이 터 를 직접 수정 하 는 것 이다. 그러면 교환 한 후에 반드시 다시 바 꿔 야 한다. 그렇지 않 으 면 우리 의 원 데이터 가 변화 하고 반드시 오류 가 발생 할 것 이다.]
위의 해석 이 여전히 어렵다 고 생각한다 면 이 말 을 기억 하 세 요. 핵심 사상 은 뒤의 모든 사람 이 당신 과 한 번 교환 하 는 것 입 니 다. (당신 은 지침 입 니 다. 예전 에 뒤로 이동 하 는 것 입 니 다.)
C 코드 는 다음 과 같 습 니 다. http://www.cnblogs.com/nokiaguy/archive/2008/05/11/1191914.html
#include <stdio.h>
int n = 0;
void swap(int *a, int *b)
{
int m;
m = *a;
*a = *b;
*b = m;
}
void perm(int list[], int k, int m)
{
int i;
if(k > m)
{
for(i = 0; i <= m; i++)
printf("%d ", list[i]);
printf("
");
n++;
}
else
{
for(i = k; i <= m; i++)
{
swap(&list[k], &list[i]);
perm(list, k + 1, m);
swap(&list[k], &list[i]);
}
}
}
int main()
{
int list[] = {1, 2, 3, 4, 5};
perm(list, 0, 4);
printf("total:%d
", n);
return 0;
}
원문 도 약간의 해석 을 내 놓 았 지만 이해 가 되 지 않 는 다 면 운행 궤적 을 출력 해 이해 에 도움 이 되 거나 필획 으로 그림 을 그 려 몇 번 더 보면 알 수 있다. 코드 를 직접 보면 확실히 이해 하기 어렵다.
사전 서식
사실은 본 고 에서 처음에 제시 한 예 에서 사전 순 서 를 사 용 했 고 사람 이 전체 배열 이나 다른 유사 한 것 을 쓸 때 자신 도 모 르 게 사전 순 서 를 사용 했다. 이렇게 하 는 것 은 서열 이 빠 지 는 것 을 방지 하기 위해 서 이다.
그렇다면 사전 순서 로 도 당연히 전체 배열 을 실현 할 수 있 습 니 다. 주어진 서열 {3, 1, 2} 에 대해 우 리 는 생각 을 정리 하고 구체 적 인 절 차 를 생각해 보 겠 습 니 다.
1. 주어진 시퀀스 에 대해 오름차 순 으로 정렬 하여 최소 사전 순서 {1, 2, 3} 를 얻 습 니 다.
2. 질서 있 는 서열 에 대해 다음 사전 순 서 를 구하 고 {1, 3, 2} 을 얻 습 니 다.
3. 현재 시퀀스 에 다음 사전 순서 가 없다 면 (또는 현재 시퀀스 가 최대 사전 순서, 예 를 들 어 {3, 2, 1}) 종료 합 니 다.
분명 한 것 은 사전 순서 법의 핵심 은 다음 사전 순 서 를 구 하 는 것 이다. 이곳 의 '다음' 을 충분히 이해 하려 면 두 가지 의미 가 있다.
1. 이 시퀀스 는 사전 에서 현재 시퀀스 뒤에 있 습 니 다.
2. 이 서열 은 사전 에서 현재 서열 에 가장 가 까 운 것 이다.
사전 순 서 는 엄격 한 수학 적 정의 가 있 고 정의 에 따라 한 서열 의 다음 사전 순 서 를 구 할 수 있 으 며 구체 적 인 방법 은 여기 서 서술 하지 않 습 니 다 (아래 코드 에 상세 한 해석 이 있 습 니 다).
자바 코드 는 다음 과 같 습 니 다:
public class DictionaryOrder {
/**
*
* <br /> ， （ ）
*/
public static void main(String[] args) {
int arr[] = new int[]{4, 3, 1, 2};
/*
boolean exist = nextPermutation(arr);
if(exist)
{
for(int value : arr)
System.out.print(value);
System.out.println();
}
else
System.out.println(" ");
*/
///*
// （ ）
sort(arr);
for(int value : arr)
System.out.print(value);
System.out.println();
//
int count = 1;//
while(nextPermutation(arr))
{
for(int value : arr)
System.out.print(value);
System.out.println();
count++;
}
System.out.println(" " + count + " ");
//*/
}
/**
* @param arr
* @return ， false
*/
public static boolean nextPermutation(int[] arr)
{
int pos1 = 0, pos2 = 0;
//1. arr[i] < arr[i + 1] i
//（ ）
boolean find = false;
for(int i = arr.length - 2;i >= 0;i--)
if(arr[i] < arr[i + 1])
{
pos1 = i;
find = true;
break;
}
if(!find)// ，
return false;
//2. pos1 arr[i] >= arr[pos1] i
//（ pos1 arr[pos1] ）
int min = arr[pos1];
for(int i = pos1 + 1;i < arr.length;i++)
{
if(arr[i] >= arr[pos1])
{
min = arr[i];
pos2 = i;
}
}
//3. pos1 pos2
int temp = arr[pos1];
arr[pos1] = arr[pos2];
arr[pos2] = temp;
//4. pos1 （ ）
int i = pos1 + 1;
int j = arr.length - 1;
for(;i < j;i++, j--)
{
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
return true;
}
/**
* （ ）
* @param arr
*/
public static void sort(int[] arr)
{
for(int i = 0;i < arr.length - 2;i++)
for(int j = 0;j < arr.length - i - 1;j++)
if(arr[j] > arr[j + 1])
{
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
-------
알고리즘 의 세부 사항 은 여기까지 입 니 다. 다음은 몇 가지 중요 하지 않 은 문 제 를 토론 하 겠 습 니 다.
1. 주어진 시퀀스 에 중복 요소 가 존재 합 니 다.
전형 적 인 전체 배열 문 제 는 이 문 제 를 토론 하지 않 지만 실제 응용 에서 만 날 수 있 습 니 다. 우 리 는 두 가지 선택 이 있 습 니 다.
i. 원 데이터 (주어진 시퀀스) 를 처리 하고 중복 요소 에 대해 하나만 보류 하거나 중복 요 소 를 교체 합 니 다. 예 를 들 어 {1, 1, 2, 3, 2}, 우 리 는 교체 표를 만 듭 니 다. a = 1, b = 2, 원 데이터 처리 결 과 는 {1, a, 2, 3, b} 입 니 다. 이로써 우 리 는 중복 요 소 를 제거 합 니 다.
ii. 알고리즘 을 수정 하고 중복 요 소 를 검 측 하 며 해당 하 는 처 리 를 하려 면 구체 적 인 데이터 특징 과 결합 하여 처리 해 야 합 니 다.
2. 알고리즘 효율 문제
만약 에 복잡 한 문제 에서 전체 배열 을 사용 해 야 한다 면 알고리즘 효율 문 제 를 고려 해 야 한다. 위 에서 제시 한 알고리즘 에서 앞의 두 가지 시간 복잡 도 는 똑 같 고 모두 n 층 재 귀 이 며 각 층 n - i + 1 순환 이다.
세 번 째 알고리즘 의 시간 복잡 도 는 주로 정렬 에 집중 되 어 있다. 만약 에 주어진 서열 이 질서 가 있다 면 이때 세 번 째 알고리즘 이 가장 좋 은 것 이다.
또한 새로운 전체 배열 알고리즘 도 있 습 니 다. 관심 이 있 으 면 시도 해 보 세 요. 원문 링크:
http://supershll.blog.163.com/blog/static/37070436201171005758332/
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Q7.1.1 한 그룹의 수의 조합을 모두 열거하다제목: 하나의 수조 안의 수의 조합을 모두 열거합니다. 예를 들어 1과 2열은 1,2,12,21입니다. 분석: 이 문제는 여러 가지 확장이 있는데, 1, 중복된 원소의 수의 조합이 없다(자집의 전체 배열 포함). 2...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
