Given a string, find all of its permutations

View previous topic View next topic Go down

Given a string, find all of its permutations

Post  viterbi on Tue Sep 13, 2011 10:15 am

1____void find_permutations(string s, int i, int n, bool check_duplicate) {
2__________if (i >= n) {
3________________cout << s << " ";
4__________} else {
5________________bool ch[256];
6________________for (int j=0; j<256; j++) ch[j] = false;
7________________for (int j=i; j<n; j++) {
8______________________if (!ch[s[j]] || !check_duplicate) {
9____________________________ch[s[j]] = true;
10___________________________swap(s[i], s[j]);
11___________________________find_permutations(s, i+1, n, check_duplicate);
12___________________________swap(s[i], s[j]);
13_____________________}____________
14_______________}
15_________}
16___}

viterbi

Posts : 32
Join date : 2011-09-03

View user profile

Back to top Go down

Re: Given a string, find all of its permutations

Post  skyboard on Tue Sep 13, 2011 4:53 pm

Hi I'm not sure about the arguments in the method

does i begin from 0 and n is the length of the string s?
Also what is the boolean check_duplicate?


viterbi wrote:1____void find_permutations(string s, int i, int n, bool check_duplicate) {
2__________if (i >= n) {
3________________cout << s << " ";
4__________} else {
5________________bool ch[256];
6________________for (int j=0; j<256; j++) ch[j] = false;
7________________for (int j=i; j<n; j++) {
8______________________if (!ch[s[j]] || !check_duplicate) {
9____________________________ch[s[j]] = true;
10___________________________swap(s[i], s[j]);
11___________________________find_permutations(s, i+1, n, check_duplicate);
12___________________________swap(s[i], s[j]);
13_____________________}____________
14_______________}
15_________}
16___}

skyboard

Posts : 31
Join date : 2011-09-03

View user profile

Back to top Go down

Re: Given a string, find all of its permutations

Post  viterbi on Thu Sep 15, 2011 11:39 pm

Sorry, I should write some explanation. Yes, you call it with i=0 and n is the length of the string. check_duplicate means to out put the same string twice if there is duplicate characters.

For example, "aab", if check duplicate, all permutations are aab, aba, baa,
if not, then aab, aab, aba, aba, baa, baa.

skyboard wrote:Hi I'm not sure about the arguments in the method

does i begin from 0 and n is the length of the string s?
Also what is the boolean check_duplicate?


viterbi wrote:1____void find_permutations(string s, int i, int n, bool check_duplicate) {
2__________if (i >= n) {
3________________cout << s << " ";
4__________} else {
5________________bool ch[256];
6________________for (int j=0; j<256; j++) ch[j] = false;
7________________for (int j=i; j<n; j++) {
8______________________if (!ch[s[j]] || !check_duplicate) {
9____________________________ch[s[j]] = true;
10___________________________swap(s[i], s[j]);
11___________________________find_permutations(s, i+1, n, check_duplicate);
12___________________________swap(s[i], s[j]);
13_____________________}____________
14_______________}
15_________}
16___}

viterbi

Posts : 32
Join date : 2011-09-03

View user profile

Back to top Go down

Re: Given a string, find all of its permutations

Post  Sponsored content


Sponsored content


Back to top Go down

View previous topic View next topic Back to top

- Similar topics

 
Permissions in this forum:
You cannot reply to topics in this forum