1507002's blog

[Problem] Permutations with repeated characters
By 1507002, history, 6 years ago, In English

The output for "AABC" should be like this: AABC, AACB, ABAC, ABCA, ACAB, ACBA, BAAC, BACA, BCAA, CAAB, CABA, CBAA.

But the output of my code doesn't match with above. Can anyone find my where is the problem?

My Code

#include <bits/stdc++.h>
using namespace std;

void permute(char str[], int count[], char result[], int level){
	if(level == strlen(result)){
		cout << result << "\n";
		return;
	}
	for(int i=0; i<strlen(str); i++){
		if(count[i] == 0) continue;
		result[level] = str[i];
		count[i]--;
		permute(str, count, result, level+1);
		count[i]++;
	}
}
int main(){
	char str[] = "AABC";
	int n = strlen(str);

	int cnt[n] = {0};

	for(int i=0; i<n; i++){
		int index = (str[i] - 'A');
		cnt[index]++;
	}

	char result[n];
	permute(str, cnt, result, 0);

	return 0;
}

The output of my code: AAA, AAB, AAA, AAB, ABA, ABA, AAA, AAB, ABA, BAA, BAA, BAA,

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
6 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

So, you can use std::next_permutation()

→ Reply
»
6 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Use strings instead of char arrays and the problem will solve itself. strlen of result (first line of permute method) only works correctly if the position after the end of the array is the first 0 in memory, which is unlikely to be the case.

→ Reply
  • »
    »
    6 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    In particular, you should be looking at the length of the string str, not of the length of result. Either way if you just use vectors and strings instead it will all work better.

    → Reply
»
6 years ago, hide # |
← Rev. 2  
Vote: I like it +8 Vote: I do not like it

solved

#include <bits/stdc++.h>
using namespace std;

void permute(set<char> &str, int *count, string result, int level){
	if(level == result.length()){
        cout << result << endl;
		return;
	}
	else{
        for(int i=0; i<str.size(); i++){
            if(count[i] == 0) continue;
            else{
                auto it = str.begin(); advance(it, i); // i th value of set will be store in *it;
                result[level] = *it;
                count[i]--;
                permute(str, count, result, level+1);
                count[i]++;
            }
        }
    }
}

int main(){
	string str = "AABC";
	string result = str;

	int n = str.length();
        int cnt[26] = {0};

        set<char> s;

	for(int i=0; i<n; i++){
		int index = (str[i] - 'A');
		cnt[index]++;
		s.insert(str[i]);
	}

	permute(s, cnt, result, 0);

	return 0;
}
→ Reply