순열을 생성하는 재귀

나는 계승과 같은 매우 직설적 인 것들을 제외하고 재귀를 이해하기가 매우 어렵습니다. 내가 문자열의 모든 순열을 인쇄하려면, 잘은 문자열 길이 내가 계승의 모든 순열을 계산하는 재귀를 원하는 경우 "abcde"처럼, 길이 7의 순열은순열을 생성하는 재귀

abced 
abdce 
abdec 
abecd 
abedc 
acbde 
acbed 
acdbe 
acdeb 
acebd 
acedb 
adbce 
adbec 
adcbe 
adceb 
adebc 
adecb 
aebcd 
aebdc 
aecbd 
aecdb 
aedbc 
aedcb 
bacde 
baced 
badce 
badec 
baecd 
baedc 
bcade 
bcaed 
...

을해야, 5라고 할 수 있습니다 예를 들어, 4, 3, 2 또는 1과 같은 5 일 수있다. 어떤 알고리즘을 사용해야합니까? 이것에 대한 C++ 라이브러리에 어떤 함수가 있습니까?

이 출력은 다음과 같아야합니다 가정 :

acbd 
bcad 
abc 
bac 
ab 
ba

출처

2016-06-11 JX2612

원래 길이는 물론 xD – JX2612

아직 시도한 것이 있습니까? 아마 일부 코드? 체크 아웃 [이 인터뷰 케이크에 대한 질문] (https://www.interviewcake.com/question/python/recursive-string-permutations) 역학에 대한 설명은 – adamb

5의 Factorial은 120 ... 나는 당신이 순열을 의미한다고 생각합니다. 길이가 5 이하 –

재귀 알고리즘을 사용하여, 거의 mathematical induction 같다. 먼저 기본 케이스를 처리하고 하위 문제 패턴을 찾아야합니다.

팩토리얼의 경우 F(n) 팩토리얼을 n으로 정의하십시오. F(n)=n!=n*(n-1)!=n*F(n-1)

그리고 순열

베이스 케이스 F(0)=1
서브 문제 패턴, E 세트의 모든 순열로서 P(E)를 정의한다.
1. 베이스 케이스 P({}) = {{}}
2. 서브 문제 패턴. 순열의 과정을 생각해 봅시다. 첫 번째 요소 인 x을 선택한 다음 하위 문제 P(E-x)을 선택한 다음 각각의 p in P(E-x) 및 x을 앞에두고 요소 x으로 시작하는 모든 순열을 얻었습니다. x 모든 순열, 일명 P(E).
next_permutation을 사용할 수 있습니다.

그리고 위의 생각에서 예제 코드 같은 것입니다 :
```
// generate permutation of {a[st], a[st+1], ..., a[ed]} 
void P(char a[], int st, int ed) { 
    if (st > ed) { puts(a); return; } // nothing to generate 
    for (int i=st; i<=ed; ++i) { 
     swap(a[st], a[i]);   // enumerate first element 
     P(a, st+1, ed); 
     swap(a[st], a[i]);   // recover 
    } 
} 
```
이 http://ideone.com/zbawY2에 그것을 확인합니다.

출처

2016-06-11 15:03:57 delta

순열을 생성하는 재귀

답변

관련 문제