NTRUEncrypt - Choose the initial random polynomial
So long the GCD of f(1) with p and with q is 1, f will have an inverse with high probability. (f(1) = f evaluated at 1, i.e. the sum of the coefficients of f).

If you take f to be binary with df 1s, then take df to be relatively prime to p and q.

If you take f to be trinary and it has df 1s and df-1 -1s, then f(1) = 1 and this will satisfy the GCD requirement identically.

If you take f to be of form 1 + pF, f(1) is 1 mod p and satisfies that requirement identically. For the GCD requirement mod q, either pick F to be trinary with equal +1s and -1s (so f(1) = 1) or pick F to be binary such that 1 + p*F(1) is relatively prime to q.

"High probability" above means that the probability of not having an inverse goes down rapidly as both q and N increase. I've posted toy examples on Stack Overflow (http://stackoverflow.com/questions/2754444/meet-in-the-middle-atack-on-an-ntru-private-key) and when I generated them I came up with invertible keys on the first attempt for N = 11, q = 29.