[Problem] Permutations with repeated characters

Блог пользователя 1507002

Автор 1507002, история, 6 лет назад, По-английски

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,

#permutation, #combinatorics, #number_theory, #next permutation

1507002
6 лет назад
5

Комментарии (4)

Показать архивные | Написать комментарий?

Halit

6 лет назад, скрыть # |

So, you can use std::next_permutation()

→ Ответить

SecondThread

6 лет назад, скрыть # |

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.

→ Ответить

SecondThread

6 лет назад, скрыть # ^ |

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.

→ Ответить

1507002

6 лет назад, скрыть # |

← Rev. 2 →

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;
}

→ Ответить