Ottenimento della permutazione mediante ricorsione [chiuso]

Question

Ottenimento della permutazione mediante ricorsione [chiuso]

#1 da (0 voti)

0

Anche se mi piacciono le ricorsioni e capisco, non riesco a padroneggiarlo! Sono bloccato con un problema che so che la ricorsione può risolvere, ma non so come.

Ho una serie di stringhe come: "cento", "cinquanta", "trentacinque" ecc. Ho "x" numero di posti per sistemarli ma la condizione è, la stringa che segue al posto successivo dovrebbe sempre essere minore uguale o uguale alla stringa che lo precede.

Ad esempio: Array di stringhe: "cento", "cinquanta", "trentacinque"

Numero di posti: 4

Poche delle possibilità corrette:

"centocinquecento, cinquanta"
"centodecentonovantatrè"
"centocinquanta, cinquanta"
"cento, cinquanta, trentacinque"
ecc.

Esempi di possibilità errate:

cinquanta, cento , centotrentatre
cento, cinquanta, cento , trentacinque

Con il meglio che potessi pensare, ho creato una funzione ricorsiva in cui provo a posizionare queste stringhe e quindi ad aumentare i parametri in modo che lo stesso compito venga ripetuto in ricorsione per il resto degli slot. Fiddle qui: link

function invokePermutation()
{
    var permutation_array = [];
    var currentPositions = {
        row: 0,
        column: 0
    };
    getComponentPermutations (["hundred", "fifty", "thirtythree"], permutation_array, 4, currentPositions);
    console.log(permutation_array.join("\n"));

   var title = document.getElementById('container');
   title.innerHTML = permutation_array.join("<br />");
}

function getComponentPermutations(modeArray, permutation_array, max_positions, current_positions) {
            // Stopping condition
        if (max_positions === current_positions.column && modeArray.length) {
            current_positions.column = 0; // Reset column
            current_positions.row = current_positions.row + 1; // Move to next row
        }
    else{
        for (i = 0; i < modeArray.length; i++) {
            if (0 === current_positions.column) {
                // http://stackoverflow.com/a/29881936/260665
                permutation_array[current_positions.row] = [];
            }
            permutation_array[current_positions.row][current_positions.column] = modeArray[i];

            // Lets move to next position in column
            current_positions.column = current_positions.column + 1;

            // The array which we pass for recursion can only have the current modeArray and items lesser than it. For ex, if currenty iteration has fifty, we have to generate an array with fifty and thirtythree to pass on. It should not have hundred in it!
            var newModeArray = modeArray.slice(i);
            getComponentPermutations(newModeArray, permutation_array, max_positions, current_positions); // Recursion
        }
    }
}

Tuttavia, i risultati non sono quelli che mi aspetto, non elencano tutte le possibilità.

Sono sicuro che il mio codice / algoritmo è sbagliato, ma non capisco qual è la strada giusta! Apprezzo se qualcuno mi può aiutare a capire dove sto andando male e come risolvere questo problema.

recursion math

posta Raj Pawan Gumdal 11.05.2016 - 15:56

fonte

1 risposta

Leggi altre domande sui tag recursion math

DAO - Come pacchetto separato o incapsulato nel Servizio stesso? utilizzando pthread_cond_broadcast senza mutex o thread in attesa?

score 0 · Accepted Answer

Ho funzionato in questo modo:

function invokePermutation()
{
    var permutation_array = [];
    getComponentPermutations (["hundred", "fifty", "thirtythree"], 0, [], 4, permutation_array);
    console.log(permutation_array.join("\n"));

   var title = document.getElementById('container');
   title.innerHTML = permutation_array.join("<br />");
}

function getComponentPermutations(possibilities, current_lowest_possibility_index, current_array_beginning, max_positions, completed_permutations) {
    //if the current array we are building up is the max length, add it to our result set
    if (current_array_beginning.length == max_positions) {
        completed_permutations.push(current_array_beginning);
        return;
    }
    //we've run out of other possibilities to use, so return
    if (current_lowest_possibility_index >= possibilities.length) {
        return;
    }
    //take the current part we are building up and call this for the next possibility to put in the next slot
    getComponentPermutations(possibilities, current_lowest_possibility_index + 1, current_array_beginning, max_positions, completed_permutations);

    //add the current possibility
    var cloned_beginning = current_array_beginning.slice();
    cloned_beginning.push(possibilities[current_lowest_possibility_index]);
    //recurse
    getComponentPermutations(possibilities, current_lowest_possibility_index, cloned_beginning, max_positions, completed_permutations);
}

Nota che questo dipende dalla serie di possibilità che vengono ordinate in modo tale che i valori "superiori" vengano prima di quelli "inferiori".

Forse è meglio vederlo usando un esempio di come si costruiscono gli array. In primo luogo, inizierà con un array vuoto come quello che abbiamo accumulato finora. Quindi eseguirà e farà la prima chiamata ricorsiva fino a quando la possibilità attuale non sarà nell'indice 2 (cioè "trentatre"). Quindi quella prima chiamata tornerà appena.

Quindi lo aggiungeremo a ciò che stiamo creando, quindi abbiamo ["thirtythree"] . Quindi ricontattiamo di nuovo, ma ora con lo stato corrente è ["thirtythree"] e l'attuale possibilità è "trentatré". Le chiamate continuano fino a quando non abbiamo costruito un array come questo ["thirtythree","thirtythree","thirtythree","thirtythree"] . Quindi, alla fine, la prossima chiamata va nel primo blocco if per aggiungerla al nostro set di risultati.

Quindi si esegue il backup ritornando finché lo stato corrente dell'array è ["thirtythree","thirtythree","thirtythree"] e l'elemento successivo da usare è "fifty". Quindi viene aggiunto ["thirtythree","thirtythree","thirtythree","fifty"] . E così via fino a quando lo stack non si è svolto fino a mettere in ["hundred","hundred","hundred","hundred"] .