[Algoritmi] Stampare sequenza di k elementi da 1 a n

[Bartolomeo2]

Salve ragazzi,
ho bisogno di aiuto per la risoluzione di un algoritmo.. l'algoritmo può anche essere fatto in speudo-codice... non mi interessa un linguaggio particolare...

La traccia è la seguente:

Dare lo pseudo-codice di un algoritmo che, presi in
input due interi positivi n e k, stampa tutte le sequenze di lunghezza k degli interi {1,2,…,n}
NON DECRESCENTI.

Ad esempio, per n = 4 e k = 3 deve stampare le seguenti sequenze:
111 112 113 114 122 123 124 133 134 144 222 223 224 233 234 244 333 334 344 444

La complessità dell'algoritmo deve essere O(nS(n, k)), dove S(n, k) è il numero di sequenze da stampare per i parametri n e k.

Al momento la comlessità computazionale non mi interesssa... mi interessa anche solo l'algoritmo.... mi sto scervellando ma mi escono cicli su cicli e neanche il risultato corretto ottengo..

grazie

[Quinzio]

Prima di stampare ogni sequenza

good =yes;
for (a=0, a

Cita

Segnala

[apatriarca]

Il metodo più semplice di descrivere un algoritmo di questo tipo è usando la ricorsione. Sia \( F(s, n, k) \) la funzione che restituisce tutte le sequenze di lunghezza \(k\) non decrescenti di numeri interi compresi tra \(s\) ed \(n\) (inclusi). Ovviamente si deve avere \(s \leq n\) e il tuo algoritmo deve calcolare \( F(1, n, k) \). Vediamo ora come si può calcolare.

Prendiamo in considerazione il valore iniziale. Questo valore deve essere un numero qualsiasi compreso tra \(1\) e \(n\). Considero tutte le sequenze che partono da un numero fissato \(i\). Queste sequenze saranno formate dal valore \(i\) seguito da una delle sequenze non decrescenti di \(k-1\) valori compresi tra \(i\) e \(n\). Abbiamo quindi scoperto che
\[ F(s, n, k) = \begin{cases} \{ i S \mid \forall s \leq i \leq n, S \in F(i, n, k-1) \} & k > 0 \\ \epsilon & \text{otherwise} \end{cases} \]
Con \(\epsilon\) intendo l'insieme che contiene soltanto una stringa (sequenza) vuota.

[Bartolomeo2]

mmm... c'è ancora qualcosa che mi sfugge... sto cercando di trasformare in codice quello che mi hai detto

  
        public static int F(int s, int n, int k)
        {
            //s <= n
            int i = 1;

            while (i <= n)
            {
                if (k > 0)
                {
                    F(s, n, k - 1);
                }


                i++;

                return i;
            }
              //  s++;
            //}
        }

        static void Main(string[] args)
        {
            int n = 4;
            int k = 3;

            F(1, n, k);

            Console.ReadLine();
        }

Ma ancora non va... non riesco a capire... k è la posizione del valore da stampare... i è il valore da stampare... s ed n sono i limiti... ok... ma non riesco a ottenere quanto richiesto...

[apatriarca]

Ci sono due problemi:
- Non hai inserito la condizione per terminare la ricorsione.
- Non stai generando ne stampando nulla.

[Bartolomeo2]

"apatriarca":Ci sono due problemi:
- Non hai inserito la condizione per terminare la ricorsione.
- Non stai generando ne stampando nulla.

Eh si scusa... ho fatto un milione di tentativi... e alla fine ho cancellato un pò di roba... ora lo rivedo...

[Bartolomeo2]

In ogni caso, la ricorsione non termina con k = 0 ?

[apatriarca]

Per poter implementare la mia idea hai bisogno di usare un qualche linguaggio funzionale tipo haskell (in cui si può implementare quella formula praticamente in modo diretto, oppure usare una lista (in realtà una pila/stack) di appoggio come nel seguente codice in Python.

def fun(s, n, k):
    return fun_ric(s, n, k, [])
    
def fun_ric(s, n, k, list):
    if (k <= 0):
        print list
        return
    for i in range(s, n+1):
        list.append(i)
        fun_ric(i, n, k-1, list)
        list.pop()

fun(1, 3, 3)