Maths: Trouver le numéro de permutation en utilisant une pile

Question

C'est plus un problème de maths je suppose, rien de programmation.

Supposons que j'ai un stack et je veux trouver le permutations des numéros 1,2,3,...n. Je peux push et pop. par exemple. si n = 2: push,pop,push,pop 1,2 et 2,1 push,push,pop,pop

si n = 4 je ne peux obtenir 14 des 24 permutations en utilisant le stack .. ce que quelqu'un sait tout function F(n) qui pourrait produire le nombre de permutations la pile (un seul) peut produire? par exemple f (1) = 1

f (2) = 2

f (4) = 14

Answer 1

je pense qu'il y a une formule très simple pour cela. Vous êtes à la recherche de permutations de N opérations push ("X") et N opérations pop ("Y"), suivant une règle simple:

• Pas de pop sur une pile vide (Y fe .... et XXYYY ... ne sont pas valides)

peut-être une définition récursive aide:

function F(n_push, n_pop) { 
    int total_count = 0; 

    if (n_push > 0) total_count += F(n_push - 1, n_pop); 
    if (n_pop > n_push) total_count += F(n_push, n_pop - 1); 

    return total_count; 
} 

Answer 2

Cette fonction est un nombre catalan. Voir http://en.wikipedia.org/wiki/Catalan_number pour la formule.