i'm preparing interviews , i'm trying memorize heap's algorithm:
procedure generate(n : integer, : array of any): if n = 1 output(a) else := 0; < n; += 1 generate(n - 1, a) if n swap(a[i], a[n-1]) else swap(a[0], a[n-1]) end if end end if this algorithm pretty famous 1 generate permutations. concise , fast , goes hand-in-hand code generate combinations.
the problem is: don't memorize things heart , try keep concepts "deduce" algorithm later.
this algorithm not intuitive , can't find way explain how works myself.
can please tell me why , how algorithm works expected when generating permutations?
heap's algorithm not answer reasonable interview question. there more intuitive algorithm produce permutations in lexicographical order; although amortized o(1) (per permutation) instead of o(1), not noticeably slower in practice, , easier derive on fly.
the lexicographic order algorithm extremely simple describe. given permutation, find next 1 by:
finding rightmost element smaller element right.
swap element smallest element right larger it.
reverse part of permutation right of element was.
both steps (1) , (3) worst-case o(n), easy prove average time steps o(1).
an indication of how tricky heap's algorithm (in details) expression of wrong, because 1 swap; swap no-op if n even, creates problem when n odd. see https://en.wikipedia.org/wiki/heap%27s_algorithm correct algorithm (at least, it's correct today) or see discussion @ heap's algorithm permutation generator
to see how heap's algorithm works, need @ full iteration of loop vector, in both , odd cases. given vector of length, full iteration of heap's algorithm leave vector rotated left 1 position. if vector of odd length, @ end of algorithm vector reversed. can prove both of these facts true using induction, although doesn't provide intuition why it's true. looking @ diagram on wikipedia page might help.
Comments
Post a Comment