
Code: Select all
M['m']=25;
M['m']=26;
Moderator: Board moderators
Code: Select all
M['m']=25;
M['m']=26;
Code: Select all
Removed after AC
Code: Select all
Removed after AC
brianfry713 wrote:Input:AC output:Code: Select all
1 AaBb
Code: Select all
AaBb AabB ABab ABba AbaB AbBa aABb aAbB aBAb aBbA abAB abBA BAab BAba BaAb BabA BbAa BbaA bAaB bABa baAB baBA bBAa bBaA
Code: Select all
1
aAbBcC
Code: Select all
AaBbCc
AaBbcC
AaBCbc
AaBCcb
AaBcbC
AaBcCb
AabBCc
AabBcC
AabCBc
AabCcB
AabcBC
AabcCB
AaCBbc
AaCBcb
AaCbBc
AaCbcB
AaCcBb
AaCcbB
AacBbC
AacBCb
AacbBC
AacbCB
AacCBb
AacCbB
ABabCc
ABabcC
ABaCbc
ABaCcb
ABacbC
ABacCb
ABbaCc
ABbacC
ABbCac
ABbCca
ABbcaC
ABbcCa
ABCabc
ABCacb
ABCbac
ABCbca
ABCcab
ABCcba
ABcabC
ABcaCb
ABcbaC
ABcbCa
ABcCab
ABcCba
AbaBCc
AbaBcC
AbaCBc
AbaCcB
AbacBC
AbacCB
AbBaCc
AbBacC
AbBCac
AbBCca
AbBcaC
AbBcCa
AbCaBc
AbCacB
AbCBac
AbCBca
AbCcaB
AbCcBa
AbcaBC
AbcaCB
AbcBaC
AbcBCa
AbcCaB
AbcCBa
ACaBbc
ACaBcb
ACabBc
ACabcB
ACacBb
ACacbB
ACBabc
ACBacb
ACBbac
ACBbca
ACBcab
ACBcba
ACbaBc
ACbacB
ACbBac
ACbBca
ACbcaB
ACbcBa
ACcaBb
ACcabB
ACcBab
ACcBba
ACcbaB
ACcbBa
AcaBbC
AcaBCb
AcabBC
AcabCB
AcaCBb
AcaCbB
AcBabC
AcBaCb
AcBbaC
AcBbCa
AcBCab
AcBCba
AcbaBC
AcbaCB
AcbBaC
AcbBCa
AcbCaB
AcbCBa
AcCaBb
AcCabB
AcCBab
AcCBba
AcCbaB
AcCbBa
aABbCc
aABbcC
aABCbc
aABCcb
aABcbC
aABcCb
aAbBCc
aAbBcC
aAbCBc
aAbCcB
aAbcBC
aAbcCB
aACBbc
aACBcb
aACbBc
aACbcB
aACcBb
aACcbB
aAcBbC
aAcBCb
aAcbBC
aAcbCB
aAcCBb
aAcCbB
aBAbCc
aBAbcC
aBACbc
aBACcb
aBAcbC
aBAcCb
aBbACc
aBbAcC
aBbCAc
aBbCcA
aBbcAC
aBbcCA
aBCAbc
aBCAcb
aBCbAc
aBCbcA
aBCcAb
aBCcbA
aBcAbC
aBcACb
aBcbAC
aBcbCA
aBcCAb
aBcCbA
abABCc
abABcC
abACBc
abACcB
abAcBC
abAcCB
abBACc
abBAcC
abBCAc
abBCcA
abBcAC
abBcCA
abCABc
abCAcB
abCBAc
abCBcA
abCcAB
abCcBA
abcABC
abcACB
abcBAC
abcBCA
abcCAB
abcCBA
aCABbc
aCABcb
aCAbBc
aCAbcB
aCAcBb
aCAcbB
aCBAbc
aCBAcb
aCBbAc
aCBbcA
aCBcAb
aCBcbA
aCbABc
aCbAcB
aCbBAc
aCbBcA
aCbcAB
aCbcBA
aCcABb
aCcAbB
aCcBAb
aCcBbA
aCcbAB
aCcbBA
acABbC
acABCb
acAbBC
acAbCB
acACBb
acACbB
acBAbC
acBACb
acBbAC
acBbCA
acBCAb
acBCbA
acbABC
acbACB
acbBAC
acbBCA
acbCAB
acbCBA
acCABb
acCAbB
acCBAb
acCBbA
acCbAB
acCbBA
BAabCc
BAabcC
BAaCbc
BAaCcb
BAacbC
BAacCb
BAbaCc
BAbacC
BAbCac
BAbCca
BAbcaC
BAbcCa
BACabc
BACacb
BACbac
BACbca
BACcab
BACcba
BAcabC
BAcaCb
BAcbaC
BAcbCa
BAcCab
BAcCba
BaAbCc
BaAbcC
BaACbc
BaACcb
BaAcbC
BaAcCb
BabACc
BabAcC
BabCAc
BabCcA
BabcAC
BabcCA
BaCAbc
BaCAcb
BaCbAc
BaCbcA
BaCcAb
BaCcbA
BacAbC
BacACb
BacbAC
BacbCA
BacCAb
BacCbA
BbAaCc
BbAacC
BbACac
BbACca
BbAcaC
BbAcCa
BbaACc
BbaAcC
BbaCAc
BbaCcA
BbacAC
BbacCA
BbCAac
BbCAca
BbCaAc
BbCacA
BbCcAa
BbCcaA
BbcAaC
BbcACa
BbcaAC
BbcaCA
BbcCAa
BbcCaA
BCAabc
BCAacb
BCAbac
BCAbca
BCAcab
BCAcba
BCaAbc
BCaAcb
BCabAc
BCabcA
BCacAb
BCacbA
BCbAac
BCbAca
BCbaAc
BCbacA
BCbcAa
BCbcaA
BCcAab
BCcAba
BCcaAb
BCcabA
BCcbAa
BCcbaA
BcAabC
BcAaCb
BcAbaC
BcAbCa
BcACab
BcACba
BcaAbC
BcaACb
BcabAC
BcabCA
BcaCAb
BcaCbA
BcbAaC
BcbACa
BcbaAC
BcbaCA
BcbCAa
BcbCaA
BcCAab
BcCAba
BcCaAb
BcCabA
BcCbAa
BcCbaA
bAaBCc
bAaBcC
bAaCBc
bAaCcB
bAacBC
bAacCB
bABaCc
bABacC
bABCac
bABCca
bABcaC
bABcCa
bACaBc
bACacB
bACBac
bACBca
bACcaB
bACcBa
bAcaBC
bAcaCB
bAcBaC
bAcBCa
bAcCaB
bAcCBa
baABCc
baABcC
baACBc
baACcB
baAcBC
baAcCB
baBACc
baBAcC
baBCAc
baBCcA
baBcAC
baBcCA
baCABc
baCAcB
baCBAc
baCBcA
baCcAB
baCcBA
bacABC
bacACB
bacBAC
bacBCA
bacCAB
bacCBA
bBAaCc
bBAacC
bBACac
bBACca
bBAcaC
bBAcCa
bBaACc
bBaAcC
bBaCAc
bBaCcA
bBacAC
bBacCA
bBCAac
bBCAca
bBCaAc
bBCacA
bBCcAa
bBCcaA
bBcAaC
bBcACa
bBcaAC
bBcaCA
bBcCAa
bBcCaA
bCAaBc
bCAacB
bCABac
bCABca
bCAcaB
bCAcBa
bCaABc
bCaAcB
bCaBAc
bCaBcA
bCacAB
bCacBA
bCBAac
bCBAca
bCBaAc
bCBacA
bCBcAa
bCBcaA
bCcAaB
bCcABa
bCcaAB
bCcaBA
bCcBAa
bCcBaA
bcAaBC
bcAaCB
bcABaC
bcABCa
bcACaB
bcACBa
bcaABC
bcaACB
bcaBAC
bcaBCA
bcaCAB
bcaCBA
bcBAaC
bcBACa
bcBaAC
bcBaCA
bcBCAa
bcBCaA
bcCAaB
bcCABa
bcCaAB
bcCaBA
bcCBAa
bcCBaA
CAaBbc
CAaBcb
CAabBc
CAabcB
CAacBb
CAacbB
CABabc
CABacb
CABbac
CABbca
CABcab
CABcba
CAbaBc
CAbacB
CAbBac
CAbBca
CAbcaB
CAbcBa
CAcaBb
CAcabB
CAcBab
CAcBba
CAcbaB
CAcbBa
CaABbc
CaABcb
CaAbBc
CaAbcB
CaAcBb
CaAcbB
CaBAbc
CaBAcb
CaBbAc
CaBbcA
CaBcAb
CaBcbA
CabABc
CabAcB
CabBAc
CabBcA
CabcAB
CabcBA
CacABb
CacAbB
CacBAb
CacBbA
CacbAB
CacbBA
CBAabc
CBAacb
CBAbac
CBAbca
CBAcab
CBAcba
CBaAbc
CBaAcb
CBabAc
CBabcA
CBacAb
CBacbA
CBbAac
CBbAca
CBbaAc
CBbacA
CBbcAa
CBbcaA
CBcAab
CBcAba
CBcaAb
CBcabA
CBcbAa
CBcbaA
CbAaBc
CbAacB
CbABac
CbABca
CbAcaB
CbAcBa
CbaABc
CbaAcB
CbaBAc
CbaBcA
CbacAB
CbacBA
CbBAac
CbBAca
CbBaAc
CbBacA
CbBcAa
CbBcaA
CbcAaB
CbcABa
CbcaAB
CbcaBA
CbcBAa
CbcBaA
CcAaBb
CcAabB
CcABab
CcABba
CcAbaB
CcAbBa
CcaABb
CcaAbB
CcaBAb
CcaBbA
CcabAB
CcabBA
CcBAab
CcBAba
CcBaAb
CcBabA
CcBbAa
CcBbaA
CcbAaB
CcbABa
CcbaAB
CcbaBA
CcbBAa
CcbBaA
cAaBbC
cAaBCb
cAabBC
cAabCB
cAaCBb
cAaCbB
cABabC
cABaCb
cABbaC
cABbCa
cABCab
cABCba
cAbaBC
cAbaCB
cAbBaC
cAbBCa
cAbCaB
cAbCBa
cACaBb
cACabB
cACBab
cACBba
cACbaB
cACbBa
caABbC
caABCb
caAbBC
caAbCB
caACBb
caACbB
caBAbC
caBACb
caBbAC
caBbCA
caBCAb
caBCbA
cabABC
cabACB
cabBAC
cabBCA
cabCAB
cabCBA
caCABb
caCAbB
caCBAb
caCBbA
caCbAB
caCbBA
cBAabC
cBAaCb
cBAbaC
cBAbCa
cBACab
cBACba
cBaAbC
cBaACb
cBabAC
cBabCA
cBaCAb
cBaCbA
cBbAaC
cBbACa
cBbaAC
cBbaCA
cBbCAa
cBbCaA
cBCAab
cBCAba
cBCaAb
cBCabA
cBCbAa
cBCbaA
cbAaBC
cbAaCB
cbABaC
cbABCa
cbACaB
cbACBa
cbaABC
cbaACB
cbaBAC
cbaBCA
cbaCAB
cbaCBA
cbBAaC
cbBACa
cbBaAC
cbBaCA
cbBCAa
cbBCaA
cbCAaB
cbCABa
cbCaAB
cbCaBA
cbCBAa
cbCBaA
cCAaBb
cCAabB
cCABab
cCABba
cCAbaB
cCAbBa
cCaABb
cCaAbB
cCaBAb
cCaBbA
cCabAB
cCabBA
cCBAab
cCBAba
cCBaAb
cCBabA
cCBbAa
cCBbaA
cCbAaB
cCbABa
cCbaAB
cCbaBA
cCbBAa
cCbBaA
Code: Select all
#include<iostream>
#include<cstdio>
#include<string>
#include<map>
using namespace std;
map<string, int>myMap;
int permutation(string prefix, string ch)
{
int n = ch.length();
for(int i=0;i<n;i++)
{
char tmp = ch[0];
ch[0] = ch[i];
ch[i] = tmp;
if(n==1)
{
if(myMap[prefix+ch]==0)
{
cout<<prefix+ch<<endl;
myMap[prefix+ch]=1;
}
return 0;
}
permutation(prefix+ch.substr(0, 1), ch.substr(1, n-1));
}
}
int main()
{
long T;
string ch, str;
map<int, int>charMap;
scanf("%ld", &T);
for(int i=1;i<=T;i++)
{
cin>>ch;
for(int j='A', k='a'; j<='Z';j++, k++)
charMap[j] = charMap[k] = 0;
int len = ch.length();
for(int j=0;j<len;j++)
charMap[ch[j]]++;
str = "";
for(int j=0;j<26;j++)
{
for(int k=1;k<=charMap['A'+j];k++)
str.push_back('A'+j);
for(int k=1;k<=charMap['a'+j];k++)
str.push_back('a'+j);
}
permutation("", str);
myMap.clear();
}
return 0;
}
Code: Select all
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 100
int compare(const void *a, const void *b)
{
char x = *(char *)a,
y = *(char *)b;
if(tolower(x) == tolower(y))
return x > y;
return tolower(x) > tolower(y);
}
int strremove(char *string, int length_of_string, int index, char *new_string)
{
int length = 0;
int i;
for(i = 0; i < length_of_string; i++){
if(i == index)
continue;
new_string[length++] = string[i];
}
new_string[length] = '\0';
return length;
}
void dfs(char *selected, int length_of_selected, char *remaining, int length_of_remaining)
{
if(length_of_remaining == 0){
printf("%s\n", selected);
return;
}
char *new_remaining = malloc(sizeof(char) * (length_of_remaining+100));
int i, j;
for(i = 0; i < length_of_remaining; i++){
if(remaining[i] == selected[length_of_selected])
continue;
selected[length_of_selected] = remaining[i];
selected[length_of_selected+1] = '\0';
strremove(remaining, length_of_remaining, i, new_remaining);
dfs(selected, length_of_selected+1, new_remaining, length_of_remaining-1);
}
free(new_remaining);
}
int main(void)
{
int num;
char word[MAX], temp[MAX];
scanf("%d", &num);
while(num--){
scanf("%s", word);
qsort(word, strlen(word), sizeof(char), compare);
dfs(temp, 0, word, strlen(word));
}
return 0;
}
brianfry713 wrote:First I mapped A to 0, a to 1, B to 2, etc.
Then sort.
Finally I solved it using next_permutation from the STL.
Code: Select all
import java.io.*;
import java.util.*;
import java.math.*;
import java.text.*;
class Main {
static ArrayList<String> permutations;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
PrintWriter pr = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
String line = br.readLine();
int testcases = Integer.parseInt(line);
for (int kz = 0 ; kz < testcases ; kz++) {
line = br.readLine();
permutations = new ArrayList<String>();
ArrayList<Character> left = new ArrayList<Character>();
for (int i = 0 ; i < line.length() ; i++) {
left.add(new Character(line.charAt(i)));
}
Collections.sort(left);
permutate(left,"");
Collections.sort(permutations,new MyComparator());
String last = "";
if (permutations.size()>0) {
last = permutations.get(0);
pr.println(last);
}
for (int k = 1 ; k < permutations.size(); k++) {
String curr = permutations.get(k);
if (!last.equals(curr)) {
last = curr;
pr.println(curr);
}
}
}
pr.close();
}
public static void permutate(ArrayList<Character> line, String curr){
if (line.size()==0) {
permutations.add(curr);
}
for (int i = 0 ; i < line.size() ; i++) {
ArrayList<Character> clone = (ArrayList<Character>)line.clone();
clone.remove(i);
permutate(clone, curr+line.get(i));
}
}
}
class MyComparator implements Comparator<String>{
char[] index = {'A','a','B','b','C','c','D','d','E','e','F','f','G','g','H','h','I','i','J','j','K','k','L','l','M','m','N','n','O','o','P','p','Q','q','R','r','S','s','T','t','U','u','V','v','W','w','X','x','Y','y','Z','z'};
public int compare(String a, String b){
for (int j = 0 ; j < a.length() ; j++) {
char aa = a.charAt(j);
char bb = b.charAt(j);
int aaa = 0;
int bbb = 0;
for (int i = 0 ; i<52; i++) {
if (index[i]==aa) {
aaa = i ;
break;
}
}
for (int i = 0 ; i<52; i++) {
if (index[i]==bb) {
bbb = i;
break;
}
}
if (aaa>bbb) {
return 1;
}
if (bbb>aaa) {
return -1;
}
}
return 0;
}
}