[ANSI C] calcolo combinatorio ricorsivo

[andr3a]

salve, espongo subito il mio problema:

data una stringa in input, che ammette N caratteri ma che questi caratteri possono essere solo 0, 1 ed x , dove x e' un carattere incognita, dovrei mostrare un output ordinato dove per ogni x modifico il valore 0 ed 1 a seconda della posizione.

esempio

xx dara'

00
01
10
11


mentre 1x0 , ad esempio dara'

100
110


oppure 1xxx

1000
1001
1010
1011
1100
1101
1110
1111


le relazioni che conosco e' che l' output sara' costituito da, ad esempio

2(combinazioni, 0 ed 1) ^(alla) 3(presenza di x)

e che la x, in quella posizione, partendo da destra verso sinistra cambiera' ogni

2(combinazioni, 0 ed 1) ^ posizioneX(da destra verso sinistra, a partire da ZERO)

esempio pratico

x0x

la x a destra, la prima, quindi quella a posizione zero, cambiera' di valore, a partire da 0, ogni 2^0 volte, ovvero ogni volta che mostro l' output la x avra' valore diverso da quello precedente

la seconda x, in questo caso quella a sinistra, cambiera' ogni 2^1 volte, ovvero ogni 2 volte che mostro l' output cambia

000
001 <-- cambia
1 <-- cambia 00 <-- cambia
101 <-- cambia


Ora, considerando che la mia analisi potrebbe anche essere sbagliata ma per ora funziona alla grande, esiste un modo ricorsivo e piu' logico per effettuare questi cambiamenti o fare lo stesso tipo di programma ?

grazie

[kentaromiura]

e' una legge matematica che vale per tutte le potenze di due..
(e per tutte le basi pesate!)
quindi la tua supposizione e' corretta.

per la ricorsione ci devo pensare..

[unomichisiada]

Praticamente il problema coincide con quello di generare ricorsivamente tutti i numeri binari con un numero di bit pari a n (dove n è il numero di x),l'unica cosa è che devi incastonare i bit generati tra quelli che hai fissi (ma non mi sembra un grande problema).Io il problema che ti ho esposto l'ho già risolto ricorsivamente parecchio tempo fa,quindi probabilmente se ti posto il codice (al limite stasera sul tardi ora non posso) te lo modifichi ed in un attimo risolvi il tuo problema

[unomichisiada]

Per altro l'algoritmoi non differisce molto da quello che ho usato nella seconda pagina di questo 3d http://forum.html.it/forum/showthrea...t=permutazioni

[andr3a]

Originariamente inviato da unomichisiada
Per altro l'algoritmoi non differisce molto da quello che ho usato nella seconda pagina di questo 3d http://forum.html.it/forum/showthrea...t=permutazioni

1 - grazie, se potessi postarmi il codice stasera te ne sarei grato
2 - ho letto l' altro 3D ... capito una cippa


in realta' io ho gia' risolto questo problema senza alcuna nozione matematica, scrivendo a matita su un foglio sono giunto a quelle conclusioni


solo che ora applicarlo con matrici o altro mi resta difficile, io l' ho applicato con cicli e contro cicli, in realta' dovrei applicarlo in modo ricorsivo ... ed e' su questo che non ci sto' dormendo la notte da circa 1 settimana ... dove faccio la ricorsione ?
in base a cosa ?

devo portarmi dietro tutta la vagonata di variabili per usare il mio metodo in una funzione ricorsiva ?
saprebbe piu' di presa in giro che altro ... penso ci sia un metodo piu' valido e realmente ricorsivo per affrontare la questione ... aiuto


se la ricorsione la facessi sull' ultima possibile combinazione ... tipo

if( stringa != '1111' ) {
questa_funzione( stringa_con_x, posizione, etc etc )
}


???

[Ilmalcom]

Credo che i casi basi siano:
- carattere == 0 || carattere == 1, in quanto in tal caso stampo semplicemente il carattere e vado a valutare il successivo
- carattere == '\0', in quanto in tal caso stampo una nuova linea ed ho terminato

Quando trovo invece la x bisogna stampare uno 0 o un 1 e valutare ricorsivamente la parte successiva della stringa. L'idea credo sia questa

[unomichisiada]

Originariamente inviato da andr3a
1 - grazie, se potessi postarmi il codice stasera te ne sarei grato
2 - ho letto l' altro 3D ... capito una cippa


in realta' io ho gia' risolto questo problema senza alcuna nozione matematica, scrivendo a matita su un foglio sono giunto a quelle conclusioni


solo che ora applicarlo con matrici o altro mi resta difficile, io l' ho applicato con cicli e contro cicli, in realta' dovrei applicarlo in modo ricorsivo ... ed e' su questo che non ci sto' dormendo la notte da circa 1 settimana ... dove faccio la ricorsione ?
in base a cosa ?

devo portarmi dietro tutta la vagonata di variabili per usare il mio metodo in una funzione ricorsiva ?
saprebbe piu' di presa in giro che altro ... penso ci sia un metodo piu' valido e realmente ricorsivo per affrontare la questione ... aiuto


se la ricorsione la facessi sull' ultima possibile combinazione ... tipo

if( stringa != '1111' ) {
questa_funzione( stringa_con_x, posizione, etc etc )
}


???

No tranquillo le matrici non servono,l'altro 3d era solo per darti un'idea dell'algoritmo,ma quello per generare tutti i binari di lunghezza usa solo un arrai d ilunghezza ntranquillo ed è anche semplice da capire.Stasera te lo posto

[andr3a]

Originariamente inviato da unomichisiada
No tranquillo le matrici non servono,l'altro 3d era solo per darti un'idea dell'algoritmo,ma quello per generare tutti i binari di lunghezza usa solo un arrai d ilunghezza ntranquillo ed è anche semplice da capire.Stasera te lo posto

grazie mille , uso gia' 2 array con calloc dinamici in base alla lungheza stringa e presenze di x ... visto mai riuscissi a capirlo e a riadattarlo in modo semplice per il mio lavoro , attendo con ansia

[andr3a]

a che ora e' sera ?

[unomichisiada]

Originariamente inviato da andr3a
a che ora e' sera ?

Ora te lo cerco e te lo posto