Come devo fare per generare ogni possibile mappa combinazione di mappa >?

Question

Sto cercando di prendere un map<char, vector<char> > e generare ogni possibile map<char, char> da esso.

Capisco che questo può utilizzare un numero considerevole di memoria e di prendere un po 'di tempo.

Ogni map<char, char> deve contenere ogni lettera a-z, ed essere mappato a un unico carattere a-z. vale a dire. 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

Ecco quello che ho concluso per me finora:

Per ridurre il numero ridicolo di possibili combinazioni per un importo inferiore, se un vector<char> contiene più di 5 elementi, mi limiterò a sostituirlo con un vector<char> contenente un singolo carattere dal mio 'maestro' / map<char, char> 'originale'.

Non tutti i personaggi saranno presenti su tutta la vector<char>s nella mappa. Questi personaggi hanno bisogno di essere trovato e messo in vettore alcuni 'altri'.

Questo dovrebbe contenere anche caratteri in cui un personaggio è l'unico personaggio possibile per più di un tasto carattere (. Es mw nell'esempio sto lavorando da - io sono sicuro di come fare per questo).

Questo vettore 'altri' deve essere utilizzato per i casi in cui non è possibile avere un unico carattere a-z, o dove più di un carattere ha la stessa, singolo carattere possibile.

Ecco un esempio di quello che ho finora.

Sarò prendendo un map<char, vector<char> >, come ad esempio:

A: gjkpqvxz
B: gjkpqvxz
c: gjkpqvxyz
D:
mw e: gjkpqvxz
f: nr
g: a
h: cf
I: la sua
j: gjkpqvxz
k: r
l: h
m: gjkpqvxz
n: gjkpquvxyz
o: è
p: gjkpqvxz
q: è
R:
dl s: l
t: e
u: dgkpuvy
v: cf
w: bcf
x: dguy
y: f
z: a

Questa è la mia mappa di partenza. Dopo aver tagliato i grandi vettori di caratteri di oltre 5 e la loro sostituzione con l'ipotesi migliore. Dove la è una vector<char> di dimensione 1, quella mappatura personaggio ha una sola combinazione, e che il carattere non può essere utilizzato in qualsiasi altra mappatura quanto renderebbe non unico. Ho tagliato giù a:

A: k
B: j
c: p
D:
mw e: v
f: n
g: a
h: c
I: è
j: q
k: r
l: h
m: x
n: ragazzo
o: è
p: z
q: è
r: d
s: l
t: e
u: dguy
v: c
w: bc
x: dguy
y: f
z: a

vettore Gli 'altri' contiene 'o' (Credo sia importante notare che che questo dovrebbe contenere casi come mw dall'esempio precedente. Poiché d è l'unico luogo mw può essere utilizzato, ma ovviamente con la necessità di ogni lettera deve essere utilizzato solo una volta, solo uno di essi può essere utilizzato, lasciando l'altro di essere perso da qualche parte. non sono sicuro di come fare per la programmazione di un caso generale per aggiungere questi al vettore altri.)

Sto cercando aiuto e puntatori con la generazione di ogni possibile map<char, char> da map<char, vector<char> >s come questo e in questo formato. Essi saranno utilizzati come argomento in una chiamata di funzione. In realtà non sono sicuro da dove iniziare a scrivere qualcosa che avrebbe funzionato in senso generale. Io probabilmente avvicino con una grande quantità di cicli for guardando attraverso ogni elemento contro ogni altro elemento contro ogni altro elemento ... ecc ecc, che presumo sarebbe estremamente inefficiente e ci sono probabilmente molto più elegante modi di risolvere un tale problema .

Scusate se questo è troppo muro di testo-ish o sembra eccessivamente specifico o scritto male / chiese.

Apprezzo ogni e qualsiasi assistenza.

Answer 1

Credo che mi auguro che non ho bisogno di tutti loro di esistere simultaneamente. Poi ho potuto:

1) Creare la prima mappa assegnando il primo elemento di possibile ogni lettera:

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

2) Creare le mappe rimanenti a loro volta modificando la mappa esistente, più volte:

++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 può ri-costruire il "altri" vettore di volta in volta dalla mappa, oppure è possibile aggiornare ogni volta che si cambia un carattere. Sostituire:

    new_map['a'] = something;

con:

    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;

Nel tuo esempio tagliato in giù ci sono solo circa 6000 possibilità, che dovrebbe volare. In realtà, se si aveva bisogno di tutti loro allo stesso tempo è possibile copiare la mappa precedente ad ogni passo, e non sarebbe esattamente prendere fino alla prossima era glaciale.

A proposito, avete considerato che una mappa è un po 'eccessivo per solo 26 chiavi possibili, ognuno dei quali è richiesto di essere presenti in ogni mappa? Un vettore o un array sarebbero notevolmente più economico da usare e da copiare.

Answer 2

  

Capisco che questo può utilizzare un numero considerevole di memoria e di prendere un po 'di tempo.

Si, il numero di combinazioni è di circa 403.291.461.000.000.000.000.000.000: -)