3.Cheerleaders(SotongPractice)↵
Môtả↵
ChomộtxâugồmNkítự(N≤10),yêucầuinratấtcảcáchoánvịphânbiệtcủaxâuđótheothứtựtừđiển.↵
Vídụ↵
Vớixâu“aba”,sẽcótấtcả3hoánvịkhácnhautheothứtựtừđiểnlà“aab”,“aba”,“baa”.↵
Phântích↵
MộtxâucóđộdàiNsẽcótốiđaN!hoánvịphânbiệtkhitấtcảcáckítựcủaxâuđóđềukhácnhau.↵
Hướnggiải↵
Vétcạn↵
Dựavàotầnsốcủacáckítựtrongxâu,dùngkĩthuậtđệquyđểsinhratấtcảhoánvịkhácnhautheothứtựtừđiển.↵
ĐộphứctạptínhtoánO(N!).↵
24↵
2. Exhaustive Search -Problem↵
voidper(inti){↵
//basic condition//↵
if(i == N){↵
cout << S << endl;↵
return;↵
}↵
//Recursion//↵
for (intj = 0; j < 26; j++){↵
if(cnt[j]){↵
S[i] = 'a'+j;↵
cnt[j]--;↵
per(i+1);//đệ quy↵
cnt[j]++;↵
}↵
}↵
}↵
↵
package sinhhv;↵
↵
import java.util.Scanner;↵
↵
public class Solution {↵
static int n;↵
static char[] s = new char[20];↵
static char[] ans = new char[20];↵
static boolean[] vs = new boolean[20];↵
↵
static void solve(int pos){↵
if(pos==n){↵
for(int i=0; i<n; i++){↵
System.out.print(ans[i]);↵
}↵
System.out.println();↵
return;↵
}↵
for(int i=0; i<n; i++){↵
if(vs[i]==true){↵
ans[pos] = s[i];↵
vs[i] = false;↵
solve(pos+1);↵
vs[i] = true;↵
}↵
}↵
}↵
public static void main(String[] args) {↵
Scanner sc = new Scanner(System.in);↵
int T;↵
T = sc.nextInt();↵
for (int test_case = 1; test_case <= T; test_case++) {↵
n = sc.nextInt();↵
String string = sc.next();↵
for(int i=0; i<string.length(); i++){↵
s[i] = string.charAt(i);↵
vs[i] = true;↵
}↵
for(int i=0; i<n; i++){↵
for(int j=i; j<n; j++){↵
if(s[j]<s[i]){↵
char t = s[j];↵
s[j] = s[i];↵
s[i] = t;↵
}↵
}↵
}↵
// for(int i=0; i<n; i++){↵
// System.out.print(s[i]);↵
// }↵
solve(0);↵
}↵
}↵
}↵
Môtả↵
ChomộtxâugồmNkítự(N≤10),yêucầuinratấtcảcáchoánvịphânbiệtcủaxâuđótheothứtựtừđiển.↵
Vídụ↵
Vớixâu“aba”,sẽcótấtcả3hoánvịkhácnhautheothứtựtừđiểnlà“aab”,“aba”,“baa”.↵
Phântích↵
MộtxâucóđộdàiNsẽcótốiđaN!hoánvịphânbiệtkhitấtcảcáckítựcủaxâuđóđềukhácnhau.↵
Hướnggiải↵
Vétcạn↵
Dựavàotầnsốcủacáckítựtrongxâu,dùngkĩthuậtđệquyđểsinhratấtcảhoánvịkhácnhautheothứtựtừđiển.↵
ĐộphứctạptínhtoánO(N!).↵
24↵
2. Exhaustive Search -Problem↵
voidper(inti){↵
//basic condition//↵
if(i == N){↵
cout << S << endl;↵
return;↵
}↵
//Recursion//↵
for (intj = 0; j < 26; j++){↵
if(cnt[j]){↵
S[i] = 'a'+j;↵
cnt[j]--;↵
per(i+1);//đệ quy↵
cnt[j]++;↵
}↵
}↵
}
↵
package sinhhv;↵
↵
import java.util.Scanner;↵
↵
public class Solution {↵
static int n;↵
static char[] s = new char[20];↵
static char[] ans = new char[20];↵
static boolean[] vs = new boolean[20];↵
↵
static void solve(int pos){↵
if(pos==n){↵
for(int i=0; i<n; i++){↵
System.out.print(ans[i]);↵
}↵
System.out.println();↵
return;↵
}↵
for(int i=0; i<n; i++){↵
if(vs[i]==true){↵
ans[pos] = s[i];↵
vs[i] = false;↵
solve(pos+1);↵
vs[i] = true;↵
}↵
}↵
}↵
public static void main(String[] args) {↵
Scanner sc = new Scanner(System.in);↵
int T;↵
T = sc.nextInt();↵
for (int test_case = 1; test_case <= T; test_case++) {↵
n = sc.nextInt();↵
String string = sc.next();↵
for(int i=0; i<string.length(); i++){↵
s[i] = string.charAt(i);↵
vs[i] = true;↵
}↵
for(int i=0; i<n; i++){↵
for(int j=i; j<n; j++){↵
if(s[j]<s[i]){↵
char t = s[j];↵
s[j] = s[i];↵
s[i] = t;↵
}↵
}↵
}↵
// for(int i=0; i<n; i++){↵
// System.out.print(s[i]);↵
// }↵
solve(0);↵
}↵
}↵
}↵
