¿Cómo debo ir sobre la generación de cada mapa es posible combinación de mapa >?

Question

Estoy buscando para tomar un map<char, vector<char> > y generar cada posible map<char, char> de ella.

Entiendo que esto puede utilizar una cantidad considerable de memoria y tomar un poco de tiempo.

Cada map<char, char> debe contener todas las cartas a-z, y ser asignado a un carácter único a-z. es decir. Alaska bj cp dy ev FH Georgia media pensión IR JQ kn li mx Carolina del Norte oo pz qs rl Dakota del Sur Te UW vf WG XM Yu ZT

Esto es lo que he concluido para mí hasta ahora:

Para reducir el número ridículo de combinaciones posibles a una cantidad inferior, si un vector<char> contiene más de 5 elementos, simplemente voy a reemplazarlo con un vector<char> que contiene un solo carbón de mi 'maestro' / map<char, char> 'original'.

No todos los personajes estarán presentes durante toda la vector<char>s en el mapa. Estos caracteres se deben encontrar y poner en vector de algunos 'otros'.

Esto también debe contener caracteres donde uno de ellos es el único personaje posible que más de una tecla de carácter (. Mw es decir, en el ejemplo que estoy trabajando desde - estoy seguro de cómo ir sobre esto).

Este vector 'otros' se debe utilizar para los casos en que no sea posible tener un único carácter a-z, o cuando más de un personaje tiene el mismo carácter, sencillo posible.

Este es un ejemplo de lo que tengo hasta ahora.

I va a tomar un map<char, vector<char> >, tales como:

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

Este es mi mapa de partida. Después de cortar los grandes vectores de caracteres de más de 5 y su sustitución por la mejor conjetura. Donde el es un vector<char> de tamaño 1, asignación de caracteres que sólo tiene una combinación, y que el personaje no puede ser utilizado en cualquier otra asignación, ya que haría que no es único. He recortado se reduce a:

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

vector Los 'otros' contiene 'o' (creo que es importante señalar que creo que esto debería contener casos como mw en el ejemplo anterior. A medida que d es el único lugar MW se puede utilizar, pero, obviamente, con el necesitará para cada letra que sólo se usa una vez, sólo uno de ellos puede ser utilizado, dejando el otro para ser perdido en algún lugar. no estoy seguro de cómo ir sobre la programación de un caso general para agregar éstos al vector otros.)

Busco ayuda y punteros con la generación de todas las posibles map<char, char> de map<char, vector<char> >s como este y en este formato. Serán utilizados como argumento en una llamada de función. No estoy realmente seguro de por dónde empezar a escribir algo que funcione en un sentido general. probablemente me acerco con una gran cantidad de los bucles que buscan a través de cada elemento en contra de todos los demás elementos contra todos los demás elementos, etc, etc ..., que yo supongo que sería extremadamente ineficiente y, probablemente, hay maneras mucho más elegante de resolver un problema tan .

Lo siento si esto es demasiado muro de texto-ish o parece demasiado específico o mal escrito / pedido.

Agradezco cualquier y toda la asistencia.

Answer 1

supongo yo espero que no a todos necesito existir simultáneamente. Entonces pude:

1) Crear el primer mapa asignando el primer elemento sea posible a cada letra:

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

2) Crear los mapas restantes a su vez, mediante la modificación del mapa existente, en repetidas ocasiones:

++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 puede volver a construir los "otros" vector cada vez desde el mapa, o bien puede actualizar cada vez que se cambia un carácter. Reemplazar:

    new_map['a'] = something;

por:

    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;

En el ejemplo recortado hacia abajo sólo hay alrededor de 6.000 posibilidades, que deben volar. De hecho, si se hizo los necesita todos al mismo tiempo se podría copiar el mapa anterior a cada paso, y que no tomaría exactamente hasta la próxima edad de hielo.

Por cierto, ¿ha considerado que un mapa es un poco exagerado para sólo 26 claves posibles, cada una de las cuales se requiere para estar presente en cada mapa? Un vector o matriz serían considerablemente más barato de usar y copiar.

Answer 2

  

Entiendo que esto puede utilizar una cantidad considerable de memoria y tomar un poco de tiempo.

Sí, el número de combinaciones es de aproximadamente 403.291.461.000.000.000.000.000.000: -)