Como devo gerar todas as combinações possíveis de map<char, char> a partir de map<char, vector<char> >?

Question

estou querendo pegar um map<char, vector<char> > e gerar cada possível map<char, char> a partir dele.

Entendo que isso pode usar uma quantidade considerável de memória e demorar um pouco.

Cada map<char, char> precisa conter todas as letras a-z e ser mapeado para um caractere a-z exclusivo.ou seja.AK BJ CP DY EV FH GA HB IR JQ KN Li MX NC OO PZ QS RL SD TE UW VF WG XM YU ZT

Aqui está o que concluí para mim mesmo até agora:

Para reduzir o número ridículo de combinações possíveis a um valor menor, se um vector<char> contém mais de 5 elementos, vou simplesmente substituí-lo por um vector<char> contendo um único caractere do meu 'master'/'original' map<char, char>.

Nem todos os personagens estarão presentes em todo o vector<char>s no mapa.Esses caracteres precisam ser encontrados e colocados em algum vetor de 'outros'.

Também deve conter caracteres onde um caractere é o único caractere possível para mais de uma chave de caractere (ou seja,mw no exemplo em que estou trabalhando - não tenho certeza de como fazer isso).

Este vetor 'outros' deve ser usado para os casos em que não é possível ter um caractere az único ou onde mais de um caractere possui o mesmo caractere único possível.

Aqui está um exemplo do que tenho até agora.

eu vou tomar um map<char, vector<char> >, como:

a:gjkpqvxz
b:gjkpqvxz
c:gjkpqvxyz
d:hum
e:gjkpqvxz
f:nº
g:no
h:cf.
eu:dele
j:gjkpqvxz
k:R
eu:h
eu:gjkpqvxz
n:gjkpquvxyz
ó:é
p:gjkpqvxz
q:é
R:dl
é:eu
t:e
você:dgkpuvy
v:cf.
c:bcf
x:cara
você:f
z:no

Este é o meu mapa inicial.Depois de cortar os vetores de caracteres grandes com mais de 5 e substituí-los pela melhor estimativa.Onde está um vector<char> de tamanho 1, esse mapeamento de caracteres possui apenas uma combinação e esse caractere não pode ser usado em nenhum outro mapeamento, pois isso o tornaria não único.Eu reduzi para:

a:k
b:j
c:p
d:hum
e:v
f:n
g:no
h:c
eu:é
j:q
k:R
eu:h
eu:x
n:cara
ó:é
p:z
q:é
R:d
é:eu
t:e
você:cara
v:c
c:a.C.
x:cara
você:f
z:no

O vetor 'outros' contém 'o' (acho importante observar que deve conter casos como mw do exemplo acima.Como d é o único lugar que mw pode ser usado, mas obviamente com a necessidade de cada letra ser usada apenas uma vez, apenas uma delas pode ser usada, deixando a outra perdida em algum lugar.Não tenho certeza de como programar um caso geral para adicioná-los ao outro vetor.)

Estou procurando ajuda e dicas para gerar todos os possíveis map<char, char> de map<char, vector<char> >s assim e neste formato.Eles serão usados ​​como argumento em uma chamada de função.Não tenho certeza por onde começar a escrever algo que funcione em um sentido geral.Eu provavelmente abordaria isso com uma grande quantidade de loops for examinando cada elemento em relação a todos os outros elementos em relação a todos os outros elementos ...etc etc, o que presumo seria extremamente ineficiente e provavelmente existem maneiras muito mais elegantes de resolver esse problema.

Desculpe se isso é muito textual ou parece excessivamente específico ou mal escrito/perguntado.

Agradeço toda e qualquer ajuda.

Answer 1

Acho que espero não precisar que todos existam simultaneamente.Então eu poderia:

1) Crie o primeiro mapa atribuindo o primeiro elemento possível 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) Crie os mapas restantes, modificando o mapa existente, repetidamente:

++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 pode reconstruir o vetor "outros" a cada vez a partir do mapa, ou então você pode atualizá-lo cada vez que mudar um personagem.Substituir:

    new_map['a'] = something;

com:

    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;

No seu exemplo reduzido, existem apenas cerca de 6.000 possibilidades, que devem passar voando.Na verdade, se você precisasse de todos eles simultaneamente, poderia copiar o mapa anterior a cada passo, e isso não demoraria exatamente até a próxima era glacial.

A propósito, você já considerou que um mapa é um pouco exagerado para apenas 26 chaves possíveis, cada uma das quais deve estar presente em todos os mapas?Um vetor ou array seria consideravelmente mais barato de usar e copiar.

Answer 2

Entendo que isso pode usar uma quantidade considerável de memória e demorar um pouco.

Sim, o número de combinações é de cerca de 403.291.461.000.000.000.000.000.000 :-)