Comment dois-je aller sur la génération de toutes les cartes possibles de combinaison de carte >?

Question

Je cherche à prendre un map<char, vector<char> > et générer chaque map<char, char> possible de celui-ci.

Je comprends cela peut utiliser une quantité importante de mémoire et prendre un peu de temps.

Chaque map<char, char> doit contenir toutes les lettres a-z, et être mis en correspondance avec un caractère a-z unique. c'est à dire. Alaska bj cp DY ev fh Géorgie hb ir JQ kn li mx NC oo pz qs rl Dakota du Sud te uw vf wg xm yu zt

Voici ce que je conclus pour moi jusqu'à présent:

Pour réduire le nombre ridicule de combinaisons possibles pour un montant inférieur, si un vector<char> contient plus de 5 éléments, je vais simplement le remplacer par un vector<char> contenant un seul ombles de mon « maître » / « original » map<char, char>.

Tous les caractères seront présents sur toute la vector<char>s sur la carte. Ces caractères doivent être trouvés et mis en quelques vecteur de 'autres de.

Cela devrait aussi contenir des caractères où un personnage est le seul caractère possible pour plus d'une touche de caractère (.-À-dire mw dans l'exemple, je travaille à partir - Je ne suis pas sûr comment aller à ce sujet).

Ce vecteur « autres » doit être utilisé pour les cas où il est impossible d'avoir un caractère a-z unique ou lorsque plus d'un personnage a le même caractère possible.

Voici un exemple de ce que j'ai jusqu'à présent.

Je vais prendre un map<char, vector<char> >, par exemple:

a: gjkpqvxz
b: gjkpqvxz
c: gjkpqvxyz
d: mw
e: gjkpqvxz
f: nr
g:
h: cf
i: son
j: gjkpqvxz
k: r
l: h
m: gjkpqvxz
n: gjkpquvxyz
o: est
p: gjkpqvxz
q: est
r: dl
s: l
t: e
u: dgkpuvy
v: cf
w: BCF
x: dguy
y: f
z: à

Ceci est ma carte de départ. Après avoir coupé les grands vecteurs de caractères de plus de 5 et de les remplacer par la meilleure estimation. Lorsque le est un vector<char> de taille 1, que le mappage de caractères a une seule combinaison, et ce caractère ne peut pas être utilisé dans toute autre application comme il le rendrait pas unique. Je l'ai coupé vers le bas à:

a: k
b: j
c: p
d: mw
e: v
f: n
g:
h: c
i: est
j: q
k: r
l: h
m: x
n: Guy
o: est
p: z
q: est
r: d
s: l
t: e
u: dguy
v: c
w: bc
x: dguy
y: f
z: à

L'vecteur « autres » contient « o » (je pense qu'il est important de noter que je pense que cela devrait contenir des cas tels que mw de l'exemple ci-dessus. Comme d est le seul endroit mw peut être utilisé, mais il est évident avec le besoin pour chaque lettre à seulement utilisée, un seul d'entre eux peut être utilisé, laissant l'autre à perdre quelque part. Je ne suis pas sûr de savoir comment s'y prendre pour la programmation d'un cas général pour les ajouter au vecteur d'autres.)

Je suis à la recherche de l'aide et des pointeurs avec la génération tous les map<char, char> possibles de map<char, vector<char> >s comme celui-ci et dans ce format. Ils seront utilisés comme argument dans un appel de fonction. Je ne suis pas vraiment sûr où commencer à écrire quelque chose qui fonctionnerait dans un sens général. J'approche probablement avec une grande quantité de boucles pour examiner chaque élément contre tout autre élément contre tout autre élément ... etc etc, que je suppose serait extrêmement inefficace et il y a probablement beaucoup plus élégante des façons de résoudre un tel problème .

Désolé si cela est trop mur de texte ish ou semble trop spécifique ou mal écrit / demandé.

Je vous remercie de toute aide.

Answer 1

Je suppose que j'espère que je ne ai pas besoin tous d'exister en même temps. Ensuite, je pouvais:

1) créer la première carte en attribuant le premier élément possible à chaque lettre:

for (char c = 'a'; c <= 'z'; ++c) {  // yes, I assume ASCII
   new_map[c] = old_map[c][0];
}
int indexes[26] = {0};

2) Créer les cartes restantes à son tour en modifiant la carte existante, à plusieurs reprises:

++indexes[0];
if (indexes[0] < old_map['a'].size()) {
    new_map['a'] = old_map['a'][indexes[0]];
} else {
    indexes[0] = 0;
    new_map['a'] = old_map['a'][0];
    // "carry the 1" by applying the same increment process to indexes[1]
}
do_something_with(new_map);

do_something_with peut re-construire le vecteur « autres » à chaque fois de la carte, ou bien vous pouvez le mettre à jour chaque fois que vous changez un caractère. Remplacer:

    new_map['a'] = something;

avec:

    char removed = new_map['a'];
    --counts[removed];
    if (counts[removed] == 0) others.add(removed);
    ++counts[something];
    if (counts[something] == 1) others.remove(something);
    new_map['a'] = something;

Dans votre exemple coupé vers le bas il y a seulement environ 6000 possibilités, ce qui devrait voler par. En fait, si vous avez besoin d'eux tout ce que vous pouvez simultanément copier la carte précédente à chaque étape, et il ne faudrait pas exactement jusqu'à la prochaine ère glaciaire.

BTW, avez-vous pensé qu'une carte est un peu exagéré pour seulement 26 clés possibles, dont chacun doit être présent dans toutes les cartes? Un vecteur ou un tableau serait beaucoup moins cher à utiliser et à copier.

Answer 2

  

Je comprends cela peut utiliser une quantité importante de mémoire et prendre un peu de temps.

Oui, le nombre de combinaisons est d'environ 403.291.461.000.000.000.000.000.000: -)